数据结构树和二叉树.ppt

第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.1 树的定义和基本术语 1.树的逻辑定义 是由n(n 0)个结点组成的有限集合T。 在任意一个非空树中： 有且仅有一个特定的称为根的结点； n 1时，其余结点可以分为m（m 0）个 互不相交的有限集T1,T2,T3 ,Tm，其中每一个集 合本身又是一棵树，且称为根的子树。 树的结构定义是一个递归的定义，即在树的定 义中又用到树的概念，它说明了树的特性。 如在右图中， 是只有一个根结点的树 是有13个结点的树 其中A是根，其余结点 分成三个互不相交的子集：T1=B，E，F，K，L, T2=C，G, T3=D，H，I，J，M； T1,T2,T3 都是A的子树，且本身也是一棵树。 则同理按此分析方式分析 T1 ,T2,T3。 AA BCD EFGHIJ KLM 2.树的其它表示方法 嵌套集合：是一些集合的集体，对于其中任何两个集合， 或不相交，或一个包含另一个的形式表示。 广义表表示：根作为由子树森林组成的表的名字写在表的 左边。 凹入表示：类似书的编目。 G C A B D H I J E K F L A* B* E* F* K* L* C* G* D* H* I* J* (A(B(E, F(K,L), C(G), D(H, I, J) A BCD EFGHIJ KL 3.树的基本术语 结点：数据元素+若干指向其子树的分支； 结点的度：结点拥有的子树数； 树的度：树中所有结点的度的最大值； 叶子结点：度为零的结点，或称为终端结点； 分支结点：度大于零的结点，或称为非终端结点； 结点的层次：假设根结点的层次为1, 若某结点在 第i层，则其子树的根在第i+1层； A BD EFHIJ KM 树的深度：树中叶子结点所在的最大层次； 孩子结点：结点的子树的根；相应地该结点称为孩 子的双亲结点； 兄弟结点：同一个双亲的孩子之间称为兄弟结点； 祖先：从根到该结点所经分支上的所有结点； 子孙：子树中任一结点； A BD EFHIJ KM 3.树的基本术语 有序树、无序树 子树之间是否存在次序关系？ 将树中结点的各子树看成从左至右是有次序的( 即不能互换) 称有序树，否则称无序树； 森林：是m（m0）棵互不相交的树的集合。 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root被称为根结点，F被称为子树森林； A BD EFHIJ KM 3.树的基本术语 4.树结构和线性结构的比较 第一个数据元素（无前驱） 最后一个数据元素（无后继） 其它元素（一个前驱、一个后继） 根结点（无前驱） 多个叶子结点（无后继） 其它结点（一个前驱、多个后继） 线 性 结 构 树结构 5.树的抽象类型定义 ADT List 数据对象D：是具有相同特性的数据元素的集合 数据关系R：数据关系R：若D为空集，则称为空树；若D仅 含一个数据元素，则R为空集，否则 R=H，H是如下二元 关系： (1) 在D中存在唯一的称为根的数据元素root，它在 关系H下无前驱； (2) 若D-root!=，则存在 D-root的一个划分 D1，D2，Dm (m0)，对任意jk(1j，km)有 DjDk=，且对任意的 i(1im)，唯一存在数据元素 xiDi，有H； 5.树的抽象类型定义 ADT List 数据关系R： (3) 对应于 D-root的划分，H-， 有唯一的一个划分 H1，H2，Hm(m0)， 对任意jk(1j，km)有 HjHk=，对任意 i(1im)，Hi是Di上的二元关系，(Di，Hi)是一棵符 合本定义的子树，称为根root的子树。 基本操作： ADT List 树的基本操作 1）Root(T);初始条件：树T存在；操作结果：返回T的根 2）Value(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：返回cur_e的值 3）Parent(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双 亲，否则其函数值为“空”。 4）TreeDepth(T); 初始条件：树T存在；操作结果：返回T的深度。 5）LeftChild(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的最 左孩子，否则其函数值为 “空” 6）RightSibling(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：若cur_e有右兄弟，则返回它的右兄弟， 否 则其函数值为“空” 7）TreeEmpty(T); 初始条件：树T存在 操作结果：判别T是否为空树 8) TraverseTree(T, Visit(); 初始条件：树T存在。Visit是对结点操作的函数。 操作结果：按某种次序对T的每个结点调用函数 Visit()一次且至多一次 9）InitTree( 操作结果：构造空树T 10）Assign( 初始条件：树T存在， cur_e是T中某个结点。 操作结果：结点cur_e赋值value。 11）DestroyTree( 初始条件：树T存在 操作结果：销毁树T 第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.2.1 二叉树的定义 或者为空树；或者是由一个根结点加上两棵 分别称为左子树和右子树的、互不相交的二叉树 组成。二叉树的结点的子树要区分左子树和右子 树，即使在结点只有一棵子树的情况下也要明确 指出该子树是左子树还是右子树。 二叉树的五种基本形态 二叉树的常用操作 某些操作和树的基本操作类似，另由于二叉树本身特 性，增加的操作有： RightChild(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：返回e的右孩子，否则其函数值为“空” 。 LeftSibling(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：返回e的左兄弟，若e是T的左孩子或无左 兄弟，则返回“空”。 PreOrderTraverse(T, Visit(); 先序遍历 InOrderTraverse(T, Visit(); 中序遍历 PostOrderTraverse(T, Visit(); 后序遍历 LevelOrderTraverse(T, Visit();层序遍历 6.2.2 二叉树的性质 性质1： 在二叉树的第i层上至多有2i-1个结点（i1） （利用归纳法容易证得此性质） 4 23 1 567 89101112131415 性质2： 深度为K的二叉树上至多含2K-1个结点（K1） （证明用求等比级数前k项和的公式） 1 2 3 4 4 23 1 567 89101112131415 性质3： 对任一棵二叉树，若它含有n0 个叶子结点， n2 个度为 2 的结点，则必存在关系式： n0 = n2+1 证明： 设二叉树上结点总数 n = n0 + n1 + n2 又二叉树上分支总数 B = n1 + 2n2 而 B = n - 1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 23 1 45 6789 满二叉树：深度为k且含有2k-1个结点的二叉树 4 23 1 567 89101112131415 4 23 1 567 8 完全二叉树：树中所含的n个结点和满二叉树 中编号为1至n的结点一一对应。 4 23 1 567 891011 1213 1415 4 23 1 567 891011 (a ) (b ) (c ) 完全二叉树的特点 (1) 叶子结点只可能在层次最大的两层上出现； (2) 对任一结点，若其右分支下的子孙的最大层 次为 L，则其左分支下的子孙的最大层次必 为 L 或 L+1。 性质4：具有n个结点的完全二叉树的高度为 log2n + 1 4 23 1 567 89101112 证明： 设完全二叉树的高度为h，则有 (2h-1 -1 ) n，则该结点无左孩子，否则，编号 为2i的结点为其左孩子结点； 若2i+1 n，则该结点无右孩子结点，否则 ，编号为2i+1的结点为其右孩子结点。 4 23 1 567 89101112 6.2.3 二叉树的存储结构 （1）二叉树的顺序存储表示 （2）二叉树的链式存储表示 1.二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt; 按照顺序存储结构的定义，在此约定，用一 组地址连续的存储单元依次自上而下、自左至右 存储完全二叉树上的结点元素，即将完全二叉树 上编号为 i的结点元素存储在如上定义的一维数 组中下标为 i-1 的分量中。 4 23 1 567 89101112 123456789101112 数组下标：0 1 2 3 4 5 6 7 8 9 10 11 23 1 456 78 123045600708 一般二叉树必须按完全二叉树的形式存储， 将造成存储的浪费。 顺序存储结构的性能分析 顺序存储结构仅适用于完全二叉树。 因为，在最坏的情况下，一个深度为k且只有 k个结点的单支树（树中不存在度为2的结点） 却需要长度为2k-1的一维数组。这样就造成存 储空间的浪费。 30 11 55 66 0 2 6 14 红字为对应结点在顺序 结构中相应的位置下标 2.二叉树的链式存储结构 由二叉树的定义得知，二叉树的结点由一个 数据元素和分别指向其左、右子树的两个分支构 成，则表示二叉树的链表中的结点至少包含三个 域：数据和左、右指针域。 DATA LChildRChild Parent 二叉树的结点 D B C EF A E C B D F 二叉链表 lchildDatarchild A 二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; / 左右孩子指针 BiTNode, *BiTree; parent A E C B D F 三叉链表rchildDatalchild B D C E F A 二叉树的三叉链表存储表示 typedef struct TriTNode TElemType data; struct TriTNode *lchild,*rchild; / 左右孩子指针 struct TriTNode *parent; / 双亲指针 TriTNode, *TriTree; 在不同的存储结构中，实现二叉树的操作方 法亦不同，如找结点 x 的双亲 PARENT(T，e)， 在三叉链表中很容易实现，而在二叉链表中则需 从根指针出发巡查。 由此，在具体应用中采用什么存储结构，除 了根据二叉树的形态之外，还应考虑需进行何种 操作。 总结 本讲我们学习了树和二叉树的定义，重点介 绍了二叉树的性质和存储结构，二叉树是非常重 要的数据结构，请同学们重点掌握，在下一讲中 我们将学习二叉树的遍历和线索化操作。 练习题 1. 假设在树中，结点x是结点y的双亲时，用(x,y) 表示树边。已知一棵树边的集合为 (i,m),(i,n), (e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g), (c,f),(h,l),(c,h),(a,c)，用树形表示法画出此 树，并回答：(1)哪个是根结点? (2)哪是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些 是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄 弟?哪些是f的兄弟? (8)结点b和n的层次各是多少? (9)树的深