《第六章 Part1(树的基本概念和二叉树遍历)》由会员分享，可在线阅读，更多相关《第六章 Part1(树的基本概念和二叉树遍历)（9页珍藏版）》请在金锄头文库上搜索。
1、18-Nov-07 1第六章 二叉树和树 树是一类重要的 非线性数据结构 ，是以分支关系定义的层次结构 典型例子：z 企业的管理机构z 计算机文件系统8-Nov-07 2本讲重点难点 基本内容z 二叉树的定义性质存储结构z 二叉树遍历和线索化z 树和森林、存储结构、树的多种应用 重点难点z 二叉树结构特性及证明方法z 二叉树各种存储结构的特点及适用z 二叉树遍历z 建立huffman树z 基于二叉链表表示的二叉树的算法8-Nov-07 3第一节 树的定义 树 (Tree)的定义z 树是由 n (n 0)个节点组成的有限集合。z 如果 n = 0，称为空树；z 如果 n 0，则 :有且仅有一个特
2、定的称之为 根 (root)的节点，它只有直接后继，但没有直接前驱；z 如果 n1，则：除根以外的其它节点可以划分为 m (m0)个互不相交的有限集合 T0, T1, , Tm-1，每个集合又是一棵树，并且称为根的 子树 (subTree)。每棵子树的根节点有且仅有一个直接前驱，但可以有 0个或多个直接后继。 特点：z 非空的树至少有一个根节点z 树中各子树是互不相交的集合8-Nov-07 4树的示例子树根A只有根节点的树AB C DE F G H I JK L M普通的树T1T2T38-Nov-07 5树的基本术语 节点 (node)：树中的元素。包含一个数据元素及若干指向其子树的分支 节点
3、的度( degree)：节点的分支数目 分支 (branch) 节点 ：度不为0的节点 叶 (leaf)（终端）节点：度为0的节点 树的度 ：树中所有节点度的最大值 孩子(child)与双亲(parent) 节点 ：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲AB C DE F G8-Nov-07 6树的基本术语（续） 兄弟 ( sibling)：同一个双亲的孩子之间互称兄弟。 祖先 (ancestor) ：从根节点到某个节点所经分支上的所有节点。 子孙（ descendant) ：以某个节点为根节点的子树中的所有节点均是该节点的子孙。 节点所处层次 (level) ：根为第一层，根的
4、孩子为第二层，依此类推。 堂兄弟 ：双亲在同一个层次上的节点互为堂兄弟。 树的深度 (depth)（高度） ：树中所有节点层次的最大值。AB C DE F G28-Nov-07 7树的基本术语 （续） 有序树 与 无序树 ：树的各个子树从左至右的顺序不可以调换则称为有序树，否则为无序树。 森林（Forest）：m(m0)棵互不相交的树的集合称为森林。 对树中每个节点而言，其子树的集合就构成森林。8-Nov-07 8树的基本术语举例12344节点A的度：3节点B的度：2节点M的度：0叶子：K，L，F，G，M，I，J节点I的双亲：D节点L的双亲：E树的度：3 树的深度：4节点B，C，D为兄弟节点K
5、，L为兄弟节点E，G，H为堂兄弟节点A，D，H是M的祖先8-Nov-07 9树的抽象数据类型 数据对象 D：D是具有相同特性的数据元素的集合。 数据关系 R：z 如果 D为空集，则称为空树；z 如果 D中只有一个元素，则 R为空集 ;z 否则 R=H， H是满足以下条件的二元关系：z (1) 在 D中存在唯一的称为根的数据元素 root，它在关系 H下无前驱；z (2) 若 D-root=, 则存在 D-root上 的一个划分D1,D2,Dm m0，对任意 j k(1 j,k m)有 Dj Dk= ，且对任意的 i(1 i m)，唯一存在数据元素xi(xi Di),，有 Hz (3) 对应于
6、D-root的划分， H , , , 有唯一的一个划分 H1,H2,Hm m0，对任意 j k(1 j,k m)有Hj Hk= ，且对任意的 i(1 i m)， Hi 是 Di 上的二元关系， (Di,Hi) 是一棵符合本定义的树，称为根 root的子树。8-Nov-07 10树的操作 初始化 InitTree(&T); 销毁树 DestroyTree(&T) 创建树 CreateTree(&T) 清空树 ClearTree(&T) 判断树是否为空 TreeEmtpy(T) 求树的深度 TreeDepth(T) 求树的根 Root(T) 求树上某个节点的值 Value(T, cur_e) 给树
7、上某个节点赋值 Assign(T, Cur_e, value) 返回某个节点的双亲 Parent(T, Cur_e)11 求某个节点的左孩子 LeftChild(T, Cur_e)12 求某个节点的右孩子 RightChild(T, Cur_e)13 求某个节点的右兄弟 RightSibling(T, Cur_e)14 在树中插入元素 InsertChild(&T, &p, i, c)15 删除树中的元素 DeleteChild(&T, &p, i)16 遍历树中所有元素 TranverseTree(T, Visit()8-Nov-07 11第二节 二叉树（Binary Tree） 二叉树的定
8、义 一棵二叉树是n(n0)个节点的有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的特点z 每个节点至多有二棵子树 (即不存在度大于 2的节点 )z 二叉树的子树有左、右之分，且其次序不能任意颠倒z 二叉树是一种 度为2的有序树8-Nov-07 12二叉树的五种不同形态 (a)空二叉树 (b)仅有根节点的二叉树 (c )右子树为空 (d)左子树为空 (e) 左右子树均非空38-Nov-07 13二叉树的抽象数据类型数据对象 D：D是具有相同特性的数据元素的集合。数据关系 R： 如果 D= ，则 R= 称为空二叉树；如果 D ，则 R=
9、H， H是满足以下条件的二元关系：(1)在 D中存在唯一的称为根的数据元素 root，它在关系 H下无前驱；(2)若 D-root , 则存在 D-root=Dl,Dr,且有Dl Dr= (3)如果 Dl ，则 Dl中存在唯一元素 xl， H，且存在 Dl上的关系 Hl H；如果 Dr ，则 Dr中存在唯一元素 xr， H,且存在 Dr上的关系 Hr H，并且有 H=, ,Hl ,Hr (4)(Dl,Hl)是一棵符合本定义的二叉树，称为根 root的左子树。 (Dr,Hr)是一棵符合本定义的二叉树，称为根 root的右子树8-Nov-07 14二叉树的操作 二叉树的操作同普通树的操作类似 二叉
10、树的遍历操作是最重要的操作 二叉树的遍历包括z 二叉树的先序z 中序z 后序遍历8-Nov-07 152 二叉树的重要特性 性质 1 在二叉树的第 i 层上至多有 2i-1(i 1) 个节点z 证明：第 1层只有 1个节点 1=21-1=20z 假定第 i层的节点个数为 2i-1z 那么由于二叉树每个节点最多有两个分支，因此第i+1层最多会有： 2 2i-1= 2i-1+1 = 2(i+1)-1个节点 性质 2 深度为 k 的二叉树至多有 2k-1 (k 1) 个节点z 证明：12211= kkii每层的最大结点数最大结点数8-Nov-07 16二叉树的性质(续)性质3 对任何一棵二叉树T，如
11、果其终端节点数为n0，度为2的节点数为 n2，则有：N0=n2+1证明： 若设度为1的节点有n1个，总节点个数为n，总分支数为B，则根据二叉树的定义，n = n0+ n1+ n2 （1）B = 2n2+ n1= n 1 （2）于是有： 2n2+ n1= n0+ n1+ n2- 1 n2= n0 1n0= n2+ 18-Nov-07 17几种特殊形式的二叉树 满二叉树(Full Binary Tree) 定义： 一棵深度为k，且有 2k-1 个节点的二叉树被称为满二叉树。 特点z 每一层的节点数目均达到了最大值z 可以对其按照从上到下，从左到右的原则进行连续编号 。8-Nov-07 18完全二叉
12、树 完全二叉树 (Complete Binary Tree) 定义： 深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应时，称之为完全二叉树。 完全二叉树的 特点 ：z 叶子节点只可能在层次最大的两层上出现；z 对任一节点，若其右分支下的子孙的最大层次为 L ，那么其左分支下的子孙的最大层次必为 L 或 L+1 。48-Nov-07 19满二叉树与完全二叉树图示8-Nov-07 20进一步解释完全二叉树 完全二叉树：若共有h层，除第h层外，其它各层(1h-1)的节点数都达到最大个数，第h层从右向左连续缺若干节点，这就是完全二叉
13、树。12 3114 58 9 12 136 710 14 1512 3114 58 9 126 71012 34 56 712 34 5 68-Nov-07 21完全二叉树的两个重要性质性质4 具有n个节点的完全二叉树的深度为符号 x表示不大于 x 的最大整数。 1log2+n证明：根据完全二叉树的定义，若深度为k,则有：1loglog12212122211+=1 ，则其双亲是节点是 i/2 。z 2）如果 2in ，则节点 i 无左孩子，否则其左孩子为2i z 3）如果 2i+1n ，则节点 i无右孩子，否则其右孩子为 2i+1 性质 5说明：在完全二叉树中，如果我们可以知道节点的编号就可以
14、用简单的数学运算来求出其双亲的位置。 性质 5的证明；可以先证明 2和 3，然后利用 2和 3的结论来证明 1。8-Nov-07 23性质5的证明 假定第i个节点位于第k层，根据二叉树的性质，那么前面k-1层总的节点个数为:2k-1-1个节点 第k层第一个节点的编号为2k-1-1+1= 2k-1,由此可以知道在第K层的第i个节点前面节点数目为：i- 2k-1 如果节点i有左孩子，根据完全二叉树的定义，那么第k层中在它前面的节点必然有左右孩子，这些孩子的总数目为：2（ i-2k-1）且位于第 k+1层 由于第K+1层第一个节点的编号为2k，那么第i个节点的左孩子的编号必然为： 2k+ 2（i-
15、2k-1） =2i，它的右孩子的编号则为 2+1.iK层2k-1K+1层2ii-2k-12k 2i+18-Nov-07 24第三节 二叉树的存储结构一 顺序存储结构 用一组 连续的存储单元依次自上而下、自左至右存储完全二叉树 中的所有元素。 特点：z 节点间关系蕴含在其存储位置中z 只适用于完全二叉树 ，对于普通的树，可能会造成严重的空间浪费。58-Nov-07 25顺序存储示例ab cd ef ga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 118-Nov-07 26顺序存储缺点 由于完全二叉树的节点数目与树的深度是指数关系，因此只要树的深度较大，所需要的空间是惊人的。单支树示例例：一个深度为 k (k=10) 的二叉树，如果用顺序存储结构来表示，需要2k-1(1023)个单元，而实际上树中的元素可能只有 100个 (单支树单支树 )。8-Nov-07 27顺序存储结构的C语言描述#define MAX_TREE_SIZE
