請根據(jù)用戶輸入的擴展的先序遍歷序列

1、1 請根據(jù)用戶輸入的“擴展的先序遍歷序列” (用小圓點表示空子樹)，建立以二叉鏈表方式存儲的二叉樹，然后寫出后序遍歷該二叉樹的非遞歸算法。方法一：#include <stdlib.h>#include <stdio.h>#define MAX_TREE_SIZE 100typedef struct BiTNode char data;struct BiTNode * lchild;struct BiTNode * rchild;BiTNode, *BiTree;/函數(shù)聲明void Print(BiTree *root);void Selection(int sel,Bi

2、Tree *root);void ReadExPreOrder(BiTree *root);void PrintExPreOrder(BiTree root);void PostOrderTraverse(BiTree T);/主函數(shù)void main()BiTree root=NULL; /初始化根結(jié)點 Print(&root);while (true)printf("nPress enter to continue.");getchar();getchar();system("cls");Print(&root);void Print

3、(BiTree *root) /提示int sel;printf("使用說明:本程序可實現(xiàn)二叉鏈表方式存儲的二叉樹，輸入為擴展先序遍歷序列.n");printf("-n");printf("1.輸入擴展先序遍歷序列并建立對應(yīng)的二叉樹.n");printf("2.打印當(dāng)前的二叉樹的擴展先序遍歷序列.n");printf("3.后序遍歷當(dāng)前的二叉樹并打印遍歷序列.n");printf("4.按其它任意鍵退出.n");printf("-n");printf(&q

4、uot;請選擇你要的操作:");scanf("%d", &sel);getchar();Selection(sel, root);void Selection(int sel, BiTree *root) /根據(jù)用戶輸入決定下一步驟switch (sel) case 1: ReadExPreOrder(root); break;case 2: PrintExPreOrder(*root); break;case 3: PostOrderTraverse(*root); break;default: exit(0);void ReadExPreOrder(B

5、iTree *root) /先序遍歷二叉樹，root為指向二叉樹（或某一子樹）根結(jié)點的指針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!

6、=NULL)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->

7、lchild;/從根開始，左結(jié)點依次入棧if(top> 0) if(tagtop=1)/表示是從該結(jié)點的右子樹返回，則訪問該結(jié)/點p=stacktop;printf("%c", p->data);top-;p=NULL;/將p指向NULL,則下次進入while循環(huán)時，不做左子/樹入棧操作else /表明是從該結(jié)點左子樹返回，應(yīng)繼續(xù)訪問其右子樹p=stacktop;if(top> 0) p=p->rchild;tagtop=1; /表明該結(jié)點的右子樹已訪問 /end of else /end of if/end of while方法二（順序棧）：#in

8、clude<iostream>using namespace std;typedef struct node char ch;struct node *lchild;struct node *rchild;node;typedef struct binarytreenode *head;/指向根結(jié)點bt;int n=0;void ini(bt * &b)b =new bt;b->head=NULL;void precreate(node * &t)/先序遞歸建立二叉樹cout<<"nn請輸入結(jié)點數(shù)據(jù)，以'.'代表空:&qu

9、ot;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

10、*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) w

11、hile (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);/構(gòu)造二叉樹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='.') retur

13、n NULL; 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

14、=1;/該標(biāo)志用于控制進入下面的while循環(huán) q=NULL; while(top!=NULL&&op=1)if(top->m->rchild=q) /若當(dāng)前棧頂結(jié)點的右孩子是上次訪問的結(jié)點，則打印該結(jié)點 printf("%c",top->m->item);/第一次時打印最左下邊結(jié)點 q=top->m; /q記錄上次訪問的結(jié)點 top=top->next; /棧指針后移,即將該結(jié)點從棧中彈出 else/若當(dāng)前棧頂結(jié)點的右孩子不是上次訪問的結(jié)點,則先訪問其右孩/子 p=top->m->rchild; op=0;/

15、op用來控制往右走一步后跳出當(dāng)前while循環(huán),進入下/一次外層的while循環(huán) 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 /二叉樹結(jié)點結(jié)構(gòu) char data; struct TREE *lsubtree; struct TR

16、EE *Rsubtree; ; struct TREE *tree; void createtree(struct TREE *&p) /先序創(chuàng)建二叉樹 char ch;ch = getchar(); if (ch = 'n') p = NULL; else if(ch = '.') p = NULL; else p = (struct TREE*)malloc(sizeof(struct TREE);/分配/結(jié)點空間p->data = ch; createtree(p->lsubtree); /遞歸創(chuàng)建左子樹createtree(p->

17、;Rsubtree); /遞歸創(chuàng)建右子樹 void lastorder(struct TREE *tree)/非遞歸后序遍歷 struct TREE *p; struct TREE *s100;/用一個指針數(shù)組來用作棧int top=-1;/下標(biāo)int mack100;/標(biāo)志數(shù)組p=tree; do while(p->lsubtree)!=NULL)&&(macktop+1!=2)/循環(huán)/直到讓p向左滑到最左子樹，并且該結(jié)點非第二次入棧 top=top+1; stop=p;/每循環(huán)一次，當(dāng)前結(jié)點入棧macktop=1;/結(jié)點第一次入棧時，標(biāo)志為1p=p->lsubt

18、ree;/找最左子樹 /葉子結(jié)點無須入棧printf("%cn",p->data); /輸出末節(jié)點p=stop;/出棧頂元素top=top-1;/每出一個棧頂元素，下標(biāo)就后退一位if (macktop+1=1)/若結(jié)點是第一次出棧，則再入棧 top=top+1; stop=p; macktop=2;/結(jié)點第二次入棧時，標(biāo)志為2p=p->Rsubtree;/訪問右子樹 while (top!=-1); /top=-1時，說明根結(jié)點剛訪問完，跳出循環(huán)后/打印printf("%cn",s0->data);/最后把根輸出int main()pr

19、intf("請輸入二叉樹數(shù)據(jù)n");createtree(tree);printf("后序遍歷結(jié)果：n");lastorder(tree);getchar();getchar(); 方法五：#include<stdio.h> #include <stdlib.h>#define maxsize 50 #define OK 1typedef struct Bnode /聲明二叉樹的數(shù)據(jù)結(jié)構(gòu) char ch; struct Bnode *lchild,*rchild; bnode,*btree; typedef struct type

20、 btree node; int flag; datatype,*pdatatype; typedef struct /聲明棧的數(shù)據(jù)結(jié)構(gòu)datatype datamaxsize;int top; seqstack,*pseqstack; btree creatbtree() /創(chuàng)建二叉樹 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(); retu