在非空二叉树的中根遍历序列中,二叉树的根结点的左边()
A.只有左子树上的部分结点
B.只有左子树上的所有结点
C.只有右子树上的所有结点
D.只有右子树上的部分结点
A.只有左子树上的部分结点
B.只有左子树上的所有结点
C.只有右子树上的所有结点
D.只有右子树上的部分结点
第6题
A.先序(根、左、右)
B.中序(左、根、右)
C.后序(左、右、根)
D.层序(从树根开始,按层次)
第7题
A.先序(根、左、右)
B.中序(左、根、右)
C.后序(左、右、根)
D.层序(从树根开始,按层次)
第8题
(42)
A. 先序(根、左、右)
B. 中序(左、根、右)
C. 后序(左、右、根)
D. 层序(从树根开始,按层次)
第9题
A.先序(根、左、右)
B.中序(左、根、右)
C.后序(左、右、根)
D.层序(从树根开始,按层次)
第10题
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode{
ElemTypedata; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode*ichiid,*rchild; /*结点的左、右弦子指针域*/
)BtNode,*BTree;
在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点
的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode{ /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
struct StNode*link;
}S%Node;
假设从栈顶到栈底的元素为en、en-1、…、e1,则不含头结点的链栈示意图如图5—5
所示。
【C函数】
int InOrder(BTree root) /*实现二叉树的非递归中序遍历*/
{
BTree ptr; /*ptr用于指向二又树中的结点*/
StNode*q; /*q暂存链栈中新创建或待删除的结点指针+/
StNode*stacktop=NULL; /*初始化空栈的栈顶指针stacktop*/
ptr=root; /*ptr指向二叉树的根结点*/
while( (1 ) I I stacktop!=NULL){
while(ptr!=NULL){
q=(StNode*)malloc(sizeof(StNode));
if(q==NULL)
return-1;
q->elem=ptr;(2) ;
stacktop=q; /*stacktop指向新的栈顶*/
ptr=(3 ) ; /*进入左子树*/
}
q=stacktop; (4) ; /*栈顶元素出栈*/
visit(q); /*visit是访问结点的函数,其具体定义省略*/
ptr= (5) ; /*进入右子树*/
free(q); /*释放原栈顶元素的结点空间*/
}
return 0;
}/*InOrder*/
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!