数据结构(C语言版)严蔚敏二叉树遍历操作二叉树的相关代码

篇首语：本文由编程笔记#小编为大家整理，主要介绍了数据结构(C语言版)严蔚敏---二叉树遍历操作二叉树的相关代码相关的知识，希望对你有一定的参考价值。

1. 二叉树的自下而上、从左到右的层次遍历算法

void LevelTraverse2(BiTree T)
BiTree Queue[100],Stack[100];
// 这里用数组代替队列和栈
int i&＃61;0,i1&＃61;0,j&＃61;0;
Queue[0] &＃61; T;
while(i1<&＃61;i)
T &＃61; Queue[i1&＃43;&＃43;];
Stack[j&＃43;&＃43;] &＃61; T;
if(T->left)
Queue[&＃43;&＃43;i] &＃61; T->left;
if(T->right)
Queue[&＃43;&＃43;i] &＃61; T->right;

while(j>0)
T &＃61; Stack[--j];
printf("%c",T->data);

printf("\\n");



【注意】代码中使用数组代替队列和栈。
运行结果如下&＃xff1a;

所表示的二叉树为&＃xff1a;

使用队列和栈的参考代码为&＃xff1a;

void LevelTraverse2(BiTree T)
Queue Q;
Stack S;
BiTree p;
// 定义队列和栈
//初始化队列和栈
if(T)
// 二叉树非空时
InitQueue(Q);
InitStack(S);
EnQueue(Q,T);
// 入队
while(!IsQueueEmpty(Q))
DeQueue(Q,p);
// 出队
Push(S,p);
// 入栈
if(p->lchild)
EnQueue(Q,p->lchild);
// 左孩子非空
if(p->rchild)
EnQueue(Q,p->rchild);

while(!IsStackEmpty(S))
Pop(S,p);
// 出栈
printf("%c",p->data);





思路为&＃xff1a;利用原有的层次遍历算法&＃xff08;从上至下、从左至右&＃xff09;&＃xff0c;出队的同时将各节点入栈&＃xff0c;在所有节点入栈后再从栈顶依次访问即可。

2.非递归算法求二叉树的高度

int BitDepth(BiTree T)
if(!T)
return 0;

// 如果二叉树为空
int f &＃61; 0,r &＃61; 0;
int level &＃61; 0,last &＃61; 1;
BiTree Queue[100];
Queue[r&＃43;&＃43;] &＃61; T;
BiTree p;
while(f<r)
p &＃61; Queue[f&＃43;&＃43;];
if(p->left)
Queue[r&＃43;&＃43;] &＃61; p->left;
if(p->right)
Queue[r&＃43;&＃43;] &＃61; p->right;
if(last &＃61;&＃61; f)
level&＃43;&＃43;;
last &＃61; r;


return level;



运行结果&＃xff08;所用的二叉树和上述一样&＃xff09;&＃xff1a;

思路&＃xff1a;采用层次遍历算法&＃xff0c;设置变量level记录当前节点所在的层次&＃xff0c;设置变量last指向当前层的最右节点&＃xff0c;每次层次遍历出队时与last指针比较&＃xff0c;若两者相同&＃xff0c;则层数加1&＃xff0c;并让last指向下一层的最右节点&＃xff0c;直到遍历完成。