非递归中序遍历(空指针进栈)含有 n 个结点高度为 h 的二叉树时,为了确保栈在处理过程中不会发生上溢,则该栈至少要有()个存储单元。
A.n
B.n+1
C.h
D.h+1
A.n
B.n+1
C.h
D.h+1
解题思路:二叉树的先序遍历非递归算法利用栈结构,从二又树的根结点开始,输出结点信息,同时将结点指针入栈,然后顺着左子树,依次将其左子树各个结点值输出,同时结点指针入栈,直到左子树为空;然后让栈顶指针出栈,接着处理右子树。
A、010
B、0120
C、012
D、0 1 0
E、0 1 2 0
F、0 1
G、0 1 2
[说明]
借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历,遍历
过程如下:
若不是空树,根节点入栈,进入左子树;若已经是空树,则栈顶元素出栈,访问该元素(根节点),进入该节点的右子树,继续直到遍历完成。
函数中使用的预定义符号如下:
typedef struct BiTNode{
int data;
struct BiTNode *iChiid,*rChiid;
} BiTNode,*BiTree;
typedef struct SNode{/*链栈的节点类型*/
BiTree elem;
struct SNode *next;
}SNode;
[函数]
int InOrderTraverse(BiTree root)
{
BiTree P;
SNode *q,*stop=NULL;/*不带头节点的单链表作为栈的存储结构*/
P=root;
while(p !=NULL || stop !=NULL){
if( (1) ){ /*不是空树*/
q=(SNode*)malloc(sizeof q);
if(q==NULL)return-1;
/*根节点指针入栈*/
(2);
q->elem=P;
stop=q;
P=(3); /*进入根的左子树*/
}else{
q=stop;
(4); /*栈顶元素出栈*/
printf("%d|,q->elem->data); /*防问根节点*/
P=(5); /*进入根的右子树*/
free(q); /*释放原栈顶元素*/
}/*if*/
}/*while*/
return 0;
}/*InOrderTraverse*/
(1)
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数print(BinTreeNode*t;DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag,Top是栈顶指针。
【函数】
void print(BinTreeNode*t;DateType &x){
stack ST;int i,top;top=0;∥置空栈
while(t!=NULL &&t->data!=x‖top!=0)
{while(t!=NULL && t->data!=x)
{
∥寻找值为x的结点
(1) ;
ST[top].ptr=t;
ST[top].tag=0;
(2) ;
}
if(t!=Null && t->data==x){∥找到值为x的结点
for(i=1; (3) ;i++)
printf("%d",ST[top].ptr->data);}
else{
while( (4) )
top--;
if(top>0)
{
ST[top].tag=1;
(5) ;
}
}
}
设一棵二叉树的扩展后序遍历序列为,则这棵二叉树的前序和中序遍历序列分别为( )。
A、ABCDEFG 和 DECBGFA
B、ABCDEFG 和 BDCEAG
C、AFGBDEC和 CBEDAFG
D、ABCDEFG 和 CBEDAFG
A、n (n>2) 个结点的二叉树中至少有一个度为 2 的结点。
B、任何一棵完全二叉树中,叶子结点或者和分支结点一样多,或者只比分支结点多一个。
C、二叉树就是度为 2 的树。
D、完全二叉树最适合采用顺序存储结构。
E、满二叉树中的所有棵子树都是完全二叉树。
F、完全二叉树中,若某个结点无左孩子,则其必为叶子。
G、在叶子数目和权值均相同的所有二叉树中,最优二叉树一定是完全二叉树。
A、树和二叉树是两种不同的树形结构。
B、树中元素之间是多对多的关系。
C、一棵有 n 个结点的树中,无论其度是多少,分支数必定为 n-1。
D、对一棵树进行先根遍历和后根遍历时,其叶子结点出现的相对次序都是相同的。
E、一棵树上的任一结点要么是叶子,要么是内部结点。
F、在一棵树的先根遍历序列中,若结点 u 出现在结点 v 之前,则 u 必定是 v 的祖先。
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!