数据结构 创建二叉树

建立二叉树的存储结构（二叉链表）不同的定义方法相应有不同的存储结构的建立算法以字符串的形式“根左子树右子树”定义一棵二叉树按层次输入边建二叉树按给定的表达式建相应的表达式二叉树由二叉树的先序和中序序列建二叉树以字符串的形式“根左子树右子树”定义一棵二叉树（递归算法）例如:以字符串#表示ABCDAB#C##D##空树只含一个根结点的二叉树A以字符串A##表示以下列字符串表示右子树左子树intCreateBiTree(BiTree&T){scanf(&ch);if(ch=='#')T=NULL;else{if(!(T=newBiTNode))exit(0);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}return1;}//CreateBiTreeABCDABCD上页算法执行过程举例如下:ATBCD^^^^^scanf(&ch);if(ch==‘#')T=NULL;else{if(!(T=newBiTNode))exit(0);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}表示#abcdefg^^^^^^^^按字符串输入：abc##d##e#fg###写出递归调用过程读入边的非递归算法按从上到下、从左到右的顺序依次输入二叉树的边(区分左右分支)。即读入(father,child,lrflag)为一条边的信息，建立二叉树的二叉链表。需要一个队列保存已建好的结点的指针。(双亲结点指针)AFBCGED算法核心：每读一条边之后，生成孩子结点，并做为叶子结点；之后将该结点的指针保存在队列中。从队头找该结点的双亲结点指针，按lrflag值建立双亲结点的左右孩子关系。(‘#’,‘A’,0)(‘A’,‘B’,0)(‘B’,‘C’,1)(‘C’,‘D’,0)(‘C’,‘E’,1)(‘D’,‘F’,0)(‘D’,‘G’,1)(‘F’,‘#’,0)^B^^C^^E^(‘#’,‘A’,0)(‘A’,‘B’,0)(‘B’,‘C’,1)(‘C’,‘D’,0)(‘C’,‘E’,1)^D^(‘D’,‘F’,0)(‘D’,‘G’,1)(‘F’,‘#’,0)^G^^F^ABCDEGFAFBCGED队列中保存已建好的(孩子)结点的指针读入方式：T=NULLT^A^voidCreat_BiTree(BiTree&T){InitQueue(Q)；T=NULL；scanf(fa,ch,lrflag)；while(ch!=’#’){p=newBiTNode；p-data=ch；//创建孩子结点p-lchild=p-rchild=NULL；//做成叶子结点enqueue(Q，p)；//指针入队列if(fa==#)T=p;//所建为根结点else{}//非根结点的情况scanf(fa,ch,lrflag)；}//end_while}//Create_BiTrees=GetHead(Q)；//取队列头元素(指针值)while(s-data!=fa){dequeue(Q)；//出队列s=GetHead(Q)；}//在队列中找到双亲结点if(lrflag==0)s-lchild=p；//链接左孩子结点elses-rchild=p；//链接右孩子结点按给定的表达式建相应二叉树由原表达式建树例如：已知表达式(a+b)×c–d/e将表达式存成二叉树，二叉树的前序序列是前缀表达式，中序序列是中缀表达式,后序序列就是后缀表达式。分析原表达式和二叉树的关系:×a+b(a+b)×c–d/ea+b×cabba×c+abc(a+b)×c/deabc×+++-运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e##1二叉树子树栈存放的是子树根的地址运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(2运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a1001003运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100+4运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b2002005+运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++3003006运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*7运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c4004008运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-9运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-d60060010运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-d600600/11运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-d600600/e70070012运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-d600600/e700700/80080013运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c400400*500500-d600600/e700700/800800-90014基本操作:scanf(&ch);if(In(ch,字母集)){建叶子结点;进子树栈;}elseif(In(ch,运算符集)){和栈顶运算符比较优先数;若当前的优先数“高”，则进字符栈;否则建子树;}voidCrtExptree(BiTree&T,charexp[]){InitStack(PND);Push(PND,#);InitStack(PTR);p=exp;ch=*p;while(GetTop(PND)!=#||ch!=#){if(!IN(ch,OP))CrtNode(T,ch);//建叶子结点并入PND栈else{}//见下一页if(ch!=#){p++;ch=*p;}}//whilePop(PTR,T);//将二叉树的根地址出栈}//CrtExptreeswitch(ch){……}switch(ch){//ch是运算符case(:Push(PND,ch);break;case):Pop(PND,c);while(c!=(){CrtSubtree(T,c);//建二叉树并入栈Pop(PND,c);}break;default:}//switch……（见下一页）while(Gettop(PND,c)&&(precede(c,ch))){//取栈顶的运算符建子树，再出栈CrtSubtree(T,c);Pop(PND,c);}if(ch!=#)Push(PND,ch);break;defult://ch不是括号的运算符建叶子结点的算法为：voidCrtNode(BiTree&T,charch){if(!(T=newBiTNode))exit(OVERFLOW);T-data=ch;T-lchild=T-rchild=NULL;Push(PTR,T);}建子树的算法为：voidCrtSubtree(BiTree&T,charc){if(!(T=newBiTNode))exit(0);T-data=c;Pop(PTR,rc);T-rchild=rc;Pop(PTR,lc);T-lchild=lc;Push(PTR,T);}由二叉树的先序和中序序列建二叉树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根voidCrtBT(BiTree&T,charpre[],charino[],intps,intis,intn){//pre[ps..ps+n-1]为二叉树的先序序列，n是序列字符个数//ino[is..is+n-1]为二叉树的中序序列，//ps是先序序列的第一个字符的位置，初值为0//is是中序序列的第一个字符的位置，初值为0if(n==0)T=NULL;else{//在中序序列中查询根，k为-1，没有找到，否则，k为根在中序序列中的位置k=Search(ino,pre[ps]);if(k==-1)T=NULL;else{}}}//CrtBT……根结点if(!(T=newBiTNode))exit(0);T-data=pre[ps];//建立根结点if(k==is)T-lchild=NULL;//没有左子树elseCrtBT(T-lchild,pre,ino,ps+1,is,k-is);if(k==is+n-1)T-rchild=NULL;//没有右子树elseCrtBT(T-rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);实验1二叉树的应用要求实现如下功能：1.创建二叉树（前序、层次、前中、后中）2.二叉树的递归遍历算法（前、中、后）3.二叉树的非递归遍历算法（前、中、后）4.二叉树的层次遍历算法5.二叉树的深度6.二叉树的叶子结点数7.二叉树的结点数实验2二叉树的应用要求实现如下功能：1.由原表达式创建表达式二叉树2.求表达式的后缀表达式3.求值