《数据结构与C++算法设计案例教程 教学课件 ppt 作者 赖俊峰 第六章》由会员分享，可在线阅读，更多相关《数据结构与C++算法设计案例教程 教学课件 ppt 作者 赖俊峰 第六章（82页珍藏版）》请在金锄头文库上搜索。
1、第六章 二叉树和树,任务一 二叉树 任务二 树和森林,任务一 二叉树,子任务1 二叉树的概念和性质 子任务2 二叉树的存储 子任务3 二叉树的遍历 子任务4 哈夫曼树,子任务1 二叉树的概念和性质,1二叉树的概念 二叉树是由结点的有限集合构成，这个有限集合或者为空集，或者同时满足以下两个条件： (1) 有且仅有一个被称为根的结点； (2) 其余的结点被分为两个互不相交的子集T1和T2、，并且T1和T2都分别是二叉树，称为根的左子树和右子树。,图6-1、2即为一棵二叉树。,2.二叉树的相关术语,(1)结点 表示树中的元素，包括数据项及若干指向其子树的分支。 (2)结点的度 结点拥有的子树数。 (
2、3)叶子 度为0 的结点 。 (4)孩子 结点子树的根。 (5)双亲 孩子结点的上层结点。 (6)兄弟 同一双亲的孩子 。 (7) 二叉树的度 棵树中最大的结点度数 。 (8)结点的层次 从根结点算起，根为第一层，它的孩子为第二层。 (9)深度 树中结点的最大层次数 。,(10)满二叉树 如果一棵二叉树的所有分支结点都有左右两棵非空子树，且所有叶子结点都在同一层上，则这棵二叉树称作满二叉树，如图5-3(a)所示。 在满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树,且树叶都在最下一层上。 (11)完全二叉树 如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层
3、的结点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树，如图6-3(b)。 完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点个数恰是上一层结点的个数的2倍，,图6-3 满二叉树和完全二叉树示例,3二叉树的五个性质,性质1 在一棵非空二叉树中，第i层上最多有2i-1个结点（i=1） 证明：利用数学归纳法 （1）当i = 1时，20 = 1，只有一个根结点，正确。 （2）现在假设对所有的j，1=j=i，命题成立，即第j层上最多有2j-1个结点。下面证明当就j = i时结论也成立。由归纳假设，第i-1层上最多有2i-2个结点。由于二叉树每个结点的度数最大为2，所以第i层上的最大结点
4、数为第i-1层上的最大结点数的2倍，即2i-1个。,性质2 一棵深度为K(K=1)的二叉树最多有2k-1个结点（其中深度为二叉树中层数最大的叶子结点的层数）。 证明：由性质1可知，第i层的最大结点数为2i-1，所以,性质3 对于任何一棵非空的二叉树，若度为2的结点数为n2，则叶子结点数(度为0的结点数)n0=n2+1。 证明：设n1为二叉树T中度为1的结点数。 因为二叉树中所有结点的度均小于或等于2，所以其结点总数为： n=n0+n1+n2 又因为二叉树中，除根结点外，其余结点都只有一个分支进入，设B为分 支总数，则可得： n=B+1 由于分支是由度为1和度为2的结点射出，所以可得： B=n1
5、+2n2 由上面的等式左右分别相加后整理可得： n=B+1=n1+2n2+1=n0+n1+n2 故推出结果： n0=n2+1,性质4 具有n个结点（n0）的完全二叉树的深度为log2 (n+1) (其中 x 表示“不大于x的最大整数”) 证明：假设深度为k，则根据性质2和完全二叉 树的定义，有如下式子成立： 2k-1 -1n=2k-1 不等式中各项取对数，于是得到 k-1 log2 (n) =k 。因为k为整数，所以k 为不大于log2 (n)的最大整数+1即 klog2 (n) 。,性质5 如果将一棵具有n个结点的完全二叉树，如果按从上至下和从左到右的顺序对其所有结点从1开始进行编号，则对任
6、一编号为i(0in)的结点X有： (1)若i=1,则结点X是根，无双亲结点,若i1,则X的双亲结点的编号为i/2。 (2)若2in,则结点x无左孩子结点(且无右孩子结点)；否则X的左孩子结点的编号为2i。 (3)若2i+1n，则结点无右孩子结点；否则，的右孩子结点的编号为2i+1。,证明：这里证明(2)，(1) 和(3)即可由结论(2)推得。 对于i = 0，由完全二叉树的定义，其左孩子的编号是1，如果1n-1，即不存在编号为1的结点，此时结点i没有左孩子。其右孩子的编号只能是2，如果2n-1，此时结点i没有右孩子。 对于i0分两种情况讨论： (1) 设第j层的第一个结点编号为i(此时有i =
7、 2j-1)，则其左孩子必为第j + 1层的第一个结点，其编号为2j+1 - 1 = 2i + 1，如果2i + 1 n - 1，那么i没有左孩子；其右孩子必为第j + 1层第二个结点，其编号为2i + 2。 (2) 假设第j层的某个结点编号为i，若它有左孩子，那么它的左孩子必然是第j + 1层中的第2i - (2j - 1)个，那么其左孩子的编号就是2j + 1 - 1 + 2i - (2j - 1) = 2i + 1；如果结点i有右孩子，那么其右孩子的编号必是2i + 2。,子任务2 二叉树的存储,二叉树通常有两类存储结构 1、顺序存储结构； 2、链式存储结构；,二叉树的顺序存储结构,二叉
8、树的顺序存储是指按照一定次序，用一组地址连续的存储单元存储二叉树上的各个结点元素。 对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。如图6-4(a)表示的一棵完全二叉树，若将其编号为i的结点存入一维数组的第i个单元，其对应的存储结构如图6-4 (b)所示。,假如二叉树不是完全二叉树，首先必需将其转化为完全二叉树， 这一目标可通过在非完全二叉树的“残缺”位置上增设“虚结点”而达到。例如，图6-5(a)所示为一非完全二叉树，在二叉树上增加一些“虚结点”（用阴影表示）从而将其转化成一棵完全二叉树，如图6-5(b)所示。对得到的完全二叉树重新按层编号，然后再
9、按编号将各结点存入数组。各个“虚结点”在数组中用一个特殊记号来表示。在这一顺序存储结构上，可以用与完全二叉树上类似的方法实现二叉树数据结构的基本运算。,显然，上述方有可能造成存储空间的浪费。故二叉树的顺序存储结构一般只适用于一些特殊场合。,2、二叉树的链式存储结构,所谓链式存储方式，是指二叉树的各结点随机的存储在内存空间中，结点之间的关系用指针表示。 二叉树的链表的结点包含三个域：数据域和左、右指针域，其结点形式如下所示： Lchild data rchild,其中，date域称为数据域，用于存储二叉树结点中的数据元素，lchild域称为左孩子指针域，用于存放指向本结点左孩子的地址(简称为左指
10、针)。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的地址(简称为右指针)。 图6-6(a)、(b)分别表示一棵二叉树及其相应的二叉链表存储结构。,【案例】二叉树的链式存储结构为基础创建一棵二叉树，并实现其基本操作。,二叉链表的存储结构的表示如下： class TreeElem /二叉树结点类 public: char Data; /数据域 TreeElem* LChild;/左孩子指针 TreeElem* RChild;/右孩子指针 ;,class BiTree /二叉树类 private: int ElemNo; /二叉树中结点的个数 TreeElem TreeE6; /
11、TreeElem的数组 public: TreeElem* root; /根结点的指针 void CreatBiTree();/二叉树的建立函数 void PreOrderBiTree(TreeElem* Tree); /先序遍历函数 void InOrderBiTree(TreeElem* Tree); /中序遍历函数 void PostOrderBiTree(TreeElem* Tree); /后序遍历函数 void PreOrderBiTreeNo(TreeElem* Tree);/先序遍历，并统计结点个数 void InOrderBiTreeNo(TreeElem* Tree);/中序
12、遍历，并统计结点个数 void PostOrderBiTreeNo(TreeElem* Tree);/后序遍历，并统计结点个数 ;,void BiTree:CreatBiTree() /二叉树的建立函数 int l,r,rt; for(int i=0;iTreeEi.Data; coutl; if(l=-1) TreeEi.LChild=NULL; else TreeEi.LChild= ,子任务3 二叉树的遍历,二叉树的算法主要有： 1、二叉树的遍历算法： 前序遍历；中序遍历；后序遍历 2、由遍历序列恢复二叉树,1二叉树的遍历算法,所谓的遍历就是按某种次序“访问”二叉树上的所有结点，并使每一
13、个结点恰好被访问一次。 所谓“访问”一个结点，是指根据要求对该结点的数据域进相应的处理。,由定义可知，一棵二叉树由三部分组成：根、左子树和右子树。因此对于二叉树的遍历也可相应地分解成部分： 访问根结点; 遍历左子树(即依次访问左子树上的全部结点); 遍历右子树(即依次访问右子树上的全部结点)。 因为左、右子树都是二叉树（可以是空二叉树），对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。,如果限定“先左后右”的规则，则有三种遍历次序, 定义如下。 (1)先根遍历 若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作： 访问根结点; 先根遍历左子树; 先根遍历右子树。,(2)
14、中根遍历 若需遍历的二叉树为空,执行空操作；否则，依次执行下列操作： 中根遍历左子树； 访问根结点； 中根遍历右子树。,(3)后根遍历 若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作： 后根遍历左子树； 后根遍历右子树; 访问根结点。,【案例】给定一棵二叉树，分别写出对应的三种遍历序列。,对图6-7(a)所示的二叉树进行三种遍历，得到的结点访问序列为： 先根遍历序列为A、B、D、E、H、I、J、K、C、F、G； 中根遍历序列为D、B、H、J、I、K、A、F、C、G； 后根遍历序列为D、H、J、K、I、E、B、F、G、C、A。,为了写出各遍历序列，采用“分步填空”的方式,把整个二叉树分
15、成三步分，即根结点、左子树和右子树，由于左右子树是一个集合，故可以用一个空来表示，等待下一步继续分解，如此反复进行，直到所有的结点都找到确切的位置为止。,（1）先根遍历 A A B C A B D E C F G A B D E I C F G A B D E H I J K C F G,图6-7(a)所示的二叉树求解格式如下：,（2）中根序列 A B A C D B E A F C G D B H E I A F C G D B H E J I K A F C G,（3）后根遍历 A B C A D E B F G C A D H I E B F G C D H J K I E B F G C A,对图6-7(b)所示的二叉树进行三种遍历，得到的结点访问序列为：,先根序列是：A B D E G C F H I； 中根序列是：D B G E A C H F I； 后根序列是：D G E B H I F C A 。,图6-8是表达式A+B(C+D)的二叉树表示,二叉树的遍历算法与表达式的“前缀”和“后缀”表示法之间有着密切的联系。,按照前根方式遍历，运算符出现在前面，参与运算的对象紧跟在其后，这样就形成了前缀表达式（波兰式）： + A B + C D 按照中根方式遍历，得到的结果是去掉括号的中缀表达式： A + B C + D 按照后根方式遍历的结
