课件5树和二叉树

1、数据结构5 树和二叉树数据结构5 树和二叉树1. 掌握二叉树的基本概念、性质和存储结构2. 掌握二叉树的前、中、后序遍历方法3. 了解线索化二叉树的思想4. 了解：霍夫曼树的实现方法、构造霍夫曼编码的方法5. 掌握：森林与二叉树的转换，树的遍历方法教学目标数据结构5 树和二叉树5.1 树的定义和基本术语ACBGFEHIJDMKLA树是树是n n个结点的有限集个结点的有限集T1T2T3数据结构5 树和二叉树 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)结点各子树从左至右有序，不能互换（左为第一）结点各子

2、树可互换位置。ACBGFEHIJDMKL基本术语数据结构5 树和二叉树即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙ACBGFEHIJDMKL基本术语数据结构5 树和二叉树即树的数据元素结点挂接的子树数

3、结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值指所有结点中最大的层数ACBGFEHIJDMKL层次1234基本术语数据结构5 树和二叉树5.2 二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。数据结构5 树和二叉树二叉树基本特点：结点的度小于等于2有序树（子树有序，不能

4、颠倒）数据结构5 树和二叉树具有3个结点的二叉树可能有几种不同形态？ 练习数据结构5 树和二叉树性质1: 在二叉树的第i层上至多有个结点二叉树的性质提问：第i层上至少有 个结点？性质2: 深度为k的二叉树至多有个结点提问：深度为k时至少有 个结点？1k数据结构5 树和二叉树1891011124526731891011124526731 nB1212nnB11212nnn012nnn性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n21 （即n0=n2+1）数据结构5 树和二叉树189101112131415452673满二叉树：k（特点：每层都“充满”了结点）18910

5、1112452673特殊形态的二叉树完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边数据结构5 树和二叉树满二叉树是叶子一个也不少的树，而完全二叉树虽然满二叉树是叶子一个也不少的树，而完全二叉树虽然前前n-1n-1层是满的，但最底层却允许在右边缺少连续若层是满的，但最底层却允许在右边缺少连续若干个结点。干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。189101112131415452673189101112452673满二叉树和完全二叉树的区别数据结构5 树和

6、二叉树一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（ ）。 练习2500数据结构5 树和二叉树性质4: 具有n个结点的完全二叉树的深度必为log2n1189101112452673k层层nk-1层层121k12 k12121kkn数据结构5 树和二叉树性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2。数据结构5 树和二叉树二叉树的顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。数据结构5 树和二叉树a b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7

7、 8 9 10abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树二叉树的顺序存储数据结构5 树和二叉树DATAPARENTLCHILDRCHILDlchilddatarchildlchilddatarchildparent二叉树的链式存储数据结构5 树和二叉树ABCDEFG AB C D E F G二叉链表数据结构5 树和二叉树分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n1个结点的链域存放指针，指向非空子女结点。空指针数目2n(n-1)=n+1有 个练习 AB C D E F Gn+1数据结构5 树和二叉树三叉链表ABCDEFG A

8、 B C D E F Glchild data parent rchild数据结构5 树和二叉树5.3 二叉树的遍历遍历定义遍历定义指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。遍历用途遍历用途它是树结构插入、删除、修改、查它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一找和排序运算的前提，是二叉树一切运算的基础和核心。切运算的基础和核心。 数据结构5 树和二叉树ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD遍历规则先左后右数据结构5 树和二叉树先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍

9、历： A B CD E口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根数据结构5 树和二叉树若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 重要结论数据结构5 树和二叉树练习已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。由后序遍历特征，根结点必在后序序列尾部（A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（BDCE），其右部必全部是右子树子孙（FHG）；

10、继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。数据结构5 树和二叉树中序遍历后序遍历（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF数据结构5 树和二叉树5.4 二叉树的二叉链表实现结点定义结点定义数据结构5 树和二叉树Status PreOrderTraverse(BiTree T) if(T=NULL) return OK; /结束 else coutdata; PreOrderTraverse(T-lchild); /递归左子树 PreOrderTraverse(T-rchild); /递归右

11、子树 先序遍历递归算法结束条件递归过程递归算法递归算法 = = 递归结束条件递归结束条件 + + 递归过程递归过程数据结构5 树和二叉树Status PreOrderTraverse(BiTree T) if(T=NULL) return OK; else coutdata; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T

12、 L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：先序序列：ABDC数据结构5 树和二叉树创建二叉树创建二叉树数据结构5 树和二叉树获取结点数获取结点数数据结构5 树和二叉树获取高度获取高度数据结构5 树和二叉树查找结点查找结点数据结构5 树和二叉树获取双亲结点获取双亲结点数据结构5 树和二叉树如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访

13、问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历遍历算法的非递归实现分析数据结构5 树和二叉树使用一个栈s存放路径。开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空，则访问根结点；然后p进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况若从左子树返回，说明左子树遍历结束，应该将指针指向其双亲结点的右孩子进行遍历，即指向栈顶结点的右子树若从右子树返回，说明已将以其双亲结点为根的子树遍历结束，则应该将指针指向其双亲结点的右兄弟进行遍历，即指向栈顶结点的右子树3、当指针为空且栈为空时，遍历结束先序遍历算法的非递归算法数据结构5 树和二叉树ADBCE栈栈s访问序列访

14、问序列 p不空时不空时 Visit (p); Push ( S, p ); p = p-lc; p空时空时 Pop ( S, p ) p = p-rc;AABBCCDDEE先序遍历算法的非递归算法示例数据结构5 树和二叉树使用栈存放经过的路径，开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空；p进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况若从左子树返回，说明左子树遍历结束，应该将指针指向其双亲结点，访问双亲结点，并对双亲结点的右孩子进行遍历，即访问栈顶结点后指向栈顶结点的右子树若从右子树返回，说明已将以其双亲结点为根的子树遍历结束，则应该将指针指向其未访问过的祖

15、先结点进行访问，并指向其结点的右子树，即访问栈顶结点后指向栈顶结点的右子树3、当指针为空且栈为空时，遍历结束中序序遍历算法的非递归算法数据结构5 树和二叉树ADBCE p不空时不空时 Push ( S, p ); p = p-lc; p空时空时 Pop ( S, p ) Visit (p); p = p-rc;栈栈s访问序列访问序列AABBCC DD EE中序序遍历算法的非递归算法示例数据结构5 树和二叉树使用栈存放经过的结点及结点标志，开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空，先将标志tag0；再将p及tag进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况

16、若tag0，则改变tag1；再把tag和弹出的结点重新入栈；然后将指针指向该结点的右子树若tag1，则访问弹出的结点，并将弹出的结点指针置空3、当指针为空且栈为空时，遍历结束后序序遍历算法的非递归算法数据结构5 树和二叉树ADBCE栈栈s访问序列访问序列A0B0B1C0C1D0D1E0E1 p不为空不为空 SNode.tag = 0; Push ( S, SNode ); SNode.p = SNode.p-lc;p为空且为空且tag0 Pop ( S, SNode ); SNode.tag = 1; Push ( S, SNode); SNode.p = SNode.p-rc; p为空且为空

17、且tag1 Pop ( S, SNode ); Visit (SNode.p ); SNode.p = NULL; CE DBA1A后序序遍历算法的非递归算法示例数据结构5 树和二叉树AFEDCBG时间效率: /每个结点只访问一次空间效率:O(n) /栈占用的最大辅助空间非递归遍历算法的分析数据结构5 树和二叉树二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。思考线索化二叉树有n+1个 AB C D E F G数据结构5 树和二叉树普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得

18、若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树例如中序遍历结果：B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！可能是根、或最左（右）叶子5.5 线索二叉树数据结构5 树和二叉树1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子； 否则， rchild指向其直接后继(即线索) 。为了避免混淆，增加两个标志域lchildLTagdataRTag rchild线索化二叉树数据结构5 树和二叉树LTag :若 LTag=0,

19、 lchild域指向左孩子； 若 LTag=1, lchild域指向其前驱。RTag :若 RTag=0, rchild域指向右孩子； 若 RTag=1, rchild域指向其后继。 lchildLTagdataRTag rchild线索化二叉树数据结构5 树和二叉树ABCDE A B D C ET先序序列：先序序列：ABCDE0000111111 lchild LTag data RTag rchild先序线索二叉树LTag=0, lchild域指向左孩子LTag=1, lchild域指向其前驱RTag=0, rchild域指向右孩子RTag=1, rchild域指向其后继 数据结构5 树和

20、二叉树ABCDE A B D C ET中序序列：中序序列：BCAED0000111111 lchild LTag data RTag rchild中序线索二叉树数据结构5 树和二叉树 lchild LTag data RTag rchildABCDE A B D C ET后序序列：后序序列：CBEDA0000111111后序线索二叉树数据结构5 树和二叉树线索线索：指向结点前驱和后继的指针：指向结点前驱和后继的指针线索链表线索链表：加上线索二叉链表：加上线索二叉链表线索二叉树线索二叉树：加上线索的二叉树（图形式样）：加上线索的二叉树（图形式样）线索化线索化：对二叉树以某种次序遍历使其变为线索二

21、叉：对二叉树以某种次序遍历使其变为线索二叉树的过程树的过程线索化二叉树的几个术语数据结构5 树和二叉树ABCGEIDHFroot悬空？悬空？悬空？该二叉树中序遍历结果为该二叉树中序遍历结果为: : H, D, I, B, E, A, F, C, G为避免悬空态，应增设一个头结点数据结构5 树和二叉树00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0-root0数据结构5 树和二叉树画出与二叉树对应的中序线索二叉树 2825405560330854因为中序遍历序列是：55 40 25 60

22、 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL练习数据结构5 树和二叉树5.5 霍夫曼树及其应用路 径路径长度带权路径长度:树的带权路径长度：WPL = wklk k=1nAFEDCBG:由一结点到另一结点间的分支所构成:路径上的分支数目结点到根的路径长度与结点上权的乘积2235数据结构5 树和二叉树dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36权值分别为7，5，2，4，构造有4个叶子结点的二叉树霍霍 夫夫 曼曼 树树：

23、带权路径长度最小的树带权路径长度最小的树数据结构5 树和二叉树根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树。在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即霍夫曼树。霍夫曼树的构造过程数据结构5 树和二叉树a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼树的构造过程数据结构5 树和二叉树在远程通讯中，要将待传字符转换成二进制的字符串，在远程通讯中，要将待传字符转换成二进

24、制的字符串，怎样编码才能使它们组成的报文在网络中传得最快？怎样编码才能使它们组成的报文在网络中传得最快？A00B01C10D11ABACCDA000110010101100A0B00C1D01000011010霍夫曼树应用实例霍夫曼编码出现次数较多的字符采用尽可能短的编码数据结构5 树和二叉树关键：关键：要设计长度不等的编码，则必须使任一字符的要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的编码都不是另一个字符的编码的前缀前缀前缀编码前缀编码0000AAAA ABA BB重码ABACCDAA0B00C1D01000011010霍夫曼树应用实例霍夫曼编码数据结构5 树和二叉树

25、ACBD000111采用二叉树设计前缀编码左分支用“0”右分支用“1”A0B110C10D111 0110010101110 ABACCDA数据结构5 树和二叉树分解接收字符串：遇分解接收字符串：遇“0 0”向左，遇向左，遇“1 1”向右；一旦到达叶子结向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。点，则译出一个字符，反复由根出发，直到译码完成。 0110010101110ACBD000111ABACCDA特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码霍夫曼编码的译码过程数据结构5 树和二叉树假设通信的电文仅由8个字母组成，字符在电文中出现的频率分别为（7、19

26、、2、6、32、3、21、10），试为这8个字母设计Huffman编码集合集合F 7、19、2、6、32、3、21、10 523集合集合F 7、19、6、32、21、10 、517710116603228401921100集合集合F 7、19、32、21、10、11集合集合F 19、32、21、11、17集合集合F 19、32、21、28集合集合F 32、28、40集合集合F 40、60集合集合F 1000001101100110101101111101111数据结构5 树和二叉树 霍夫曼编码是不等长编码 霍夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀 霍夫曼编码树中没有度为1

27、的结点。若叶子结点的个数为n，则霍夫曼编码树的结点总数为 2n-1 发送过程：根据由霍夫曼树得到的编码表送出字符数据 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束霍夫曼编码的几点结论数据结构5 树和二叉树5.6 树和森林ACBGFEHIJDMKL数据结构5 树和二叉树若树非空，则先访问树的根结点，然后依次先根遍历根的每棵子树RABDCFGEIHR（ADE）（B）（CFGHI）树的先根遍历RADEBCFGHI5.6 树和森林树的先根遍历数据结构5 树和二叉树若树非空，则先依次后根遍历根的每棵子树，然后访问树的根结点RABDCFGEIH（A

28、DE）（B）（CFGHI） R树的后根遍历（DEA）（B）（FGHI）C）R（DEA）（B）（GHIFC）R树的后根遍历数据结构5 树和二叉树若树非空，则从树的根结点起按层从左到右依次访问各结点RABDCFGEIHR （ABC）（DEF）（GHI）树的层次遍历RABCDEFGHI树的层次遍历数据结构5 树和二叉树练习：写出下面这棵树的先根、后根和层次遍历ABJDCFGEIH数据结构5 树和二叉树A AB BD DC CF FG GE EI IH H若森林非空，则可以按照下述规则遍历：若森林非空，则可以按照下述规则遍历：a a、访问森林中第一棵树的根结点、访问森林中第一棵树的根结点b b、先序遍

29、历第一棵树中根结点的子树森林、先序遍历第一棵树中根结点的子树森林c c、先序遍历除去第一棵树之后剩余的树构成的森林、先序遍历除去第一棵树之后剩余的树构成的森林森林的先序遍历森林的先序遍历A A（DEDE）（）（BCFGHIBCFGHI）A DE BCFGHIA DE BCFGHI森林的先序遍历数据结构5 树和二叉树A AB BD DC CF FG GE EI IH H若森林非空，则可以按照下述规则遍历：若森林非空，则可以按照下述规则遍历：a a、中序遍历第一棵树中根结点的子树森林、中序遍历第一棵树中根结点的子树森林b b、访问森林中第一棵树的根结点、访问森林中第一棵树的根结点c c、中序遍历除

30、去第一棵树之后剩余的树构成的森林、中序遍历除去第一棵树之后剩余的树构成的森林森林的中序遍历森林的中序遍历（DEDE ）A A （BCFGHIBCFGHI）DE A DE A （B B （FGHIFGHI C C）DE A B GHIF CDE A B GHIF C森林的中序遍历数据结构5 树和二叉树A AB BD DC CF FG GE EI IH H若森林非空，则可以按照下述规则遍历：若森林非空，则可以按照下述规则遍历：a a、对第一棵树从根结点起按层从左到右依次访问结点、对第一棵树从根结点起按层从左到右依次访问结点b b、按层访问森林中除去第一棵树之后剩余的树构成的森林、按层访问森林中除去

31、第一棵树之后剩余的树构成的森林森林的层次遍历森林的层次遍历ADE B CFGHIADE B CFGHI森林的层次遍历数据结构5 树和二叉树练习：写出下面森林的先序、后序和层次遍历BJDCFGEIH数据结构5 树和二叉树RABDCFGEIHRABDCFGEIH（1）加线：在各兄弟间加一连线）加线：在各兄弟间加一连线（2）去线：对任何结点，除了其最左子树）去线：对任何结点，除了其最左子树之外，去掉该结点与其他子树之间的连线之外，去掉该结点与其他子树之间的连线（3）调整二叉树的层次）调整二叉树的层次树和二叉树的转换数据结构5 树和二叉树（1）将森林中的每一棵树转换成二叉树（2）将每棵二叉树按左孩子右兄弟的规则连接成一棵二叉树ABDCFGEIHABDCFGEIH森林与二叉树的转换数据结构5 树和二叉树ABJDCFGEIH练习：写出下面这两棵树转换为二叉树和森林E EC CD DB BF FA AG GH HJ JI I数据结构5 树和二叉树ABDCFGEIHABDCFGEIH森林的先序遍历森林的先序遍历：A DE BCFGHI森林的中序遍历森林的中序遍历：DE A B GHIF C二叉树的先序遍历二叉树的先序遍历：A DE BCFGHI二叉树的中序遍历二叉树的中序遍历