资源描述：
《数据结构 创建二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、建立二叉树的存储结构 （二叉链表）不同的定义方法相应有不同的存储结构的建立算法以字符串的形式“根左子树右子树”定义一棵二叉树按层次输入边建二叉树按给定的表达式建相应的表达式二叉树由二叉树的先序和中序序列建二叉树以字符串的形式“根左子树右子树”定义一棵二叉树（递归算法）例如:以字符串#表示ABCDAB#C##D##空树只含一个根结点的二叉树A以字符串A##表示以下列字符串表示右子树左子树intCreateBiTree(BiTree&T){scanf(&ch);if(ch=='#')T=NULL;else{if(!(T=newBiT
2、Node))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
3、);}表示#abcdefg^^^^^^^^按字符串输入：abc##d##e#fg###写出递归调用过程读入边的非递归算法按从上到下、从左到右的顺序依次输入二叉树的边(区分左右分支)。即读入(father,child,lrflag)为一条边的信息，建立二叉树的二叉链表。需要一个队列保存已建好的结点的指针。(双亲结点指针)AFBCGED算法核心：每读一条边之后，生成孩子结点，并做为叶子结点；之后将该结点的指针保存在队列中。从队头找该结点的双亲结点指针，按lrflag值建立双亲结点的左右孩子关系。(‘#’,‘A’,0)(‘A’,‘B’
4、,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=NUL
5、L；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)；//出
6、队列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##
7、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)
8、*c-d/e#ch#(a100100b200200++300300*7运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#ch#(a100100b200200++300300*c4004008运算符栈二叉树子树栈由原表达式建树:(a+b)*c-d/e#c
