数据结构课件：第六章 二叉树.ppt

1、第六章 二叉树n树及二叉树的定义n二叉树的性质n二叉树的存储n二叉树的遍历n二叉树的应用树的基本概念树定义：树是n（n0）个结点的有限集合（用T表示）。当n=0时，称为空树；当n0时，该集合满足如下条件： (1) 其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2) 其余n-1个结点可以划分成m（m0）个互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。 例如：一棵树的逻辑结构图为：ABCDGFEHIJKLM从图中可以看出它好象一棵倒栽的树。树的基本概念（续）树的相

2、关术语：树的相关术语：结点的度结点的度：一个结点的子树个数称为此结点的度。叶结点叶结点：度为0的结点，即无后继的结点，也称为终端结点。 分支结点分支结点：度不为0的结点，也称为非终端结点。结点的层次结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。 树的基本概念（续）树的度树的度：树中所有结点的度的最大值。树的深度树的深度：树中所有结点的层次的最大值。双亲结点双亲结点：一个结点的直接前驱称为该结点的双亲结点。下图中：一个结点的直接前驱称为该结点的双亲结点。下图中A是是B、C、D的双亲。的双亲。兄弟结点兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。下图中：同一

3、双亲结点的孩子结点之间互称兄弟结点。下图中的结点的结点B、C、D互为兄弟结点。互为兄弟结点。 孩子结点孩子结点：一个结点的直接后继称为该结点的孩子结点。如下图：一个结点的直接后继称为该结点的孩子结点。如下图的的B、C、D是是A的孩子。的孩子。 我们常常借助人类家族的术语，以便于直观理解结点间的层次关系。我们常常借助人类家族的术语，以便于直观理解结点间的层次关系。 ABCDGFEHIJKLM二叉树的基本概念定义：我们把满足以下两个条件的树型结构叫做二叉树（Binary Tree）： （1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。下面给出二叉树的五种基本形态：下面给出二叉

4、树的五种基本形态：(a)(a)空二叉数空二叉数(c)(c)只有左子只有左子树的二叉树树的二叉树(b)(b)只有根结只有根结点的二叉树点的二叉树(d)(d)左右子树均左右子树均非空的二叉树非空的二叉树(e)(e)只有右子树只有右子树的二叉树的二叉树性质性质1：在二叉树的第i层上至多有2i-1个结点(i1).性质性质2：深度为k的二叉树至多有2k-1个结点(k1).性质性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1.二叉树的性质两种特殊的二叉树满二叉树满二叉树：深度为深度为k且有且有2k-1个结点的二叉树。在个结点的二叉树。在满二叉树中，每层结点都是

5、满的，即每层结点都具满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。有最大结点数。 12345678910111213 1415满二叉树满二叉树两种特殊的二叉树（续）完全二叉树完全二叉树：12345678910111213 14关系：关系：满二叉树满二叉树必为必为完全二叉树，而完全二叉树完全二叉树，而完全二叉树不一定不一定是是满二叉树满二叉树。 深度为深度为k k，结点数为，结点数为n n的二叉树，如果其结点的二叉树，如果其结点1 1到到n n的位置序的位置序号分别与同深度的满二叉树的结点号分别与同深度的满二叉树的结点1 1到到n n的位置序号一一对的位置序号一一对应，则为完全二叉树

6、应，则为完全二叉树 两种特殊的二叉树（续）n满二叉树n特点：每一层上的结点数都是最大结点数n完全二叉树n特点：n叶子结点只可能在层次最大的两层上出现n对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l + 11231145891213671014151231145891267101234567123456 完全二叉树(性质性质)12第二节二叉树第二节二叉树n具有具有n n个结点的完全二叉树个结点的完全二叉树, ,其深度为其深度为loglog2 2n +1n +1n设设k k为深度，由二叉树性质，已知为深度，由二叉树性质，已知 2 2k-1k-1-1-1 n n

7、2 2k k-1-1即即 2 2k-1k-1 n n 2 2k k即即 k = logk = log2 2n +1n +1第章树与二叉树第章树与二叉树621754389 10 11 12完全二叉树(性质性质)13第二节二叉树第二节二叉树n在完全二叉树中，结点在完全二叉树中，结点i i的双亲为的双亲为i/2i/2n结点结点i i的左孩子的左孩子LCHILD(i)=2iLCHILD(i)=2in结点结点i i的右孩子的右孩子RCHILD(i)=2i+1RCHILD(i)=2i+1第章树与二叉树第章树与二叉树6217543891011122i+2i2i+32i+12ii+1i/2二叉树的存储结构二叉

8、树的结构是非线性的，每一结点最多二叉树的结构是非线性的，每一结点最多可有两个后继。可有两个后继。一、一、 二叉树的顺序存储表示二叉树的顺序存储表示二、二叉树的链式存储表示二、二叉树的链式存储表示二叉树的存储结构（续）1.顺序存储结构顺序存储结构：是用一组连续的存储单元来存放：是用一组连续的存储单元来存放二叉树的数据元素二叉树的数据元素 。ABCDEFGHIJKLABCDEFGHIJKL二叉树的顺序存储结构二叉树的顺序存储结构从上到下从左到右二叉树的存储结构（续） 对于一般的二叉树，我们必须按照对于一般的二叉树，我们必须按照完全二叉树完全二叉树的的形式来存储，就会造成空间的浪费。单支树就是一形式

9、来存储，就会造成空间的浪费。单支树就是一个极端情况。个极端情况。ABCDABCD单支树单支树二叉树的存储结构（续）2. 链式存储结构：链式存储结构：我们可以设计每个结点至少包括三我们可以设计每个结点至少包括三个域：个域：数据域、左孩子域和右孩子域：数据域、左孩子域和右孩子域： LChildDataRChild二叉链表二叉链表DABCEFGA BCD E F G 二叉树二叉树T二叉链表二叉链表二叉树遍历指按一定规律对二叉树中的每个结点进行访问且仅访问一次。指按一定规律对二叉树中的每个结点进行访问且仅访问一次。 先序遍历过程：先序遍历过程：访问根结点；访问根结点；按先序遍历左子树；按先序遍历左子树

10、；按先序遍历右子树。按先序遍历右子树。RChildDataLChildDataLChildLChildRChild中序遍历过程：中序遍历过程：按中序遍历左子树；按中序遍历左子树；访问根结点；访问根结点；按中序遍历右子树。按中序遍历右子树。后序遍历过程：后序遍历过程：按后序遍历左子树；按后序遍历左子树；按后序遍历右子树；按后序遍历右子树； 访问根结点访问根结点遍历二叉树n如果规定先左子树后右子树，则共有三种组合如果规定先左子树后右子树，则共有三种组合1.DLR 1.DLR 先序遍历先序遍历 2.LDR 2.LDR 中序遍历中序遍历 3.LRD 3.LRD 后序遍历后序遍历 LR二叉树遍历（续）先

11、序遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.访问根节点访问根节点(D)(D)3.3.先序遍历左子树先序遍历左子树(L)(L)4.4.先序遍历右子树先序遍历右子树(R)(R)LR二叉树遍历（续）二叉树遍历（续）例：给出下面二叉树的三种遍历序列ABCDEFGIH先序遍历：ABDEHICFG中序遍历：DBHEIAFCG后序遍历：DHIEBFGCA先序遍历二叉树n算法算法( (举例举例) )：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.先序遍历左子树(L)4.先序遍历右子树(R)输出结果：输出结果：ABDEGCFABDEGCFADBFC

12、GE二叉树遍历（续）先序遍历二叉树n算法算法(C(C语言实现语言实现) )：void PreOrderTraverse ( BinTree T ) if (T) cout data; PreOrderTraverse ( T-lChild ); PreOrderTraverse ( T-rChild ); 二叉树遍历（续）中序遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.中序遍历左子树中序遍历左子树(L)(L)3.3.访问根节点访问根节点(D)(D)4.4.中序遍历右子树中序遍历右子树(R)(R)LR二叉树遍历（续）中序遍历二叉树n算法算法(

13、(举例举例) )：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R)输出结果：输出结果：DBGEAFCDBGEAFCADBFCGE二叉树遍历（续）三、中序遍历二叉树n算法算法(C(C语言实现语言实现) )：void InOrderTraverse ( BinTree T ) if (T) InOrderTraverse ( T-lChild ); cout data; InOrderTraverse ( T-rChild ); 二叉树遍历（续）后序遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.后

14、序遍历左子树后序遍历左子树(L)(L)3.3.后序遍历右子树后序遍历右子树(R)(R)4.4.访问根节点访问根节点(D)(D)LR二叉树遍历（续）后序遍历二叉树n算法算法( (举例举例) )：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.后序遍历左子树(L)4.后序遍历右子树(R)输出结果：输出结果：DGEBFCADGEBFCAADBFCGE二叉树遍历（续）后序遍历二叉树n算法算法(C(C语言实现语言实现) )：void PostOrderTraverse ( BinTree T ) if (T) PostOrderTraverse ( T-lChild ); PostOrderTr

15、averse ( T-rChild ); cout data; 二叉树遍历（续）n什么是线索二叉树？什么是线索二叉树？n类似与单向链表发展到双向链表类似与单向链表发展到双向链表n线索二叉树有什么用途？线索二叉树有什么用途？线索二叉树一、增加新指针n最简单的方法是在每个结点中，增加前驱最简单的方法是在每个结点中，增加前驱(fwd)(fwd)和后继和后继(bkwd)(bkwd)指针指针n在做二叉树遍历（前、中、后序），将每个结在做二叉树遍历（前、中、后序），将每个结点的前驱和后继信息添入点的前驱和后继信息添入fwdfwd和和bkwdbkwd域中域中fwdlChilddatarChildbkwd线索

16、二叉树二、利用空指针n在有在有n n个结点的二叉树中，必定存在个结点的二叉树中，必定存在n+1n+1个空链个空链域域n因为每个结点有两个链域（左、右孩子指针），因为每个结点有两个链域（左、右孩子指针），因此共有因此共有2n2n个链域个链域n除根结点外，每个结点都有且仅有一个分支相除根结点外，每个结点都有且仅有一个分支相连，即连，即n-1n-1个链域被使用个链域被使用线索二叉树（续）二、利用空指针n在结点中增加两个标记位（在结点中增加两个标记位（LTag, RTag)LTag, RTag)nLTag=0, lChildLTag=0, lChild域指示结点的左孩子域指示结点的左孩子LTag=1,

17、 lChildLTag=1, lChild域指示结点的前驱结点域指示结点的前驱结点nRTag=0, rChildRTag=0, rChild域指示结点的右孩子域指示结点的右孩子RTag=1, rChildRTag=1, rChild域指示结点的后继结点域指示结点的后继结点LTaglChilddatarChildRTag线索二叉树（续）一、树的存储结构1.1.双亲表示法双亲表示法n采用一组连续的存储空间采用一组连续的存储空间ABCDEFG-10001130 1 2 3 4 5 6AEBGDFC树和森林一、树的存储结构2.2.孩子表示法孩子表示法n可以采用多重链表，即每个结点有多个指针可以采用多重

18、链表，即每个结点有多个指针n最大缺点是空链域太多最大缺点是空链域太多(d-1)n+1(d-1)n+1个个 AEBGDFC data child1child2child3childd树与森林一、树的存储结构2.2.孩子表示法孩子表示法n将每个结点的孩子排列起来，用单链表表示将每个结点的孩子排列起来，用单链表表示n将每个结点排列成一个线性表将每个结点排列成一个线性表AEBGDFCABCDEFG0123456Root123 45 6 树与森林（续）一、树的存储结构3.3.孩子兄弟表示法孩子兄弟表示法n采用二叉链表采用二叉链表n左边指针指向第一个孩子，右边指针指向兄弟左边指针指向第一个孩子，右边指针指

19、向兄弟AEBGDFC datafirstChild nextSiblingBCDGFE A 树与森林（续）二、树与二叉树的对应关系n树与二叉树都可以采用二叉链表作存储结构树与二叉树都可以采用二叉链表作存储结构n任意给定一棵树，可以找到一个唯一的二叉树任意给定一棵树，可以找到一个唯一的二叉树( (没有右子树没有右子树) )AEBGDFCBCDGFE A ABGDFCE树对应的二叉树树与森林（续）三、森林与二叉树的对应关系n如果把森林中的第二棵树的根结点看作是第一如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应叉树

20、与之对应三棵树的森林对应的二叉树T1 T2 T3AFHB C DGIJEKABCEDHIKFGJ树与森林（续）森林转为二叉树(算法)如果如果F=TF=T1 1, T, T2 2, , , T, Tn n 是森林，是森林，B B（rootroot，LBLB，RBRB）是二叉树是二叉树（1 1）若）若F F为空，即为空，即n n0 0，则，则B B是空树；是空树；（2 2）若）若F F非空，则非空，则nB B的根的根rootroot即为即为F F中第一棵树中第一棵树T T1 1的根的根rootroot（T T1 1）；）；nB B的左子树的左子树LBLB是从是从T T1 1中根结点的子树森林中根结

21、点的子树森林F F1 1=T=T1111, T, T1212, , , , T T1m1m 转换而成的二叉树；转换而成的二叉树；nB B的右子树的右子树RBRB是从是从F F2 2=T=T2 2, , , T, Tn n 转换而成的二叉树；转换而成的二叉树； 树与森林（续）二叉树转为森林(算法)如果如果F=TF=T1 1, T, T2 2, , , T, Tn n 是森林，是森林，B B（rootroot，LBLB，RBRB）是二叉树是二叉树（1 1）若）若B B为空，则为空，则F F是空；是空；（2 2）若）若B B非空，则非空，则nF F中第一棵树中第一棵树T T1 1的根的根rootro

22、ot（T T1 1）即为）即为B B的根的根root root ；nT T1 1中根结点的子树森林中根结点的子树森林F F1 1 是由是由B B的左子树的左子树LBLB转换而成的森转换而成的森林；林；nF F中除中除T T1 1外，其他树组成的森林外，其他树组成的森林F F2 2=T=T2 2, , , T, Tn n 是从是从B B的右的右子树子树RBRB转换而成的森林；转换而成的森林； 树与森林（续）四、树的遍历n对树的遍历主要有两种：对树的遍历主要有两种：1. 1. 先根（次序）遍历先根（次序）遍历2. 2. 后根（次序）遍历后根（次序）遍历AEBGDFC树与森林（续）四、树的遍历1.

23、1. 先根（次序）遍历先根（次序）遍历 当树非空时当树非空时n 访问根结点访问根结点n 依次先根遍历根的各棵子树依次先根遍历根的各棵子树 输出结果：输出结果：ABEFCDGABEFCDGAEBGDFC树与森林（续）四、树的遍历2. 2. 后根（次序）遍历后根（次序）遍历 当树非空时当树非空时n依次后根遍历根的各棵子树依次后根遍历根的各棵子树n访问根结点访问根结点 输出结果：输出结果：EFBCGDAEFBCGDAAEBGDFC树与森林（续）一、最优二叉树n路径：从树中一个结点到另一个结点之间的分路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径支构成这两个结点之间的路径n路径长度

24、：路径上的分支数目路径长度：路径上的分支数目n树的路径长度：从树根到树的路径长度：从树根到每个结点的路径长度之和每个结点的路径长度之和n右树路径长度为：右树路径长度为：2 2* *1 + 31 + 3* *2 + 12 + 1* *3 = 113 = 11ADBFCGE赫夫曼树及其应用（续）一、最优二叉树n带权路径长度：从结点到树根之间的路径长度带权路径长度：从结点到树根之间的路径长度与结点上权的乘积与结点上权的乘积n树的带权路径长度树的带权路径长度(WPL)(WPL)：树中所有叶子结点：树中所有叶子结点的带权路径长度之和的带权路径长度之和nWPL = 2WPL = 2* *5+35+3* *

25、3+23+2* *4=274=27ADBFCGE5赫夫曼树及其应用（续）一、最优二叉树n最优二叉树：假设二叉树有最优二叉树：假设二叉树有n n个叶子，其每个个叶子，其每个叶子结点带权叶子结点带权w wi i，则带权路径长度，则带权路径长度WPLWPL最小的最小的二叉树称为最优二叉树二叉树称为最优二叉树n赫夫曼赫夫曼(Huffman)(Huffman)树就是一棵最优二叉树树就是一棵最优二叉树nWPL = 1WPL = 1* *5+25+2* *3+23+2* *4=194=19ADBCE5赫夫曼树及其应用（续）二、Huffman树(构造)n在在HuffmanHuffman树中，权值最大的结点离根

26、最近树中，权值最大的结点离根最近n权值最小的结点离根最远权值最小的结点离根最远ADBCE5赫夫曼树及其应用（续）二、Huffman树(算法)1.1.根据给定的根据给定的n n个权值个权值(w(w1 1, w, w2 2, , , w, wn n) )构成构成n n棵二叉树棵二叉树的集合的集合F=TF=T1 1, T, T2 2, , , T, Tn n ，其中每棵二叉树，其中每棵二叉树T Ti i中只中只有一个带树为有一个带树为T Ti i的根结点的根结点2.2.在在F F中选取两棵根结点的权值最小的树作为左右子树中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值

27、为其左右构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和子树权值之和3.3.在在F F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F F中中4.4.重复重复2, 32, 3，直到，直到F F只含一棵树为止只含一棵树为止赫夫曼树及其应用（续）二、Huffman树(举例)F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 1127461118赫夫曼树及其应用（续）三、Huffman编码n设给出一段报文：设给出一段报文：GOOD_GOOD_GOODGODGGOOD_GO

28、OD_GOODGODGn字符集合是字符集合是 O, G, _, D O, G, _, D ，各个字符出现，各个字符出现的频度的频度( (次数次数) )是是 W W 7, 5, 2, 4 7, 5, 2, 4 。n若给每个字符以等长编码若给每个字符以等长编码O: 00 G: 10 _: 01 D: 11O: 00 G: 10 _: 01 D: 11n则总编码长度为则总编码长度为 (2+7+4+5) (2+7+4+5) * * 2 = 36. 2 = 36.赫夫曼树及其应用（续）三、Huffman编码n若按各个字符出现的概率不同而给予不等长编若按各个字符出现的概率不同而给予不等长编码，可望减少总编

29、码长度。码，可望减少总编码长度。n各字符出现概率为各字符出现概率为 2/18, 7/18, 4/18, 2/18, 7/18, 4/18, 5/18 ,5/18 ,化整为化整为 2, 7, 4, 5 2, 7, 4, 5 n可构成右图所示可构成右图所示HuffmanHuffman树树5274赫夫曼树及其应用（续）三、Huffman编码n令左孩子分支为编码令左孩子分支为编码0 0，右孩子分支为编码，右孩子分支为编码1 1n得到不等长编码：得到不等长编码：O:0 G:10 _:110 D:111O:0 G:10 _:110 D:111n则总编码长度为则总编码长度为 7 7* *1+51+5* *2

30、+42+4* *3+23+2* *3 = 353 = 35nHuffmanHuffman是一种前缀编码，解码时不会混淆是一种前缀编码，解码时不会混淆5274000111赫夫曼树及其应用（续）二叉树应用问题：对于一个集合： 12，32，4，6，10，34，24，46 给定一个数13，在集合中寻找距离它最近的元素。一般方法：需要遍历集合中每个元素，耗时怎样用二叉树来表示集合？二叉树应用（续）188335112840461012 24324634作为实验课作业，用C语言实现n在一段文字中，7个常用汉字及出现频度如下：的 地 于 个 和 是 有 20 19 18 17 15 10 1n要求：（1）画出对应的Huffman树；（2）求出每个汉字的Huffman编码。重点n了解二叉树的定义n理解二叉树的性质n理解二叉树的存储结构n掌握遍历二叉树的方法n了解二叉树的应用，会编写二叉树相关算法谢谢！