后序遍历二叉树的非递归算法

1、后序遍历二叉树的非递归算法1 请根据用户输入的“扩展的先序遍历序列” （用小圆点表示空子树 ），建立以二叉链表方式 存储的二叉树， 然后写出后序遍历该二叉树的 非递归算法。方法一：#include#include#defineMAX_TREE_SIZE 100typedefstruct BiTNode chardata;structBiTNode * lchild;structBiTNode * rchild;BiTNode,*BiTree;/ 函数声明void Print(BiTree *root);void Selection( int sel,BiTree *root);void Rea

2、dExPreOrder(BiTree *root);void PrintExPreOrder(BiTree root);void PostOrderTraverse(BiTree T);/ 主函数 void main() / 初始化根结点BiTree root=NULL;Print(&root);while ( true ) printf( nPress enter to continue );getchar();getchar();system( cls );Print(&root);void Print(BiTree *root) / 提示int sel;);输入为扩展printf( 使用

3、说明 : 本程序可实现二叉链表方式存储的二叉树， 先序遍历序列 .n );printf(n);printf(1.输入扩展先序遍历序列并建立对应的二叉树 .nprintf(2.打印当前的二叉树的扩展先序遍历序列.n);printf(3.后序遍历当前的二叉树并打印遍历序列.n);printf(4.按其它任意键退出 .n );printf(n);printf( 请选择你要的操作 :);scanf( %d , &sel);getchar();Selection(sel, root);void Selection( int sel, BiTree *root) / 根据用户输入决定下一步骤switch

4、(sel) case 1: ReadExPreOrder(root);break ;case 2: PrintExPreOrder(*root);break ;case 3: PostOrderTraverse(*root);break ;default : exit(0);void ReadExPreOrder(BiTree *root)/ 先序遍历二叉树， root 为指向二叉树（或某一子树）根结点的指针char ch;ch = getchar();if (ch = . ) *root = NULL; else (*root) = (BiTree)malloc( sizeof (BiTNo

5、de); (*root)-data = ch;ReadExPreOrder(&(*root)-lchild);ReadExPreOrder(&(*root)-rchild);void PrintExPreOrder(BiTree root)char ch;if (root!=NULL) ch = root-data; printf( %c , ch); PrintExPreOrder(root-lchild); PrintExPreOrder(root-rchild); elseprintf( . );void PostOrderTraverse(BiTree T) BiTree stackM

6、AX_TREE_SIZE, p; int tagMAX_TREE_SIZE,top=0; p = T;while (p | top != 0) while (p) top+; stacktop=p; tagtop=0;p=p-lchild; / 从根开始，左结点依次入栈if (top 0) if (tagtop=1) / 表示是从该结点的右子树返回， 则访问该结 / 点 p=stacktop;printf( %c , p-data);top-;p=NULL; / 将p指向 NULL, 则下次进入 while 循环时，不做左子 / 树入栈操作else / 表明是从该结点左子树返回，应继续访问其右

7、子树 p=stacktop;if (top 0) p=p-rchild;tagtop=1; / 表明该结点的右子树已访问 /end of else /end of if /end of while方法二（顺序栈）： #include using namespace std; typedef struct node char ch;struct node *lchild; struct node *rchild;node;typedef struct binarytreenode *head; / 指向根结点bt;int n=0;void ini(bt * &b)b = new bt; b-he

8、ad=NULL;void precreate(node * &t)/ 先序递归建立二叉树coutc;if (c= . ) t=NULL; elsen+;t= new node; t-ch=c; precreate(t-lchild); precreate(t-rchild);/ 非递归算法需要栈 typedef struct stack node *base;node *top;int stacksize;stack;void ini(stack &s) s.base= new node *100 ; s.top=s.base; s.stacksize=100;void push(stack

9、&s,node *elem) (*s.top+)=elem;void pop(stack &s,node * &elem) elem= *(-s.top);int isempty(stack &s) if (s.base=s.top) return 1; else return 0;void gettop(stack &s,node *&t) t=*(s.top-1);/ 后序遍历非递归算法void afttraverse(node *t) stack s;ini(s);node * lastvist = NULL;while (NULL != t | !isempty(s) while (N

10、ULL != t) push(s,t); t = t-lchild;gettop(s,t);if (NULL = t-rchild | lastvist = t-rchild) cout ch;pop(s,lastvist);t = NULL;elset = t-rchild;int main() bt *b;ini(b);precreate(b-head); / 构造二叉树couthead); cout nn ;方法三(链栈)：#include #include typedef struct BiTNode char item;struct BiTNode *lchild,*rchild;B

11、iTNode,*Tree;typedef struct Stack Tree m;struct Stack *next;Stack,*st;Tree CreateTree()Tree B;char ch;ch=getchar();if (ch= . ) return NULL;else(BiTNode);B=(Tree)malloc( sizeof B-item=ch;B-lchild=CreateTree(); B-rchild=CreateTree();return B;void PostOrder(Tree T) Tree p,q;st s,top;int op;p=T;top=NULL

12、;dowhile (p!=NULL)s=(st)malloc( sizeof (Stack); / 使用链表形式存储栈 , 即/ 链栈s-m=p; s-next=top; top=s; p=p-lchild;op=1; / 该标志用于控制进入下面的 while 循环q=NULL;while (top!=NULL&op=1)if (top-m-rchild=q) / 若当前栈顶结点的右孩子是上次访问的结点，则打印该结点printf( %c ,top-m-item); / 第一次时打印最左下边结点q=top-m; /q 记录上次访问的结点top=top-next; / 栈指针后移 , 即将该结点从

13、栈中弹出else / 若当前栈顶结点的右孩子不是上次访问的结点 , 则先访问其右孩/ 子 p=top-m-rchild;op=0; /op 用来控制往右走一步后跳出当前 while 循环 , 进入下/ 一次外层的 while 循环 while (top!=NULL);int main()Tree T;printf( please enter the chars:n ); T=CreateTree();PostOrder(T);getchar();getchar();return 0;方法四：#include #include struct TREE / 二叉树结点结构char data;str

14、uct TREE *lsubtree;struct TREE *Rsubtree; ;struct TREE *tree;void createtree( struct TREE *&p) / 先序创建二叉树char ch;ch = getchar();if (ch = n )p = NULL;else if (ch = . ) p = NULL;elsep = ( struct TREE*)malloc( sizeof ( struct TREE); / 分配/ 结点空间10/ 递归创建左子树p-data = ch; createtree(p-lsubtree);createtree(p-R

15、subtree);/ 递归创建右子树void lastorder( struct TREE *tree)/ 非递归后序遍历struct TREE *p;struct TREE *s100; / 用一个指针数组来用作栈int top=-1; / 下标int mack100; / 标志数组p=tree;do while (p-lsubtree)!=NULL)&(macktop+1!=2)/ 直到让 p向左滑到最左子树，并且该结点非第二次入栈top=top+1;stop=p; / 每循环一次，当前结点入栈macktop=1; / 结点第一次入栈时，标志为 1 p=p-lsubtree; / 找最左子

16、树 / 叶子结点无须入栈printf( %cn ,p-data); / 输出末节点p=stop; / 出栈顶元素top=top-1; / 每出一个栈顶元素，下标就后退一位/ 循环if (macktop+1=1)/ 若结点是第一次出栈，则再入栈11top=top+1;stop=p;macktop=2; / 结点第二次入栈时，标志为 2p=p-Rsubtree; / 访问右子树 while (top!=-1); /top=-1 时，说明根结点刚访问完，跳出循环后 / 打印printf( %cn ,s0-data); / 最后把根输出int main() printf（ 请输入二叉树数据 n ）;c

17、reatetree(tree);printf( 后序遍历结果： n ); lastorder(tree);getchar();getchar();方法五：#include #include #define maxsize 50#define OK 1typedef struct Bnode / 声明二叉树的数据结构char ch;12struct Bnode *lchild,*rchild;bnode,*btree;typedef struct typebtree node;int flag;datatype,*pdatatype;typedef struct / 声明栈的数据结构dataty

18、pe datamaxsize;int top;seqstack,*pseqstack;return OK;btree creatbtree() / 创建二叉树int i=0;btree t;char c;c=getchar();if (c= # ) t=NULL;i+; elset=(btree)malloc( sizeof (bnode);t-data=c;i+;t-lchild=creatbtree();t-rchild=creatbtree();return t;int printelem( /*ElemType */ char e)printf( %c ,e);void postorder(btree t) / 二叉树的后序遍历 ( 非递归 ) / 与教材 p.131 的中序遍历方法类似pseqstack p;13 p=(pseqstack)malloc( sizeof (seqstack); p-top=0;while (t|!(p-top=0)if (t)p-datap-top.node = t;p-datap-top.flag = 0;(p-top)+;t=t-