数据结构-----二叉树遍历 利用堆栈的非递归算法

中序遍历非递归遍历算法

void InOrderTraversal(BinTree BT) { BinTree T=BT; Stack S = CreatStack(Maxsize); while(T || !isempty(s)) { while(T) { push(S,T); T=T->Left; } if(!isempty(s)) { T=Pop(s); printf("]",T->Data); T=T->Right; } } }

先序遍历的非递归遍历算法

void InOrderTraversal(BinTree BT) { BinTree T=BT; Stack S = CreatStack(Maxsize); while(T || !isempty(s)) { while(T) { printf("]",T->Data); push(S,T); T=T->Left; } if(!isempty(s)) { T=Pop(s); T=T->Right; } } }

后序遍历的非递归遍历算法

`` void PostOrderTraversal(BinTree BT) {

BinTree T = BT, PrePop = NULL; //PrePop记录上一个Pop出来的结点 Stack S = CreatStack(MaxSize); while (T || !IsEmpty(S)) { while (T) { //一直向左将结点压入堆栈 Push(S, T); T = T->Left; } //将Pop的过程改为循环 while (!IsEmpty(S)) { //后序遍历有两种情况可以Pop该结点 T = Pop(S); if (T->Right == PrePop || T->Right == NULL) { //该结点的右结点为空或者上一次Pop的是该结点的右结点 printf("d", T->Data); PrePop = T; } else { //若不满足以上两种情况 说明该节点右侧节点还未被Pop Push(S, T); //则将该结点重新压回堆栈 T = T->Right; //然后指向该结点的右节点 break; //退出Pop循环 } } }

}