CH6-树和二叉树-数据结构()课件.ppt

《CH6-树和二叉树-数据结构()课件.ppt》由会员分享，可在线阅读，更多相关《CH6-树和二叉树-数据结构()课件.ppt（174页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.1 树的类型定义和基本术语树的类型定义和基本术语6.2 二叉树二叉树6.3 二叉树的遍历和线索二叉树二叉树的遍历和线索二叉树6.4 树和森林树和森林6.6 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码6.1 树的类型定义和基本术语树的类型定义和基本术语l l树的定义定义：树定义：树(Tree)(Tree)是是n(nn(n0)0)个结点的有限集个结点的有限集T T，其中：其中：当当n n1 1时，有且仅有一个特定的结点，称为树的时，有且仅有一个特定的结点，称为树的根根(Root)(Root)，当当n 1n 1时，其余结点可分为时，其余结点可分为m(m0)m(m0)个个互不相交互不相交互不相交互不

2、相交的有限集的有限集T T1 1,T,T2 2,T Tm m，其其中每一个集合本身又是一棵树，称为根的中每一个集合本身又是一棵树，称为根的子树子树(SubTree)SubTree)。特点：特点：树中各子树是互不相交的集合。树中各子树是互不相交的集合。树是一类重要的非线性数据结构，是以分支关系定义树是一类重要的非线性数据结构，是以分支关系定义的层次结构。的层次结构。ABCDEFGHIJMKLA()T1T3T2树根B(E,F(K,L),C(G),D(H,I,J(M)数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。(1)在在D中存在唯一的称为根的数据元素中存在

3、唯一的称为根的数据元素root,(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm,其中每一其中每一 个子集本身又是一棵树个子集本身又是一棵树,称为根称为根root的子树。的子树。数据关系数据关系 R：ADT Tree 若若D为空集，则称为空树；为空集，则称为空树；否则否则:ADT Tree 基本操作基本操作 P：基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类InitTree(&T)/初始化构造空树初始化构造空树 插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树A

4、ssign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空 删除类：删除类：DestroyTree(&T)/销毁树结构销毁树结构DeleteChild(&T,&p,i)/删除删除T中结点中结点p的第的第i棵子树棵子树一、树形表示法一、树形表示法一、树形表示法一、树形表示法一、树形表示法一、树形表示法二、凹入表示法二、凹入表示法二、凹入表示法二、凹入表示法二、凹入表示法二、凹入表示法三、嵌套集合表示法三、嵌套集合表示法三、嵌

5、套集合表示法三、嵌套集合表示法三、嵌套集合表示法三、嵌套集合表示法四、广义表表示法四、广义表表示法四、广义表表示法四、广义表表示法四、广义表表示法四、广义表表示法ABCDFEGHIJMKLA AAB BBE EEK KKL LLF FFC CCG GGD DDH HHMMMI IIJ JJGGF FKK L LI IJ JMMHHAAB BDDCCE E(A(A(A(B(E(K,L),F)B(E(K,L),F)B(E(K,L),F),C(G)C(G)C(G),D(H(M),I,J)D(H(M),I,J)D(H(M),I,J)(树根树根(子树子树1 1，子树子树2 2，子树子树n n)基基 本本

6、 术术 语语结结 点点:结点的度结点的度:树树 的的 度度:叶子结点叶子结点:分支结点分支结点:一个数据元素一个数据元素+若干指向子树的分支。若干指向子树的分支。分支的个数。分支的个数。(结点拥有子树数目结点拥有子树数目结点拥有子树数目结点拥有子树数目)树中所有结点的度的最大值。树中所有结点的度的最大值。度为零的结点。度为零的结点。度大于零的结点。度大于零的结点。DHIJM（终端结点）（终端结点）（终端结点）（终端结点）（非终端结点）（非终端结点）（非终端结点）（非终端结点）任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点，F 被称为子树森林。森林：森林：是m

7、（m0）棵互不相交的树的集合。ArootBEFKLCGDHIJMF子树之间不存在确定的次序关系（能互换能互换）。子树之间存在确定的次序关系（不能互换不能互换）。有序树：有序树：()有确定的根；()树根和子树根之间为有向关系。有向树：有向树：无序无序树：树：DHIJMDIHJM=双亲在同一层的结点双亲在同一层的结点ABCDEFGHIJKLM结点结点 A的度：的度：结点结点 B的度：的度：结点结点M的度：的度：叶子：叶子：结点结点A的孩子：的孩子：结点结点B的孩子：的孩子：结点结点I的双亲：的双亲：结点结点L的双亲：的双亲：结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：结

8、点结点A的层次：的层次：结点结点M的层次：的层次：树的深度：树的深度：结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先结点结点B的子孙：的子孙：320B，C，D E，F3K，L，F，G，M，I，JD E14例例例例E，K，L，F4 4线性结构线性结构树形结构树形结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个后继一个前驱、一个后继)其它数据元素其它数据元素(一个前驱、多个后继一个前驱、多个后继)6.2 二叉树二

9、叉树二叉树的五种基本形态：空树空树只含根结点只含根结点LR右子树为空树右子树为空树左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树二叉树特点：l每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2的结点的结点)。l二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树的子树有左、右之分，其次序不能任意颠倒。NNNLRN思考：二叉树与树的区别？二叉树与无序树的区别二叉树与无序树的区别二叉树与有序树的区别二叉树与有序树的区别二叉树就是度为二叉树就是度为2 2的有序树吗？的有序树吗？所以，二叉树不是前面定义的树的特殊形式，而是另外一种数据结构。否否练习：具有3个结点

10、的二叉树有多少种？Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit()/先序遍历先序遍历;InOrderTraverse(T,Visit()/中序遍历中序遍历;PostOrderTraverse(T,Visit()/后序遍历后序遍历;LevelOrderTraverse(T,Visit()/层序遍历层序遍历;InitBiTree(&T);Ass

11、ign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c)/根据根据LR为为0或或1，插入，插入 c为为T中中p所指结点的左或右子树。所指结点的左或右子树。p所指结点的原右或左子树成为所指结点的原右或左子树成为c的右子树。的右子树。二叉树二叉树的重要特性的重要特性 性质性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点，2i-1=20=1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两

12、棵子树，则第 i 层的结点数=2i-2 2=2i-1。性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点.(k1)证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1 性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1 由此，由此，n1+2n2=n0+n1+n2-1 即即 n0=n2+1两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1

13、个结点的二叉树。特点：每一层上的结点数都是最 大结点数.完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。特点:(1)叶子结点只可能在层次最底的两层上出现.(2)对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1.12345678910 11 12 13 14 15abcdefghij证明：证明：设设 完全二叉树的深度为 k 即 k-1 log2 n k 因为因为 k 只能是整数，因此，只能是整数，因此，k=log2n +1 性质性质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1则根据

14、性质2得 2k-1-1 n 2k-1 2k-1 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。二叉树的存储结构二叉树的存储结构二、二、二叉树的链式存储表示二叉树的链式存储表示一、一、二叉树的顺序存储表示二叉树的顺序存储表示二叉树的顺序存储结构中结点的存放次序是：对该树中每个二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号结点进行编号,其编号从小到大的顺序就是结点存放在连续存其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中储

15、单元的先后次序。若把二叉树存储到一维数组中,则该编号则该编号就是下标值加就是下标值加1(注意注意,C/C+语言中数组的起始下标为语言中数组的起始下标为0)。树。树中各结点的编号与等高度的完全二叉树中对应位置上结点的中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。编号相同。根据二叉树的性质根据二叉树的性质2，有，有k个结点的二叉树，需要长度为个结点的二叉树，需要长度为2k-1的一维数组的一维数组一、一、二叉树的顺序存储表示二叉树的顺序存储表示完全二叉树 一般二叉树的顺序表示 的顺序表示二叉树的顺序表示二叉树的顺序表示11 2 3 4 5 6 7 8 9 10 141 2 3 4 6

16、 7 8 9 12 1424891056731237648912510 1113实现：按满二叉树中结点的编号，依次存放二叉按满二叉树中结点的编号，依次存放二叉 树中的数据元素。树中的数据元素。特点：结点间关系蕴含在其存储位置中；结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树。浪费空间，适于存满二叉树和完全二叉树。极端情形极端情形:只有右单支的二叉树只有右单支的二叉树13715311371531二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2 2三叉链表三叉链表3 3线索链表线索链表typedef struct BiTNode /结点结构结点结构 T

17、ElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;C 语言的类型描述如下语言的类型描述如下:1.1.二叉链表二叉链表lchild data rchild结点结构结点结构:ADEBCF rootABDCFE在有在有在有在有n n个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有？个空指针域个空指针域个空指针域个空指针域n+1 typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lc

18、hild,*rchild,*parent;/左右孩子指针、双亲指针 TriTNode,*TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:2三叉链表三叉链表ADEBCF root ABDCFE练习：画出下面二叉树的三叉链表。练习：画出下面二叉树的三叉链表。abcdefgh6.3二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例五、遍历算法的应用举例 遍历遍历：顺

19、着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问均被访问一次一次，而且仅被访问一次仅被访问一次。即找一个完整即找一个完整而有规律的走法，得到树中所有结点的一个线性而有规律的走法，得到树中所有结点的一个线性排列。排列。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历如何遍历即按什么样的搜索搜索路径路径遍历的问题。对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三

20、条搜索路径：设设访问根结点访问根结点记作记作 D 遍历根的左子树遍历根的左子树记作记作 L 遍历根的右子树遍历根的右子树记作记作 R则可能的遍历次序有则可能的遍历次序有 前序前序 DLR 镜像镜像 DRL 中序中序 LDR 镜像镜像 RDL 后序后序 LRD 镜像镜像 RLDDLRLDR、LRD、DLRRDL、RLD、DRL 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。先先（根）（根）序的遍历算法：序的遍历算法：ADBCD L RAD L RD L RBDCD L

21、 R先序遍历序列：A B D C先序遍历先序遍历:若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。中中（根）（根）序的遍历算法：序的遍历算法：ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历中序遍历:若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。后后（根）（根）序的遍历算法：序的遍历算法：ADBC

22、 L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历后序遍历:BABCDEFGHK分 析：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A三、算法的递归描述三、算法的递归描述void PreOrder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树先序遍历二叉树 if(T)Visit(T-data);/访问结点访问结点 PreOrder(T-lchild,Visit);/遍历左子树遍历左子树 PreOrder(T

23、-rchild,Visit);/遍历右子树遍历右子树 例例 假假设设二二叉叉树树采采用用二二叉叉链链存存储储结结构构存存储储,试试设设计计一一个个算算法法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。解解：输输出出一一棵棵二二叉叉树树的的所所有有叶叶子子结结点点的的递递归归模模型型f()如如下：下：f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶子结点为叶子结点 f(b)：f(b-lchild);f(b-rchild)其他情况其他情况 void DispLeaf(BTNode*b)if(b!=NULL

24、)if(b-lchild=NULL&b-rchild=NULL)printf(%c,b-data);else DispLeaf(b-lchild);DispLeaf(b-rchild);void pre(BiTree t)if(t!=NULL)printf(%dt,t-data);pre(t-lchild);pre(t-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返

25、回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：先序序列：A B D CA B D C递归算法的执行过程递归算法的执行过程T Tabcde-+/如图二叉树表示表达式如图二叉树表示表达式如图二叉树表示表达式 :(a+b)(a+b)c d /ec d /e二叉树的先序遍历序列为：二叉树的先序遍历序列为：+a b c /d e+a b c /d e二叉树的中序遍历序列为：二叉树的中序遍历序列为：a +b a +b c d /ec d /e二叉树的后序遍历序列为：二叉树的后序遍历序列为：a b +c a b +c d e d e /前缀表达式

26、前缀表达式前缀表达式前缀表达式前缀表达式前缀表达式中缀表达式中缀表达式中缀表达式中缀表达式中缀表达式中缀表达式后缀表达式后缀表达式后缀表达式后缀表达式后缀表达式后缀表达式二叉树与表达式二叉树与表达式void InOrderTraverse(BiTree T,void(*visit)(TelemType&e)InitStack(S);p=T;while(p|!StackEmpty(S)/找到最左下的结点找到最左下的结点 if(p)Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子

27、树 Pop(S,p);if(!visit(p-data)return ERROR;p=p-rchild;/else /while return OK;/InOrderTraverse四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述 非递归算法的执行过程ABCDEFGpiA A(1)ABCDEFGpiA AB B(2)ABCDEFGpiA AB BC C(3)p=NULLp-Cp=NULLABCDEFGiA AB B访问：C(4)while(p|!StackEmpty(S)(p|!StackEmpty(S)/找到最左下的结点找到最左下的结点 if(p)Push(S,p);p=p-lchi

28、ld;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，访问根结点，根指针退栈，访问根结点，Pop(S,p);遍历左子树遍历左子树 if(!visit(p-data)return ERROR;p=p-rchild;/else /whilewhile(p|!StackEmpty(S)(p|!StackEmpty(S)/找到最左下的结点找到最左下的结点 if(p)Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，访问根结点，根指针退栈，访问根结点，Pop(S,p);遍历左子树遍历左子树 if(!visit(p-d

29、ata)return ERROR;p=p-rchild;/else /whilepABCDEFGiA A访问：C B(5)ABCDEFGiA AD D访问：C Bp(6)ABCDEFGiA AD DE E访问：C Bp(7)ABCDEFGiA AD D访问：C B Ep(8)p=NULLp=NULLp-Ep-E p-G p-GABCDEFGiA AD DGG访问：C B EP=NULLABCDEFGiA A访问：C B E G Dp(11)ABCDEFGiA AF F访问：C B E G Dp(12)ABCDEFGiA AD D访问：C B E Gpwhile(p|!StackEmpty(S)

30、(p|!StackEmpty(S)/找到最左下的结点找到最左下的结点 if(p)Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，访问根结点，根指针退栈，访问根结点，Pop(S,p);遍历左子树遍历左子树 if(!visit(p-data)return ERROR;p=p-rchild;/else /whileP=NULLP=NULLP=NULLP=NULLABCDEFGiA A访问：C B E G D Fp-Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D

31、F Ap=NULL(15)while(p|!StackEmpty(S)(p|!StackEmpty(S)/找到最左下的结点找到最左下的结点 if(p)Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，访问根结点，根指针退栈，访问根结点，Pop(S,p);遍历左子树遍历左子树 if(!visit(p-data)return ERROR;p=p-rchild;/else /whilevoid PreOrderTraverse(BiTree T,void(*visit)(TelemType&e)InitStack(S);p=T;whil

32、e(p|!StackEmpty(S)if(p)if(!visit(p-data)return ERROR;/访问根结点访问根结点 Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else /根指针退栈，遍历右子树根指针退栈，遍历右子树 Pop(S,p);p=p-rchild;/else /while return OK;/PreOrderTraverse非递归先序遍历二叉树非递归先序遍历二叉树五五、遍历算法的应用举例遍历算法的应用举例 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 3、求二叉树的深度、求二叉树的深度 4、建立二叉树的存储结

33、构建立二叉树的存储结构1、查询二叉树中某个结、查询二叉树中某个结 点点Status Preorder_Seek(BiTree T,ElemType x,BiTree&p)/若二叉树中存在和若二叉树中存在和x x相同的元素，则相同的元素，则p p指向该结点并返回指向该结点并返回true if(T)if(T-data=x)p=T;return OK,else if(Preorder_Seek(T-lchild,x,p)return OK;else return(Preorder_Seek(T-rchild,x,p);/else /if else return FALSE;2、统计二叉树中叶子结点的

34、个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增若是叶子，则计数器增1 1。void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf3、求二叉树的深度、求二叉

35、树的深度算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的深度应为二叉树的深度应为其左、右子树深度的最大值加其左、右子树深度的最大值加1 1。由此，需先分别需先分别求得左、右子树的深度，求得左、右子树的深度，算法中“访问结点访问结点”的操作为:求得左、右子树深度的最大值，然后加求得左、右子树深度的最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子树右子树深度深度之间的关系。int TreeDepth(BiTree T)/返回二叉树的深度 if(!T)depth=0;else depthLeft=TreeDepth(T-lchild);depthRight=Tree

36、Depth(T-rchild);depth=1+(depthLeft depthRight?depthLeft:depthRight);return depth;算法算法算法算法 4、建立二叉树的存储结构、建立二叉树的存储结构不同的定义方法对应不同的建立存储不同的定义方法对应不同的建立存储结构的算法结构的算法l 按先序遍历序列建二叉树按先序遍历序列建二叉树 l 按给定的表达式建二叉树按给定的表达式建二叉树l 由先序和中序序列建二叉树由先序和中序序列建二叉树 以先序遍历序列的形式以先序遍历序列的形式 根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树例如:ABCD以空白字符“”表示A(

37、B(,C(,),D(,)空树空树只含一个根结点的只含一个根结点的二叉树二叉树A以字符串“A ”表示以下列字符串表示A B C D 算法算法Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else if(!(T=new BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTreeA B C D A BCD上页算法执行过程举例如下:ATBCDA B C A

38、 B C D E D E G G F F 练习：按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCDEFG 按给定的表达式建相应二叉树按给定的表达式建相应二叉树 由前缀表示式建树由前缀表示式建树例如：已知表达式的前缀表示式 -+-+a b c/d e 由原表达式建树由原表达式建树例如：已知表达式(a+b)c d/e d/e对应前缀表达式 -+-+a b c/d e的二叉树的二叉树abcde-+/特点特点：操作数为叶子叶子结点，运算符为分支分支结点scanf(&ch);if(In(ch,字母集)建叶子结点;else 建根结点;递归建左子树;递归建右子树;由前缀表示式建树的算法的基本操作：

39、由前缀表示式建树的算法的基本操作：a+b(a+b)c d/e d/ea+bc 分析表达式和二叉树的关系分析表达式和二叉树的关系:ab+abc+abc+(a+b)cabcde-+/算法的算法的基本操作基本操作:scanf(&ch);if(In(ch,字母集)建叶子结点;入操作数栈;else if (In(ch,运算符集)和前一个运算符比较优先级;若当前的优先级“高”，则入运算符栈;否则建子树;PNDPNDS Svoid CrtExptree(BiTree&T,char exp)InitStack(S);Push(S,#);InitStack(PND);p=exp;ch=*p;while(!(Ge

40、tTop(S)=#&ch=#)if(!IN(ch,OP)CrtNode(t,ch);/非运算符非运算符,即字母即字母,建叶子结点并入栈建叶子结点并入栈PND else if(ch!=#)p+;ch=*p;/while Pop(PND,T);/CrtExptree switch(ch)case(:Push(S,ch);break;case):Pop(S,c);while(c!=()CrtSubtree(t,c);/建子树并入栈建子树并入栈PND Pop(S,c)break;defult:/switch while(!Gettop(S,c)&(precede(c,ch)CrtSubtree(t,c

41、);/建子树并入栈建子树并入栈PND Pop(S,c);if(ch!=#)Push(S,ch);break;/栈顶元素栈顶元素栈顶元素栈顶元素c c优先级优先级优先级优先级高于高于高于高于当前运算符当前运算符当前运算符当前运算符chch建叶子结点的算法为：void CrtNode(BiTree&T,char ch)if(!(T=new BiTNode)exit(OVERFLOW);T-data=char;T-lchild=T-rchild=NULL;Push(PND,T);建子树的算法为：void CrtSubtree(Bitree&T,char c)if(!(T=new BiTNode)ex

42、it(OVERFLOW);T-data=c;Pop(PND,rc);T-rchild=rc;Pop(PND,lc);T-lchild=lc;Push(PND,T);仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时也知二叉树的中序序列“cbdaegf”,则会如何？二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列线索二叉树线索二叉树 何谓线索二叉树？何谓线索二

43、叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。例如:先序序列:A B C D E F G H K中序序列:B D C A H G K F E后序序列:D C B H K G F E AABCDEFGHK若利用二叉链表存储二叉树，则含若利用二叉链表存储二叉树，则含n个个结点的二叉链表中有结点的二叉链表中有(n+1)个空指针域，个空指针域，利用这些指针域指向所在结点在某线性利用这些指针域指向所在结点在某线性序列中的序列中的“前驱前驱”或或“后继后继”，以便，以便 于某些操作。这些于

44、某些操作。这些 指针，称作指针，称作“线索线索”。与其相应的二叉树，称作与其相应的二叉树，称作“线索二叉树线索二叉树”包含包含“线索线索”的存储结构，称作的存储结构，称作“线索链表线索链表”A B C D E F G H K （先序序列）（先序序列）（先序序列）（先序序列）D C B E ABCDEFGHK对对线索链表线索链表中结点的约定：中结点的约定：在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，则则Lchild域的指针指向其左子树，域的指针指向其左子树，且左标志域的值为且左标志域的值为“指针指针 LinkLink”(0)(0)；否则，Lchild域的指

45、针指向其域的指针指向其“前驱前驱”，且左标志域的值为且左标志域的值为“线索线索 ThreadThread”(1)(1)。lchild 左标志左标志左标志左标志 data 右标志右标志右标志右标志 rchild若该结点的右子树不空，则则rchild域的指针指向其右子树，域的指针指向其右子树，且右标志域的值为且右标志域的值为 “指针指针 LinkLink”(0)(0)；否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志域的值为且右标志域的值为“线索线索 ThreadThread”(1)(1)。如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。typ

46、edef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;/左右指针左右指针 PointerTag LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerTag;/Link=0:指针，指针，Thread=1:线索线索二、线索链表的遍历算法二、线索链表的遍历算法:for(p=firstNode(T);p;p=Next(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简

47、化了遍 历的算法。rtagrightChild=0（右子女指针）=1（后继线索）=NULL无此情况无后继!=NULL后继为当前结点右子树的中序下的第一个结点后继为右子女结点寻找当前结点在中序序列下的后继寻找当前结点在中序序列下的后继 寻找当前结点在中序序列下的前驱寻找当前结点在中序序列下的前驱 ltag LeftChild=0（左子女指针）=1（前驱线索）=NULL无此情况无前驱!=NULL前驱为当前结点左子树中序下的最后一个结点前驱为左子女结点写出中序线索二叉树中找指针写出中序线索二叉树中找指针写出中序线索二叉树中找指针写出中序线索二叉树中找指针p p p p所指结点后继的算法。所指结点后继

48、的算法。所指结点后继的算法。所指结点后继的算法。BiThrNode*next(BiThrNode*p)BiThrNode*next(BiThrNode*p)if(p-rtag)return(p-rchild)if(p-rtag)return(p-rchild)/p-rtag/p-rtag/p-rtag/p-rtag为为为为1,1,1,1,表示线索表示线索表示线索表示线索,else else /右子树非空右子树非空右子树非空右子树非空 即右子树为空即右子树为空即右子树为空即右子树为空 q=p-rchild;q=p-rchild;/从从从从*p p p p的右孩子开始查找的右孩子开始查找的右孩子开

49、始查找的右孩子开始查找 while(!q-ltag)q=q-lchild;while(!q-ltag)q=q-lchild;/当当当当*q q q q不是不是不是不是 return(q);return(q);最左下结点时，继续查找最左下结点时，继续查找最左下结点时，继续查找最左下结点时，继续查找 /else/else 有右子树无右子树对新子树void InOrderTraverse_Thr(BiThrTree T,/中序遍历带头结点二叉线索树中序遍历带头结点二叉线索树中序遍历带头结点二叉线索树中序遍历带头结点二叉线索树T T的非递归算法的非递归算法的非递归算法的非递归算法void(*Visit

50、)(TElemType e)/T/T指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点指向根结点指向根结点指向根结点 p=T-lchild;/p/p指向根结点指向根结点指向根结点指向根结点 while(p!=T)/空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，p=Tp=T while(p-LTag=Link)p=p-lchild;/最左下的结点是中序遍历的最左下的结点是中序遍历的最左下的结点是中序遍历的最左下的结点是中序遍历的 Visit(p-data);/第第第第一个结点一个结点一个结点