第7章树形结构(最新修改)

《第7章树形结构(最新修改)》由会员分享，可在线阅读，更多相关《第7章树形结构(最新修改)（99页珍藏版）》请在文档大全上搜索。

1、第第7 7章章 树形结构树形结构7.1 7.1 树的基本概念树的基本概念 7.2 7.2 二叉树概念和性质二叉树概念和性质7.3 7.3 二叉树存储结构二叉树存储结构7.4 7.4 二叉树的遍历二叉树的遍历7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.6 7.6 二叉树的构造二叉树的构造7.8 7.8 哈夫曼树哈夫曼树 本章小结本章小结7.7 7.7 线索二叉树线索二叉树7.9 7.9 并查集并查集 7.1 7.1 树的基本概念树的基本概念 7.1.1 7.1.1 树的定义树的定义 7.1.3 7.1.3 树的基本术语树的基本术语 7.1.2 7.1.2 树的表示树的表示

2、7.1.4 7.1.4 树的性质树的性质7.1.5 7.1.5 树的基本运算树的基本运算7.1.6 7.1.6 树的存储结构树的存储结构数据结构数据结构可分为可分为线性结构线性结构和和非线性结构非线性结构两大类。在第两大类。在第3，4，5章章讨论的都是线性结构，本章和下一章讨论非线性结构。讨论的都是线性结构，本章和下一章讨论非线性结构。 线性结构线性结构(线性表线性表, 栈栈,队列等队列等)：数据元素之间是一对一的关系，：数据元素之间是一对一的关系，除了第一个数据元素外，其它每个元素都有且只有一个直接前驱；除了第一个数据元素外，其它每个元素都有且只有一个直接前驱；除了最后一个数据元素，其它每个

3、元素都有且只有一个直接后继。除了最后一个数据元素，其它每个元素都有且只有一个直接后继。 非线性结构非线性结构: 至少存在一个数据元素有不止一个直接前驱或后至少存在一个数据元素有不止一个直接前驱或后继继(树树,图等图等)7.1 树的定义以及相关术语树的定义以及相关术语BADEFGIHCa一个结点的树一个结点的树3. 广义表表示法广义表表示法(A(B(D),C)4.树的形式化表示方法树的形式化表示方法 树的形式化表示法主要用于树的理论描述。树的形式化表示树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树法定义树T为为T=(D,R)。其中。其中D为为T中结点的集合，中结点的集合，R为树为树

4、T中结中结点之间关系的集合。例如右图所示的树用形式化表示方法表示点之间关系的集合。例如右图所示的树用形式化表示方法表示如下：如下： , （b b）树的基本术语）树的基本术语1. 1. 树的结点树的结点: :数据元素和构造数据元素之间关系的指数据元素和构造数据元素之间关系的指针合起来称作结点针合起来称作结点; ;2. 2. 结点的度结点的度: :一个结点拥有的子树的个数一个结点拥有的子树的个数, ,称作该结称作该结点的度；点的度；3.3.叶子结点叶子结点：度为零的结点称为：度为零的结点称为叶结点叶结点; ;4.4.孩子结点，双亲结点孩子结点，双亲结点：树中一个结点的子树的根结：树中一个结点的子树

5、的根结点称作这个结点的孩子结点，相应地，该结点称为孩点称作这个结点的孩子结点，相应地，该结点称为孩子的双亲结点；子的双亲结点；5.5.兄弟结点，堂兄弟结点兄弟结点，堂兄弟结点：具有相同的双亲结点称为：具有相同的双亲结点称为兄弟结点；其双亲在同一层的结点互为堂兄弟结点；兄弟结点；其双亲在同一层的结点互为堂兄弟结点；6.6.祖先结点祖先结点：从根结点到树中某结点所经过的所有分：从根结点到树中某结点所经过的所有分支结点称作该结点的祖先结点；支结点称作该结点的祖先结点；7.7.子孙结点子孙结点：某一结点的所有孩子结点，以及这些孩：某一结点的所有孩子结点，以及这些孩子结点的孩子结点称为该结点的子孙结点；

6、子结点的孩子结点称为该结点的子孙结点；8. 8. 树的度树的度: :树中所有结点的度的最大值称为该树的度；树中所有结点的度的最大值称为该树的度； 含义含义: :树中最大分支数为树的度树中最大分支数为树的度; ;9. 9. 结点的层次结点的层次: :从根结点到树中某结点所经路径上的从根结点到树中某结点所经路径上的分支数称为该结点的层次。分支数称为该结点的层次。10.10.树的深度树的深度：树中结点的最大层次称为树的深度或：树中结点的最大层次称为树的深度或高度高度11.11.无序树，有序树无序树，有序树：如果将树中结点的各子树看成：如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该

7、树为有从左到右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。序树，否则称为无序树。12.12.森林森林: :是是m(m=0)m(m=0)棵互不相交的树的集合。棵互不相交的树的集合。 7.2 二叉树二叉树 二叉树是另外一种树形结构，它的特点是每个结点至二叉树是另外一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在大于多只有两棵子树（即二叉树中不存在大于2的结点），并的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。由且，二叉树的子树有左右之分，其次序不能任意颠倒。由于二叉树的左右子树也是二叉树，则由二叉树的定义，它于二叉树的左右子树也是二叉树，则由二叉树的

8、定义，它们也可以是空树，由此，二叉树可以有五种基本形态，如们也可以是空树，由此，二叉树可以有五种基本形态，如下图所示。下图所示。（1）二叉树的定义）二叉树的定义二叉树的二叉树的5种基本形态种基本形态（2）满二叉树和完全二叉树的定义）满二叉树和完全二叉树的定义1243567满二叉树：在一棵二叉树中，如果所满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。并且所有叶子结点都在同一层上。124356完全二叉树：如果一棵具完全二叉树：如果一棵具有有n个结点的二叉树的结构个结点的二叉树的结构与满二叉树的前与满二叉树的前n个结点的

9、个结点的结构相同，这样的二叉树称结构相同，这样的二叉树称作完全二叉树。作完全二叉树。（3）二叉树的性质）二叉树的性质 性质性质1： 若规定根结点的层次为若规定根结点的层次为1，则一颗非空二叉树的第，则一颗非空二叉树的第i层层上最多有上最多有2i-1（i=1)个结点。个结点。 该性质可以用数许归纳法来证明：该性质可以用数许归纳法来证明：第一步：当层次第一步：当层次n=1是，二叉树在根结点只有一个结点，是，二叉树在根结点只有一个结点，21-1=1，结论成立；结论成立；第二步：假设当层次第二步：假设当层次n=t时结论成立，即在第时结论成立，即在第t层上最多有层上最多有2t-1个结个结点；点；第三步：

10、当层次第三步：当层次n=t+1时，根据二叉树的定义，第时，根据二叉树的定义，第t层上的每个结层上的每个结点最多有点最多有2个子结点，所以在第个子结点，所以在第t+1成上最多有成上最多有2*2t-1=2(t+1)-1个结点。个结点。因此，结论成立。因此，结论成立。性质性质2： 若规定空树的深度为若规定空树的深度为0，则，则深度为深度为h的二叉树最大结点个数的二叉树最大结点个数（至多）是（至多）是2h-1个结点（个结点（h00)。证明：证明： 当深度为当深度为=0时是空二叉树，空二叉树应当一个结点也没有；时是空二叉树，空二叉树应当一个结点也没有； 当深度当深度h0时是非空二叉树，要求最大结点个数，

11、只要该时是非空二叉树，要求最大结点个数，只要该二叉树的每一层都达到最大，这样，可以利用性质二叉树的每一层都达到最大，这样，可以利用性质1来计算，来计算，计算过程如下：计算过程如下： i=02i-1=2h-1h第第6层就是满的，且第层就是满的，且第6层的最后八个结点没有孩子结点，其它的层的最后八个结点没有孩子结点，其它的都有左右孩子结点。都有左右孩子结点。 26163第第6层上最多有层上最多有2i12612532 32824 24*2=48 48+63=111性质性质3：对任何一颗二叉树对任何一颗二叉树T，如果其终端结点数如果其终端结点数 为为n0,度为度为2的结点的结点数为数为n2，则则n0=