二叉树的前序、中序、后序遍历的非递归算法及层次遍历算法

亦凉 2021-12-16 15:11 99阅读 0赞

二叉树的各种非递归遍历中，要数后序比较麻烦了，因为即使左子树为空，也不能马上出栈，而是要判断右子树。以下就给出代码：

typedef struct Tnode  
\{  
ElemType data;  
struct Tnode \*lchild,\*rchild;  
\}BBTnode,\*BBTree;

typedef struct  
\{  
BBTree \*base,\*top; //栈指针成员  
int initsize; //栈初始长度  
\}Stack;

//以下假设已经建好二叉树和栈了

status NonFirstView(BBTree T,Stack S) //非递归前序遍历  
\{  
while(S.base != S.top || T != NULL)  
\{  
while(T != NULL) //向左走到最左  
\{  
cout << T->data << " "; //输出元素  
\*S.top++ = T;  
T = T->lchild;  
\}  
T=\*--S.top; //出栈  
T = T->rchild; //转向右  
\}  
return OK;  
\}

status NonMiddleView(BBTree T,Stack S) //非递归中序遍历  
\{  
while(S.base != S.top || T != NULL)  
\{  
while(T != NULL) //向左走到最左  
\{  
\*S.top++ = T;  
T = T->lchild;  
\}  
T=\*--S.top; //出栈  
cout << T->data << " "; //输出元素  
T = T->rchild; //转向右  
\}  
return OK;  
\}

status NonLastView(BBTree T,Stack S)  
\{  
BBTree pre = NULL;  
while(S.base != S.top || T != NULL)  
\{  
while(T != NULL) //向左走到最左  
\{  
\*S.top++ = T;  
T = T->lchild;  
\}  
T=\*(S.top - 1); //取栈顶节点  
if(T->rchild == NULL || T->rchild == pre) //如果T没有右孩子或者其右孩子刚刚被访问过  
\{  
cout << T->data << " "; //输出元素  
S.top--;  
pre = T;  
T = NULL;  
\}  
else  
T = T->rchild; //转向右  
\}  
return OK;  
\}

status LevelView(BBTree T,Queue Q) //层次遍历  
\{  
if(T != NULL)  
\{  
\*Q.rear++ = T;  
while(Q.front != Q.rear) //队列不空时  
\{  
if(T->lchild != NULL) \*Q.rear++ = T->lchild; //左子树进队  
if(T->rchild != NULL) \*Q.rear++ = T->rchild; //右子树进队  
T = \*Q.front++; //出队  
cout << T->data << " ";  
T = \*Q.front; //最新的队头  
\}  
\}  
return OK;  
\}

转载于:https://www.cnblogs.com/arcfat/archive/2012/11/21/2780432.html