《请根据用户输入的扩展的先序遍历序列》由会员分享，可在线阅读，更多相关《请根据用户输入的扩展的先序遍历序列（13页珍藏版）》请在金锄头文库上搜索。
1、1请根据用户输入的“扩展的先序遍历序列” （用小圆点表示空子树），建立以二叉链表方 式存储的二叉树，然后写出后序遍历该二叉树的非递归算法。方法一：#include #include #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,BiTree *root); void ReadExPreO
2、rder(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.输入扩展先序遍历序列并建立对应的二叉树.n);printf(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 (sel) case 1: ReadExPreOrde
4、r(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(BiTNode); (*root)-data = ch;ReadExPreOrder(
5、&(*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 stackMAX_TREE_SIZE, p; int tagMAX_TREE_SIZE,top
6、=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 /表明是从该结点左子树返回，应继续访问其右子树 p=stacktop;if(top 0)p=p-rchild;tagtop=1; / 表明该结点的右子树已访问 /en
7、d of else /end of if/end of while方法二(顺序栈)：#includeusing namespace std;typedef struct nodechar 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) /先序递归建立二叉树coutc;if(c=.) t=NULL;elsen+;t
8、=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 *elem) (*s.top+)=elem;void pop(stack &s,node * &elem)elem= *(-s.top);int ise
9、mpty(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 (NULL != t) push(s,t);t = t-lchild; gettop(s,t);if (NULL = t-rchild | lastvist = t-rchild)
10、 cout ch;pop(s,lastvist);t = NULL;elset = t-rchild;int main() bt *b;ini(b);precreate(b-head); /构造二叉树couthead); coutnn;方法三(链栈)：#include#include typedef struct BiTNode char item;struct BiTNode *lchild,*rchild; BiTNode,*Tree;typedef struct StackTree m;struct Stack *next;Stack,*st;Tree CreateTree()Tree
11、B; char ch;ch=getchar(); if(ch=.) return 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;do while(p!=NULL) s=(st)malloc(sizeof (Stack);/使用链表形式存储栈，即/链栈s-m=p;s-next=top;top=s;p=p-lchi
12、ld;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/栈指针后移，即将该结点从栈中弹出else/若当前栈顶结点的右孩子不是上次访问的结点，则先访问其右孩/子p=top-m-rchild;op=/op用来控制往右走一步后跳出当前while循环，进入下/一次外层的while循环while(top!=NULL
13、); int main()TreeT;printfplease enter the chars:n);T=CreateTree();PostOrder(T);getchar();getchar();return 0;方法四：#include #include struct TREE /二叉树结点结构char data;struct 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);/分配/ 结点空间p-data = ch;createtree(p-lsubtree); /递归创建左子树createtree(p-Rsubtree); /递
