数据结构树与二叉树.pptx

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

1、15.1 树的基本概念树的基本概念1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算第1页/共66页21.1.树的定义树的定义树的定义树的定义注1：树的定义具有递归性，即“树中还有树”。由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。第2页/共66页3树的表示法主要有5种：v图形表示法v嵌套集合表示法v广义表表示法v凹入表示法v左孩子右兄弟表示法第3页/共66页4图形表示法：图形表示法：教师学生其他人员2002级2003级2004级2005级

2、华科大武昌分校电信系计算机系自控系叶子根子树第4页/共66页5嵌套集合表示法嵌套集合表示法第5页/共66页6广义表表示法广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为由子树森林组成的表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域?第6页/共66页7凹入表示法凹入表示法(又称目录表示法又称目录表示法)第7页/共66页8左孩子右兄弟表示法A AB BC CD DE EF FGGH HI IJ JK KL LMM数据左孩子 右兄弟第8页/共66页92.若干术语若干术语即树的数据元素结点挂接的子树数结点结点的度结点的层

3、次终端结点分支结点树的度树的深度(或高度)从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为非终端结点）所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的度 ；树的深度1334（有几个直接后继就是几度，亦称“次数”）ABCGEIDHFJFLK第9页/共66页103.3.树的逻辑结构树的逻辑结构树的逻辑结构树的逻辑结构 一对多（1:n1:n），有多个直接后继（如家谱有多个直接后继（如家谱树、目录树等等），但只有一个根结点，树、目录树等等），但只有一个根结点，且且子树之间互不相交子树之间互不相交。4.4.

4、树的存储结构树的存储结构 讨论1：树是非线性结构，该怎样存储？特点：仍然有顺序存储、链式存储等方式。第10页/共66页115.2 5.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构（二叉树的运算见5.3节）第11页/共66页121.1.1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义定义：是n（n0）个结点的有

5、限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。问：具有问：具有3 3个结点的二叉树可能有几种不同形态？个结点的二叉树可能有几种不同形态？有有5 5种种基本形态：一般的树有几种？第12页/共66页132.2.2.2.二叉树的性质二叉树的性质二叉树的性质二叉树的性质 (3+2)(3+2)(3+2)(3+2)讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点（个结点

6、（i0i0）。）。性质2:深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点（个结点（k0k0）。）。再提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，最多有多少个结点？（利用二进制性质可轻松求出）2 2i-1i-1个个2 2k k-1-1个个第13页/共66页14讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）证明：证明：二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又又二叉树中全部

7、结点数nB+1(总分支数根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而而 总分支数B=n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)三式联立可得：三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1物理意义：叶子数物理意义：叶子数2 2度结点数度结点数1 1第14页/共66页152.深度为的二叉树的结点总数，最多为 个。)k-1 )log2k )k )k1.树中各结点的度的最大值称为树的 。)高度 )层次 )深度 )度DCC3.深度为9的二叉树中至少有 个结点。)9 )8 )91课堂练习：第15页/共66页16满二叉树：满二叉树：一棵深度为一棵深度为

8、k 且有且有2k-1个结点的二叉个结点的二叉树。树。（特点：每层都（特点：每层都“充满充满”了结点）了结点）完全二叉树：深度为k 的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是顺序二叉树的含义。而图论中的“完全二叉树”是指n1=0的情况。因为它们在顺序存储方式下可以复原！第16页/共66页17对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉满二叉树和完

9、全二叉树树）,还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为 loglog2 2n n 1 1性质性质5:5:对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i i 的结点的结点，其左孩子编号必为，其左孩子编号必为2i2i，其右孩子编号为，其右孩子编号为2i2i1 1；其双亲的编号必为；其双亲的编号必为i/2i/2（i i1 1 时为根时为根,除外）。除外）。证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面

10、编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2k-1-1n2k-1 或2k-1n2k三边同时取对数，于是有：k-1log2n1)f=n*fact(n-1);else f=1;return(f);用递归形式格外简单！回忆1：二叉树结点的数据类型定义：则三种遍历算法可写出:第26页/共66页27中根遍历算法中根遍历算法LDR(node*root)if(root!=NULL)LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);return(0);后根遍历算法后根遍历算法LRD(node*root)if(root!=NU

11、LL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);结点数据类型自定义结点数据类型自定义typedef struct nodeint data;struct node*lchild,*rchild；node;node*root;先根遍历算法先根遍历算法DLR(node*root)if(root!=NULL)/非空二叉树 printf(“%d”,root-data);/访问DDLR(root-lchild);/递归遍历左子树DLR(root-rchild);/递归遍历右子树 return(0);第27页/共6

12、6页28对遍历的分析：1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问，是先根遍历第2次经过时访问，是中根遍历第3次经过时访问，是后根遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)O(n)/每个结点只访问一次空间效率:O(n)O(n)/栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元第28页/共66页29用空格字符表示无孩子或指针为空注：要实现遍历运算，必须先把二叉树存入电脑

13、要实现遍历运算，必须先把二叉树存入电脑内内怎样建树？例：将下面的二叉树以二叉链表形式存入计算机内。A AB BGGD DF FC CE E考虑1：输入结点时怎样表示“无孩子”？考虑2：以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：A B C D E G F 以先序遍历最为合适，让每个结点都能及时被连接到位。第29页/共66页30建树算法：Status CreateBiTree(BiTree&T)/构造二叉树Tscanf(“%c”,&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(overflow);

14、T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree输入序列：A B C D E G F 第30页/共66页31问：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。所以，空指针数目2n(n-1)=n+1个。n+1n+1个个分析：用二叉链表存储包含n个结点的二

15、叉树，结点必有2n个链域（见二叉链表数据类型说明）。除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。线索二叉树线索二叉树第31页/共66页32思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。这就是线索二叉树（Threaded Binary Tree）第32页/共66页335.4 线索二叉树线索二叉树（Threaded Binary Tree）二叉树中容易找

16、到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。在此前提下，那n+1个空链域才可能装得下“线索”。讨论1：二叉树是1:2的非线性结构，其直接后继可能不止一个，如何存放？讨论2.如何获得这种“直接前驱”或“直接后继”？有何意义？第33页/共66页34 每个结点

17、增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？有两种解决方法：与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。规 定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。datalchildrchildfwdbwddatalchildrchild缺点：空间效率太低！问题：计算机如何判断是孩子指针还是线索指针？如何区别？第34页/共66页35lchildLTagdataRTag rchild约定:当Tag域为0时,表示正常情况;当T

18、ag域为1时,表示线索情况.前驱(后继)左(右)孩子为区别两种不同情况，特增加两个标志域：问：增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。各1bit第35页/共66页361.有关线索二叉树的几个术语：线索链表：线 索：线索二叉树：线 索 化：用含Tag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程yyy线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）第36页

19、/共66页37dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：带了带了两个标志两个标志的某的某先序遍历先序遍历结果如下表结果如下表所示，请画出对应的二叉树。所示，请画出对应的二叉树。A第37页/共66页38ABCGEIDHFroot悬空？NIL悬空？NIL解：对该二叉树中序遍历的结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：为避免悬空态，应增设一个头结点例1 1：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。2.线索二叉树的生成线索化线索化过程就是在遍历过程中修改空指针的过程第38

20、页/共66页3900A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：第39页/共66页40线索二叉树的生成算法线索二叉树的生成算法（递归算法见教材）递归算法见教材）实质：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。为了记下遍历过程中访问结点的先后次序，需要设置两个指针：p指针当前结点之指针；pre指针当前结点的前趋结点指针。设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为

21、空。每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法。若p-lchildNULL,则p-Ltag=1;p-lchildpre;/p的前驱线索应存p结点的左边若pre-rchildNULL,则pre-Rtag1;pre-rchild=p;/pre的后继线索应存pre结点的右边第40页/共66页413.3.线索二叉树的遍历线索二叉树的遍历（无需堆栈）（无需堆栈）对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。（因为建立线索时已遍历一次，相当于线性化了！）难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过

22、一定运算才能找到它的后继。以中根线索二叉树为例：当RTag=1时，直接后继指针就在其rchild域内；当RTag=0时，直接后继是当前结点右子树最左下方右子树最左下方的结点；请注意中序遍历规则是LDR，先左再先左再根根再再右右第41页/共66页425.55.5 树和森林树和森林1.树和森林的存储方式2.树和森林与二叉树的转换3.树和森林的遍历第42页/共66页431.1.树和森林的存储方式树和森林的存储方式树有三种常用存储方式：双亲表示法 孩子表示法 孩子兄弟表示法 1、用双亲表示法存储思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。paren

23、tdata结点结构dataparent1树结构 23n第43页/共66页44RABCDEFGHK-1000例例1:双亲表示法双亲表示法R RB BC CGGE EK KD DH HF FA A缺点：求结点的孩子时需要遍历整个结构1136668976543210第44页/共66页45思路：对n个结点分别设立n个孩子链表，结点为表头；再将n个表头用数组存放起来，形成一个混合结构。例如：abecdfhgdefghgfedcbah123456782 2、用孩子表示法存储、用孩子表示法存储bc第45页/共66页46思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指

24、针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3 3、用孩子、用孩子兄弟表示法存兄弟表示法存储储指向左孩子指向右兄弟第46页/共66页47abecdfhgbacedfgh问：树二叉树的“连线抹线旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。例如例如：第47页/共66页482.树和森林与二叉树的转换转换步骤：step1:将树中同一结点的兄弟相连;加线抹线旋转讨论1：树如何转为二叉树？孩子兄弟表示法step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。第48页/共66页49方法：加线抹线旋转

25、abeidfhgc树转二叉树举树转二叉树举例例：abeidfhgc兄弟相连长兄为父孩子靠左根结点肯定没根结点肯定没有右孩子！有右孩子！第49页/共66页50讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：逆操作，把所有右孩子变为兄弟！abdefhgic第50页/共66页51法一：各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？即F=T1,T2,Tm B=root,LB,RB法二：森林直接变兄弟，再转为二叉树（参见教材，两种方法都有转换示意图）法一和法二得到的二叉树是完全相同的、惟一的、第51页/共66页52ABCDEFGHJ

26、IABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：森林转二叉树举例：（采用法二）（采用法二）兄弟相连 长兄为父头树为根 孩子靠左A A第52页/共66页53A ABCDEFGHJI讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟 即B=root,LB,RB F=T1,T2,TmABCDEFGHJIEFABCDGHJI第53页/共66页545.65.6 Huffman Huffman树及其应树及其应用用一、Huffman树二、Huffman编码最优二叉树Huffman树Huffman编码带权路径长度最短的树不等长编码是通

27、信中最经典的压缩编码第54页/共66页55一、最优二叉树一、最优二叉树（HuffmanHuffman树）树）路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：Huffman树：由一结点到另一结点间的分支所构成。路径上的分支数目。从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积（WPL）若干术语：debacf g树中所有叶子结点的带权路径长度之和带权路径长度最小的树。ae的路径长度树长度210Huffman常译为赫夫曼、霍夫曼、哈夫曼等Weighted Path Length第55页/共66页56树的带权路径长度树的带权路径长度如何计算？如何计算？WPL=wklk

28、 k=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=WPL=WPL=Huffman树是WPL 最小的树树中所有叶子结点的带权路径长度之和364635第56页/共66页571.1.构造构造Huffman树的基本思想：树的基本思想：例：例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL12bit(7524）36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：明确：要实现Huff

29、man编码，就要先构造Huffman树讨论：Huffman树有什么用？权值大的结点用短路径，权值小的结点用长路径。WPL最小的树频度高的信息用短码，反之用长码，传输效率肯定高！信息高效传输WPL2=1bit72bit5+3bit(2+4)=35第57页/共66页582.2.构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：(1)(1)由给定的由给定的 n n 个权值个权值 w w1 1,w w2 2,w wn n 构成构成n n棵二叉树的集合棵二叉树的集合F F =T T1 1,T T2 2,T Tn n （即森林）（即森林），其中每棵二叉

30、树，其中每棵二叉树 T Ti i 中中只有只有一个带权为一个带权为 w wi i 的根结点，其左右子树均空。的根结点，其左右子树均空。(2)(2)在在F F 中选取中选取两棵根结点权值最小的树两棵根结点权值最小的树 做为左右子树构造一棵做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值新的二叉树，且让新二叉树根结点的权值等于等于其左右子树的其左右子树的根结点根结点权值之和权值之和。(3)(3)在在F F 中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入 F F中中。(4)(4)重复重复(2)(2)和和(3)(3),直到直到 F F 只含一棵树为止。这棵树便

31、是只含一棵树为止。这棵树便是HuffmanHuffman树。树。怎样证明它就是WPL最小的最优二叉树？参考信源编码第58页/共66页59step1：对权值进行合并、删除与替换对权值进行合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权具体操作步骤：具体操作步骤：a.初始方框表示外结点（叶子，字符）圆框表示内结点（合并后的权值）b.合并2 4c.合并5 6d.合并7 11第59页/共66页60step2step2：按左按左按左按左“0 0 0 0”右右右右“1 1 1 1”对对对对HuffmanHuffmanHuffmanHuffman树的所有树的所有树的所有树的所有分支编号

32、分支编号分支编号分支编号dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36）特征：每一码不会是另一码的前缀，译码时惟一，不会错特征：每一码不会是另一码的前缀，译码时惟一，不会错!Huffman编码也称为前缀码称为前缀码将将 Huffman树 与 Huffman编码 挂钩第60页/共66页61二、二、HuffmanHuffman编码编码由于哈夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合

33、w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。例1：假设用于通信的电文仅由8个字母 a,b,c,d,e,f,g,h 构成，它们在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？哈夫曼编码的基本思想是 出现概率大的信息用短码，概率小的用长码第61页/共66页6210717000000000000000-00000000r0010002100300320060020019007lpw13121011987654321116w=

34、7,19,2,6,32,3,21,10 w=7,19,2,6,32,3,21,10 在机内存储形式在机内存储形式为为:235282119403260100bcadegfh请注意：哈夫曼树样式不惟一！599361110104917284060100第62页/共66页6310717116235282119403260100bcadegfh对应的哈夫曼编码：符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.1000100010101000000000000

35、00100010101000010000111110011001100000101001110010111011100000001111111Huffman码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二进制等长码的WPL第63页/共66页64本本 章章 小小 结结1、定义和性质2、存储结构3、遍历4、线索化顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树二叉树森林霍夫曼编码1:2，性质有3+2条先序遍历中序遍历遍历存储结构遍历孩子兄弟先序遍历后序遍历线索树霍夫曼树应用中序遍历后序遍历先序遍历层次遍历第64页/共66页65第五章 树和二叉树结 束第65页/共66页66谢谢您的观看！第66页/共66页