第六章树和二叉树.PPTx

《第六章树和二叉树.PPTx》由会员分享，可在线阅读，更多相关《第六章树和二叉树.PPTx（152页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.1 树的定义和基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 哈夫曼树及其应用 第六章 树和二叉树第1页/共152页6.1 树的类型定义第2页/共152页第六章 树6.1 树的定义树的定义定义定义定义：树定义：树(tree)是是n(n=0)个结点的个结点的有限集有限集T，其中：其中：n=0 则称为则称为空树空树。当当n0时，时，有且仅有一个特定的结点，称为有且仅有一个特定的结点，称为树的树的根根(root)当当n1时，时，其余结点可分为其余结点可分为m(m0)个互不个互不相交的相交的有限集有限集T1,T2,Tm，其中每一个其中每一个集合本身又是一棵集合本身又是一

2、棵树树，称为根的，称为根的子树子树(subtree)第3页/共152页A只有根结点的树ABCDEFGHIJKLM有子树的树根子树第4页/共152页数据对象 D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm，其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系 R：ADT Tree 基本操作：查找类；插入类;删除类；ADT Tree第5页/共152页基本术语基本术语结点结点(node)表示树中的表示树中的元素元素，包括，包括数据数据

3、元素及若干指向其子树的元素及若干指向其子树的分支分支结点的度结点的度(degree)结点拥有的结点拥有的子树数子树数叶子叶子(leaf)度为度为0的结点的结点孩子孩子(child)结点子树的根称为该结点的结点子树的根称为该结点的孩子孩子双亲双亲(parents)孩子结点的孩子结点的上层结点上层结点叫该结点的叫该结点的兄弟兄弟(sibling)同一双亲同一双亲的孩子的孩子树的度树的度一棵树中一棵树中最大最大的结点度数的结点度数结点的层次结点的层次(level)从根结点算起，从根结点算起，根为第一层根为第一层，它的孩子为第二层，它的孩子为第二层深度深度(depth)树中结点的树中结点的最大层次最大

4、层次数数森林森林(forest)m(m 0)棵棵互不相交互不相交的树的集合的树的集合第6页/共152页ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先结点F,G是结点A的子孙结点第7页/共152页任何一棵非空树是一个二元组 Tree=(root，F)其中：root 被称为根结点 F 被称为子树森林森林：是m(m0)棵互不相交的树的集合Ar

5、ootBCDEFGHIJMKLF第8页/共152页赵老根赵跃进赵小康赵改革赵开放赵解放赵抗美赵卫兵赵永红第9页/共152页 Root(T)/求树的根结点 查找类：Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T,Visit()/遍历第10页/共152页InitTree(&T)/初始化置空树 插入类：CreateTr

6、ee(&T,definition)/按定义构造树Assign(T,cur_e,value)/给当前结点赋值InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树第11页/共152页 ClearTree(&T)/将树清空 删除类：DestroyTree(&T)/销毁树的结构DeleteChild(&T,&p,i)/删除结点p的第i棵子树第12页/共152页ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根树的图示表示法树的图示表示法树的广义表表示法1、图示法2、广义表法树的几种表示法:第13页/共152页ABDCJIH

7、MEFGKL3、树的嵌套集合表示法第14页/共152页 ()有确定的根；()树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。树的基本分类：第15页/共152页对比树型结构和线性结构 的结构特点第16页/共152页线性结构 树型结构 (非线性结构)第一个数据元素 (无前驱)根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)第17页/共152页6.1 树的定义和基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 哈夫曼树及其应

8、用 第六章 树和二叉树第18页/共152页6.2 6.2 二叉树二叉树二叉树的定义二叉树的定义二叉树的性质二叉树的性质二叉树的存储结构二叉树的存储结构第19页/共152页6.2 6.2 二叉树二叉树二叉树的定义二叉树的定义定义：二叉树是定义：二叉树是n(n 0)个结点的有限集，它个结点的有限集，它或为或为空树空树(n=0)，或由一个根结点和两棵分别或由一个根结点和两棵分别称为称为左子树左子树和和右子树右子树的的互不相交的互不相交的二叉树构二叉树构成成。特点特点每个结点至多有二棵子树每个结点至多有二棵子树二叉树的子树有左、右之分，且其次序不二叉树的子树有左、右之分，且其次序不能任意颠倒能任意颠倒

9、基本形态基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空第20页/共152页 二叉树的主要基本操作：查 找 类插 入 类删 除 类第21页/共152页 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

10、();LevelOrderTraverse(T,Visit();查找类：第22页/共152页InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入类：第23页/共152页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删除类：第24页/共152页二叉树的性质二叉树的性质性质性质1：在二叉树的第：在二叉树的第i层上至多有层上至多有2i-1个节点个节点(i1)证明：用归纳法证明之 i=1时，只有一个根结点，是对的。假设对所

11、有j(1ji)命题成立，即第j层上至多有 个结点,那么，第i-1层至多有 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即 故命题得证第25页/共152页二叉树的性质二叉树的性质v性质2：深度为k的二叉树至多有 个结点(k1)证明：由性质1，可得深度为k 的二叉树最大结点数是第26页/共152页v性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支

12、总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1第27页/共152页几种特殊形式的二叉树几种特殊形式的二叉树满二叉树满二叉树定义：定义：l特点：每一层上的结点数都是最大结点数v完全二叉树l定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为l特点u叶子结点只可能在层次最大的两层上出现u对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1第28页/共152页123114589121367101415123114

13、5891267101234567123456第29页/共152页性质4：证明：假设深度为k，则根据性质2和完全二叉树的定义有 2 k-1-1n=2k-1或2 k-1=n2k 于是k-1=log2n1，则其则其双亲双亲是是 i/2 (2)如果如果2in，则结点则结点i无左孩子；如果无左孩子；如果2i n，则则其其左孩子是左孩子是2i (3)如果如果2i+1n，则结点则结点i无右孩子；如果无右孩子；如果2i+1 n，则其则其右孩子是右孩子是2i+1第31页/共152页 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1图6.11 完全二叉树中结点i和i+1(a)

14、i和i+1结点在同一层(b)i和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右好在结点之间的关系。第32页/共152页证明：证明：可以从可以从(2)(2)和和(3)(3)推出推出(1)(1)，先证明，先证明(2)(2)和和(3)(3)。科学归纳法：科学归纳法：对于对于i i1 1，其左孩子是结点，其左孩子是结点2 2，若，若2n2n，即不存，即不存在结点在结点2 2，此时，结点，此时，结点i i无孩子。结点无孩子。结点i i的右孩子是的右孩子是结点结点3 3，若结点，若结点3 3不存在，即不存在，即3n3n，此时结点，此时结点i i无右孩无右孩子。子。即即i=1,i=1,结论成

15、立。结论成立。对于对于i1i1，可分为两种情况：，可分为两种情况：(1)(1)设第设第j j层的层的第一个结点第一个结点的编号为的编号为i i，由二叉树，由二叉树的性质的性质2 2和定义知和定义知i i2 2j-1j-1 结点结点i i的左孩子的左孩子必定为的必定为的j j1 1层的第一个结点，层的第一个结点，其编号为其编号为2 2j j2222j-1j-12i2i。如果。如果2 2i inn，则无左孩子。，则无左孩子。结点结点i i右孩子右孩子必定为第必定为第j j1 1层的第二个结点，层的第二个结点，编号为编号为2i2i1 1。若。若2i+1n2i+1n，则无右孩子。，则无右孩子。第33页

16、/共152页 (2)(2)假设第假设第j j层上的某个结点编号为层上的某个结点编号为i i(2(2j-j-1 1=i=2=i=2j j-1),-1),且且2i2i1n11时，如果i为左孩子，即2(i/2)=i，则i/2是i的双亲；如果i为右孩子，i2p+1，i的双亲应为p，p(i1)/2=i/2.证毕。第34页/共152页二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示第35页/共152页#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTree b

17、t;一、二叉树的顺序存储表示第36页/共152页二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素放二叉树中的数据元素特点：特点：结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉浪费空间，适于存满二叉树和完全二叉树树 (比如深度为k的右单支树，需要2k-1个结点，有效结点为k)abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11第37页/共152页二、二叉树的链式存储表示1.二叉链表2三叉链表3双亲链

18、表4线索链表第38页/共152页ADEBCFrootlchild data rchild结点结构:1.二叉链表第39页/共152页链式存储结构链式存储结构二叉链表二叉链表typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;lchild data rchild ABCDEFG性质6：在n个结点的二叉链表中，有n+1个空指针域 AB C D E F G第40页/共152页ADEBCFroot2三叉链表parent lchild data rchild结点结构:第41页/共152页l

19、三叉链表typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild,*parent;BiTNode,*BiTree;lchild data parent rchildABCDEFG A B C D E F G第42页/共152页0123456 data parent结点结构:3双亲链表LRTagLRRRLABCDFE第43页/共152页 typedef struct BPTNode /结点结构 TElemType data;int *parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNo

20、de typedef struct BPTree/树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree第44页/共152页6.1 树的定义和基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 哈夫曼树及其应用 第六章 树和二叉树第45页/共152页遍历二叉树问题的提出先序遍历中序遍历后序遍历中序遍历的非递归算法遍历算法的应用举例线索二叉树何谓线索二叉树？线索链表的遍历算法如何建立线索链表6.3 遍历二叉树和线索二叉树第46页/共152页遍历二叉树是指按一定的规律对二叉树中的每个

21、结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出结点的信息或判定节点满足某些条件等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是树型结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。一、问题的提出（寻找某个结点）6.3 遍历二叉树和线索二叉树第47页/共152页 对对“二二叉叉树树”而而言言，可可以以有有三三条条搜搜索索路径：路径：1 1先上后下先上后下的按层次遍历；的按层次遍历；2 2先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历；3 3先右先右（子树）（

22、子树）后左后左（子树）的遍历。（子树）的遍历。第48页/共152页先左后右的遍历算法先左后右的遍历算法(左子树总是先于右子树左子树总是先于右子树)DLRLDR、LRD、DLRRDL、RLD、DRLv方法l先序(根)遍历：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树；l中序(根)遍历：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树；l后序(根)遍历：(1)后序遍历左子树;(2)后序遍历右子树；(3)访问根结点;l按层次遍历：从上到下、从左到右访问各结点第49页/共152页ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:第

23、50页/共152页ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:第51页/共152页ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:B第52页/共152页-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-cd/ef-+a*b-c d/e f第53页/共152页主程序Pre(T)返回返回返回返回ACBDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCv

24、isit(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D Cstatus PreOrderTraversal(BiTree T)if(T)visit(T-data);PreOrderTraversal(T-lchild);PreOrderTraversal(T-rchild);return OK;v算法：递归算法先序遍历:pre(T R);pre(T R);第54页/共152页status InOrderTraversal(BiTree T)if(T)InOrderTraversal(T-lch

25、ild);visit(T-data);InOrderTraversal(T-rchild);return OK;status PostOrderTraversal(BiTree T)if(T)PostOrderTraversal(T-lchild);PostOrderTraversal(T-rchild);visit(T-data);return OK;中序遍历:后序遍历:第55页/共152页l非递归算法(中序)ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)第56页/共152页p

26、ABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)第57页/共152页ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)第58页/共152页ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(

27、14)ABCDEFGi访问：C B E G D F Ap=NULL(15)思考：访问的第一个结点的特点 前序，后序栈的操 作 层次遍历？第59页/共152页四、中序遍历算法的非递归描述Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S);Push(S,T)/根指针进栈 while(!StackEmpt(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);/空指针退栈 if(!StackEmpty(S)Pop(S,p);if(!Visit(p-data)retur

28、n ERROR;Push(S,p-rchild);/if /while return OK;/InOrderTraverse第60页/共152页四、中序遍历算法的非递归描述BiTNode*GoFarLeft(BiTree T,Stack*S)/T为树根结点的指针 if(!T)return NULL;while(T-lchild)Push(S,T);T=T-lchild;return T;/得到树T最左叶子结点的指针第61页/共152页void InorderTree(BiTree T,void(*visit)(TelemType&e)Stack*S;BiTree t,p;p=T-lchild;

29、t=GoFarLeft(p,S);/找到最左下的结点 while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);else if(!StackEmpty(S)/栈不空时退栈 t=Pop(S);else t=NULL;/栈空表明遍历结束 /while /InorderTree 第62页/共152页说明：说明：由由一一棵棵给给定定的的二二叉叉树树可可以以获获得得三三种种遍遍历历序序列列，同同样样，也也可可以以由由这这些些遍遍历历序序列列来来重重新新构造二叉树。构造二叉树。单单用用一一个个遍遍历历序序列列是是无无法法构构造造二二叉叉树树的的，因

30、因为为无无法法从从遍遍历历序序列列中中区区分分二二叉叉树树的的左左、右子树。右子树。利用中序遍历序列，并结合先序遍历序列或后序遍历序列就能重新构造二叉树利用中序遍历序列，并结合先序遍历序列或后序遍历序列就能重新构造二叉树。第63页/共152页本章实验内容本章实验内容 编写一个程序，输入先序遍历序列和中序遍历序列编写一个程序，输入先序遍历序列和中序遍历序列，由先序遍历和中序遍历序，由先序遍历和中序遍历序列列构造出一棵二叉树构造出一棵二叉树，然后用，然后用后序遍历后序遍历输出该二叉树。输出该二叉树。第64页/共152页先序遍历序列和中序遍历序列的结点分布特点：先序遍历序列和中序遍历序列的结点分布特

31、点：先序遍历序列：先序遍历序列：中序遍历序列：中序遍历序列：第65页/共152页二叉树的构造步骤：二叉树的构造步骤：1 1）从从先先序序遍遍历历序序列列中中取取出出第第一一个个结结点点，该该结结点点一一定定是是二二叉叉树树的的根根。然然后后在在中中序序遍遍历历序序列列中中找找到到根根结结点点，根根结结点点前前面面的的结结点点序序列列就就是是左左子子树树的的中中序序遍遍历历序序列列，根根结结点点后后面面的的结结点序列就是点序列就是右子树右子树的中序遍历序列。的中序遍历序列。2 2）对根的左子树先序遍历序列和中序遍历序列及右子树的先序遍历序列和中序遍历序）对根的左子树先序遍历序列和中序遍历序列及右

32、子树的先序遍历序列和中序遍历序列，再列，再执行第一步执行第一步，直到得出所有叶子结点为止。，直到得出所有叶子结点为止。第66页/共152页a b c d e f gc b d a e g f例如:aab bccddeeffggabcdefg先序序列中序序列第67页/共152页main()输入先序序列输入先序序列=preod 输入中序序列输入中序序列=inod PreInOd(preod,1,n,inod,1,n,&root);void PreInOd(char preod,int i,int j,char inod,int k,int h,BiTree*t)申请结点空间申请结点空间=t;t-d

33、ata=preodi;查找查找t-data在在inod中的位置中的位置=m if(m=k)t-lchild=Null;else PreInOd(preod,i+1,i+m-k,inod,k,m-1,&(t-lchild);/递归建立左子树递归建立左子树 if(m=h)t-rchild=NULL;else PreInOd(preod,i+m-k+1,j inod,m+1,h&(t-rchild);第68页/共152页练习练习如图所示二叉树的中序遍历序列是（如图所示二叉树的中序遍历序列是（）。）。A AabcdgefabcdgefB Bdfebagcdfebagc C Cdbaefcgdbaefc

34、g D Ddefbagcdefbagc第69页/共152页练习练习1)已知一棵二叉树的先根序列为已知一棵二叉树的先根序列为ABDGCFK，中根序列为，中根序列为DGBAFCK，则结点，则结点的后根序列为（的后根序列为（）。）。AACFKDBGBGDBFKCA CKCFAGDBDABCDFKG 2)已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。AacbedBdecab CdeabcDcedba第70页/共152页利用中序遍历序列，并结合先序遍历序列或后序遍历序列重新构造二叉树。利用中序遍历序列，并结合先序遍历序列或后序遍历序列重新构造二叉树。例一例一

35、先序：先序：ABCDEFGHIJ 中序：中序：CBDEAFHIGJ 例二例二 中序：中序：ABCDJEFHGI 后序：后序：BCJDAHIGFE 练习练习第71页/共152页五、遍历算法的应用举例2、统计二叉树中叶子结点的个数(先序遍历)3、求二叉树的深度(后序遍历)1、按先序遍历序列建立二叉树的二叉链表第72页/共152页 以字符串的形式 根 左子树 右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树只含一个根结点的二叉树A以字符串“A ”表示以下列字符串表示第73页/共152页遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：A B C D

36、E G F ABCDEFG A B C D E F G status CreateBitree(BiTree&T)scanf(&ch);if(ch=|ch=n)T=NULL;else if(!(T=(BiTnode*)malloc(sizeof(BiTnode)exit(overflow);T-data=ch;CreateBitree(T-lchild);CreateBitree(T-rchild);return OK;第74页/共152页A B C D A BCD上页算法执行过程举例如下：ATBCD第75页/共152页2、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树

37、，在遍历过程中查找叶子结点，并计数。需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。第76页/共152页void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf第77页/共152页统计二叉树中叶子结点个数算法ABCDEFGint BitreeLeafCount(BiTree T)if(T=NULL)return 0;

38、else if(T-lchild=NULL&T-rchild=NULL)return 1;else return BitreeLeafCount(T-lchild)+BitreeLeafCount(T-rchild);第78页/共152页ABCDEFGl统计二叉树中结点个数算法int BitreeCount(BiTree T)if(T=NULL)return 0;else return BitreeCount(T-lchild)+BitreeCount(T-rchild)+1;第79页/共152页l求二叉树深度算法int BitreeDepth(BiTree T)if(T=NULL)depth

39、=0;else ldepth=BitreeDepth(T-lchild);rdepth=BitreeDepth(T-rchild);depth=1+(ldepthrdepth?ldepth:rdepth);return depth;ABCDEFG第80页/共152页线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？第81页/共152页一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:A B C D E F G H K中序序列:B D C A H G K F E后序序列:

40、D C B H K G F E A第82页/共152页指向该线性序列中的“前驱”和 “后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”A B C D E F G H K D C B E 第83页/共152页对线索链表中结点的约定：在二叉链表的结点中增加两个标志域：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”.lchild Ltag data Rtag rchild 第84页/共152页若该结点的右子树不空，则rch

41、ild域的指针指向其右子树，且右标志域的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。如此定义的二叉树的存储结构称作“线索链表”。第85页/共152页typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1:线索 l

42、child Ltag data Rtag rchild 第86页/共152页ABCDE A B D C ET00001111 11typedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;PointTag Ltag,Rtag;BiThrNode,*BiThrTree;lchild Ltag data Rtag rchild 结点定义：Typedef enum PointerTag Link,Thread;先序序列：ABCDE先序线索二叉树第87页/共152页ABCDE A B D C ET000011111

43、1中序序列：BCAED中序线索二叉树第88页/共152页ABCDE A B D C ET0000111111后序序列：CBEDA后序线索二叉树第89页/共152页二、线索链表的遍历算法 for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。第90页/共152页例如:对中序线索化链表的遍历算法 中序遍历的第一个结点？在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。第91页/共152页v

44、oid InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/第一个结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 /InOrderTraverse_Thr第92页/共152页在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍

45、历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三、如何建立线索链表？第93页/共152页void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThreading(p-rchild);/右子树线索化 /if/

46、InThreading第94页/共152页Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/添加头结点 return OK;/InOrderThreading 第95页/共152页if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T

47、);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;第96页/共152页6.1 树的定义和基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 哈夫曼树及其应用 第六章 树和二叉树第97页/共152页6.4 树和森林树和森林树的存储结构树的存储结构 森林与二叉树的转换森林与二叉树的转换 树和森林的遍历树和森林的遍历第98页/共152页树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法第99页/共152页ABCDEFG0 A -11 B 02 C 03 D 04 E 2

48、 5 F 26 G 5r=0n=6data parent一、双亲表示法第100页/共152页 typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构:C语言的类型描述:typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构:第101页/共152页abcdefhgi6012345789acdefghibdata fc 2 3 4 5 9 7 8 6如何找双亲结点l孩子链

49、表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表二、孩子链表表示法第102页/共152页l带双亲的孩子链表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi第103页/共152页typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子结点结构:child nextC语言的类型描述:typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;双亲结点结构 data

50、 firstchild第104页/共152页typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构:第105页/共152页三、孩子兄弟表示法三、孩子兄弟表示法(二叉树表示法二叉树表示法)实现：用二叉链表作树的存储结构，链表中每实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其个结点的两个指针域分别指向其第一个孩子结第一个孩子结点点和和下一个兄弟结点下一个兄弟结点特点特点操作容易操作容易破坏了树的层次破坏了树的层次typedef struct CSNode ElemType data;struc