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

1、1 请根据用户输入的“扩展的先序遍历序列 (用小圆点表示空子树)，建立以二叉链表方式存储的二叉树，然后写出后序遍历该二叉树的非递归算法。方法一：#include <stdlib.h>#include <stdio.h>#define MAX_TREE_SIZE 100typedef struct BiTNode char data;struct BiTNode * lchild;struct BiTNode * rchild;BiTNode, *BiTree;/函数声明void Print(BiTree *root);void Selection(int sel,BiT

2、ree *root);void ReadExPreOrder(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(

3、BiTree *root) /提示int sel;printf("使用说明:本程序可实现二叉链表方式存储的二叉树，输入为扩展先序遍历序列.n");printf("-n");printf("1.输入扩展先序遍历序列并建立对应的二叉树.n");printf("2.打印当前的二叉树的扩展先序遍历序列.n");printf("3.后序遍历当前的二叉树并打印遍历序列.n");printf("4.按其它任意键退出.n");printf("-n");printf(&qu

4、ot;请选择你要的操作:");scanf("%d", &sel);getchar();Selection(sel, root);void Selection(int sel, BiTree *root) /根据用户输入决定下一步骤switch (sel) case 1: ReadExPreOrder(root); break;case 2: PrintExPreOrder(*root); break;case 3: PostOrderTraverse(*root); break;default: exit(0);void ReadExPreOrder(Bi

5、Tree *root) /先序遍历二叉树，root为指向二叉树或某一子树根结点的指针char ch;ch = getchar();if (ch = '.')*root = NULL;else (*root) = (BiTree)malloc(sizeof(BiTNode);(*root)->data = ch;ReadExPreOrder(&(*root)->lchild);ReadExPreOrder(&(*root)->rchild);void PrintExPreOrder(BiTree root)char ch;if (root!=NU

6、LL)ch = root->data;printf("%c", ch);PrintExPreOrder(root->lchild);PrintExPreOrder(root->rchild);elseprintf(".");void PostOrderTraverse(BiTree T) BiTree stackMAX_TREE_SIZE, p;int tagMAX_TREE_SIZE,top=0;p = T;while(p | top != 0)while(p) top+;stacktop=p;tagtop=0;p=p->lch

7、ild;/从根开始，左结点依次入栈if(top> 0) if(tagtop=1)/表示是从该结点的右子树返回，那么访问该结/点p=stacktop;printf("%c", p->data);top-;p=NULL;/将p指向NULL,那么下次进入while循环时，不做左子/树入栈操作else /说明是从该结点左子树返回，应继续访问其右子树p=stacktop;if(top> 0) p=p->rchild;tagtop=1; /说明该结点的右子树已访问 /end of else /end of if/end of while方法二顺序栈：#inclu

8、de<iostream>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->head=NULL;void precreate(node * &t)/先序递归建立二叉树cout<<"nn请输入结点数据，以'.'代表空:"

9、char c;cin>>c;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 &s,node *el

10、em) (*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) whil

11、e (NULL != t) push(s,t); t = t->lchild; gettop(s,t); if (NULL = t->rchild | lastvist = t->rchild) cout<<" "<<t->ch; pop(s,lastvist); t = NULL; else t = t->rchild;int main() bt *b;ini(b);precreate(b->head);/构造二叉树cout<<"nn后序遍历: "afttraverse(b->

12、;head);cout<<"nn"方法三链栈：#include<stdio.h>#include<stdlib.h>typedef struct BiTNode char item; struct BiTNode *lchild,*rchild;BiTNode,*Tree;typedef struct Stack Tree m; struct Stack *next;Stack,*st;Tree CreateTree()Tree B; char ch; ch=getchar(); if(ch='.') return NUL

13、L; else B=(Tree)malloc(sizeof(BiTNode); 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; dowhile(p!=NULL)s=(st)malloc(sizeof(Stack);/使用链表形式存储栈,即/链栈 s->m=p; s->next=top; top=s; p=p->lchild; op=1;/该

14、标志用于控制进入下面的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; /栈指针后移,即将该结点从栈中弹出 else/假设当前栈顶结点的右孩子不是上次访问的结点,那么先访问其右孩/子 p=top->m->rchild; op=0;/o

15、p用来控制往右走一步后跳出当前while循环,进入下/一次外层的while循环 while(top!=NULL);int main()Tree T; printf("please enter the chars:n"); T=CreateTree(); PostOrder(T);getchar();getchar(); return 0;方法四：#include <stdio.h> #include <stdlib.h> struct TREE /二叉树结点结构 char data; struct TREE *lsubtree; struct TRE

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

17、Rsubtree); /递归创立右子树 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;/结点第一次入栈时，标志为1p=p->lsubtr

18、ee;/找最左子树 /叶子结点无须入栈printf("%cn",p->data); /输出末节点p=stop;/出栈顶元素top=top-1;/每出一个栈顶元素，下标就后退一位if (macktop+1=1)/假设结点是第一次出栈，那么再入栈 top=top+1; stop=p; macktop=2;/结点第二次入栈时，标志为2p=p->Rsubtree;/访问右子树 while (top!=-1); /top=-1时，说明根结点刚访问完，跳出循环后/打印printf("%cn",s0->data);/最后把根输出int main()p

19、rintf("请输入二叉树数据n");createtree(tree);printf("后序遍历结果：n");lastorder(tree);getchar();getchar(); 方法五：#include<stdio.h> #include <stdlib.h>#define maxsize 50 #define OK 1typedef struct Bnode /声明二叉树的数据结构 char ch; struct Bnode *lchild,*rchild; bnode,*btree; typedef struct typ

20、e btree node; int flag; datatype,*pdatatype; typedef struct /声明栈的数据结构datatype datamaxsize;int top; seqstack,*pseqstack; btree creatbtree() /创立二叉树 int i=0; btree t;char c;c=getchar();if(c='#') t=NULL;i+; else t=(btree)malloc(sizeof(bnode); t->data=c;i+; t->lchild=creatbtree(); t->rchild=creatbtree(); return t;