数据结构第04章树和二叉树.ppt

第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用;6.1 树的定义和基本术语;如在右图中， ? 是只有一个根结点的树 ? 是有13个结点的树 其中A是根，其余结点 分成三个互不相交的子集：T1={B，E，F，K，L}, T2={C，G}, T3={D，H，I，J，M}； T1,T2,T3 都是A的子树，且本身也是一棵树。则同理按此分析方式分析 T1 ,T2,T3。;2.树的其它表示方法 嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。 广义表表示：根作为由子树森林组成的表的名字写在表的左边。 凹入表示：类似书的编目。;3.树的基本术语;树的深度：树中叶子结点所在的最大层次； 孩子结点：结点的子树的根；相应地该结点称为孩子的双亲结点； 兄弟结点：同一个双亲的孩子之间称为兄弟结点； 祖先：从根到该结点所经分支上的所有结点； 子孙：子树中任一结点；;有序树、无序树 子树之间是否存在次序关系？ 将树中结点的各子树看成从左至右是有次序的(即不能互换) 称有序树，否则称无序树； 森林：是m（m≥0）棵互不相交的树的集合。 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root被称为根结点，F被称为子树森林；;4.树结构和线性结构的比较 ;5.树的抽象类型定义;5.树的抽象类型定义;树的基本操作;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); 操作结果：构造空树T 10）Assign(T, cur_e, value); 初始条件：树T存在， cur_e是T中某个结点。 操作结果：结点cur_e赋值value。 11）DestroyTree(T); 初始条件：树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 二叉树的性质;性质2： 深度为K的二叉树上至多含2K-1个结点（K≥1） （证明用求等比级数前k项和的公式）;性质3： 对任一棵二叉树，若它含有n0 个叶子结点，n2 个度为 2 的结点，则必存在关系式： n0 = n2+1;满二叉树：深度为k且含有2k-1个结点的二叉树;完全二叉树：树中所含的n个结点和满二叉树 中编号为1至n的结点一一对应。;