《数据结构课件(树和二叉树)》由会员分享，可在线阅读，更多相关《数据结构课件(树和二叉树)（93页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 1数据结构第六章 树和二叉树 *第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 2ABCDEFGHIJKLM树第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码
2、 36.1 树的类型定义数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树；否则: （1）在D中存在唯一的称为根的数据元素root, （2）当n1时，其余结点可分为m(m0)个互不相交的 有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵符 合本定义的树，称为根root的子树。 基本操作： 查找：Root(T); Value(T, cur_e); Parent(T, cur_e);LeftChild(T, cur_e); TreeEmpty(T); TreeDepth(T); TraverseTree(T, Visit( );第六章第六章6.1 树的
3、类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 46.1 树的类型定义插入：InitTree( CreateTree(Assign(T, cur_e, value);InsertChild(删除：ClearTree( DestroyTree(DeleteChild(DestroyTree(第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 56.1 树的类型定义
4、和线性结构的比较 线性结构 树结构第一个数据元素(无前驱)； 根结点(无前驱)；最后一个数据元素(无后继)； 多个叶子结点(无后继)；其它数据元素 树中其它结点(一个前驱、一个后继) 。 (一个前驱、多个后继)。第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 6ABCDEFGHIJKLM树形表示A (B (E (K, L), F), C(G ), D( H( M), I, J) 嵌套括号表示法树的表示方法：IJFKLGMCCDBEA文氏图凹入表A BF EK L
5、C DH IGM J第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 7基本术语结点: 数据元素 + 若干指向子树的分支。 结点的度: 分支的个数。 树的度: 树中所有结点的度的最大值。 叶子结点: 度为零的结点。 分支结点: 度大于零的结点； 路径和路径长度。 孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点 、子孙结点。 边：双亲节点x到子结点y的有序对(x，y)。 结点的层次: 假设根结点的层次为1，第i 层的结点的 子树根结点的层次为i+1。规定根的层数为0。
6、 树的深度：树中叶子结点所在的最大层次。 森林：是m（m0）棵互不相交的树的集合任何一棵 非空树是一个二元组Tree = （root，F）其中： root被称为根结点，F被称为子树森林。第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 86.2 二叉树的类型定义二叉树的定义定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。与树的关系：这也是一个递归定义。区别： 二叉树结点的子树要
7、区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 9(a)空二叉树A(b) 根和空的 左右子树AB(c) 根和左子树二叉树的5种基本形态A(d) 根和右子树BA(e) 根和左右子树BC第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 10二叉树的主要基本操作：查
8、找：Root(T); Value(T, e);Parent(T, e);LeftChild(T, e); RightChild(T, e);LeftSibling(T, e); RightSibling(T, e);BiTreeEmpty(T); BiTreeDepth(T);PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit();PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); 插入：InitBiTree( Assign(T, CreateBiTree(Insert
9、Child(T, p, LR, c); 删除：ClearBiTree( DestroyBiTree(DeleteChild(T, p, LR); 第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 11性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。证明：采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定第i1层上命题成立，则第i1层上至 多有2i-2个结点。由于二叉树每个结点的度最大为2， 故在第i层上最大结点
10、数为第i1层上最大结点数的二 倍， 即22i-22i-1。 命题得到证明。二叉树的重要特性：第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 12性质2：深度为k的二叉树至多有2k1个结点（k=1).证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2i-1（第i层上的最大结点数）二叉树的重要特性：第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索
11、二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 13二叉树的重要特性：性质3： 对任何一棵二叉树，如果其终端结点数为n0，度 为2的结点数为n2，则n0n21。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点 数为N，因为二叉树中所有结点均小于或等于2，所以有 ： Nn0n1n2 （1）再看二叉树中的分支数，除根结点外，其余结点都 有一个进入分支，设B为二叉树中的分支总数， 则有：N B1。由于这些分支都是由度为1和2的结点射出的， 所以有：Bn1+2*n2 NB1n12n21 （2) 由式（1）和（2）得到：n0+n1+n2=n1+2*n2+1n0n21第六章第六章6.1
12、树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 14满二叉树2453671123456(a)完全二叉树123457(b)非完全二叉树12367( c)非完全二叉树第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 15两种特殊形态的二叉树：一棵深度为k且由2k-1个结点的二叉树称为满二叉树 。 如果深度为k、由n个结点的二叉树中各结点能够与深 度为k的顺序编
13、号的满二叉树从1到n标号的结点相对应 ，则称这样的二叉树为完全二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为h，则 其左子树的最大层次为h或h1。满二叉树和完全二叉树第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 16性质4：具有n个结点的完全二叉树的深度为log2n1。符号x表示不大于x的最大整数。证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-111，则其双亲是结点
14、i/2。（2）如果2in，则结点i为叶子结点，无左孩子；否 则，其左孩子是结点2i。（3）如果2i1n，则结点i无右孩子；否则，其右孩 子是结点2i1。证明：略！完全二叉树的特点:第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 186.3 二叉树的存储结构1.顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素 。因此，必须把二叉树的所有结点安排成为一个恰当的 序列，结点在这个序列中的相互位置能反映出结点之间 的逻辑关系，用编号的方法：#define max-
15、tree-size 100 Typedef telemtype sqbitreemax-tree-size; Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有 结点编号。第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 19 L K J I H G F E D C B A1 2 3 4 5 6 7 8 9 10 11 12完全二叉树ABCDEFGHIJKL第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 20ABCDEFG 表示该处没有元素 存在仅仅为了好理解ABCDEFG一般二叉树第六章第六章6.1 树的类 型定义6.2 二叉树 的类型定义6.3 二叉树 的存储结构6.4 二叉树 的遍历6.5 线索二 叉树6.6 树和森 林6.7 哈夫曼 树与哈夫曼 编码 211.顺序存储结构缺点：有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若
