数据结构__树和叉树.pptVIP

第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 6.7 回溯法与树的遍历 6.8 树的计数 6.1 树的定义和基本术语 6.1.1 树的定义 6.1.2 树的表示方法 6.1.3 基本术语 6.1.1 树的定义 定义 树是n（n≥0）个结点的有限集。 在任意一棵非空树中： （1）有且仅有一个特定的称为根的结点； （2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。 6.1.1 树的定义 树的示例 树的抽象数据类型 ADT Tree{ 数据对象 D D是具有相同特性的数据元素的集合 数据关系 R： 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, …, Tm，其中每 一棵子集本身又是一棵符合本定义的树， 称为根root的子树。 树的抽象数据类型 基本操作： （1）初始化操作。 （2）求根函数。 （3）求双亲函数。 （4）求孩子结点函数。 （5）求右兄弟函数。 （6）建树函数。 （7）插入子树操作。 （8）删除子树操作。 （9）遍历操作。 （10）清除结构操作。 }ADT Tree 6.1.2 树的表示方法 6.1.2 树的表示方法 6.1.3 基本术语 结点：数据元素+若干指向子树的分支 结点的度：分支的个数 树的度：树中所有结点的度的最大值 叶子结点(终端结点)：度为零的结点 分支结点(非终端结点)：度大于零的结点 (从根到结点的)路径：由从根到该结点所经 分支和结点构成。 6.1.3 基本术语 6.1.3 基本术语 6.1.3 基本术语 有向树： (１) 有确定的根； (２) 树根和子树根之间为有向关系。 6.1.3 基本术语 有序树： 子树之间存在确定的次序关系。 无序树： 子树之间不存在确定的次序关系。 6.1.3 基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.2.1 二叉树的定义 定义：每个结点至多只有两颗子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 抽象数据类型二叉树的定义 ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=Φ，则R=Φ，称BinaryTree为空二叉树； 若D≠Φ，则R={H}，H是如下二元关系： （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root} ≠Φ,则存在D－{root}＝{Dl,Dr},且Dl∩Dr＝Φ； 抽象数据类型二叉树的定义 （3）若Dl ≠Φ，则Dl中存在惟一的元素xl， root, xl ∈H，且存在Dl上的关系Hl,∈H；若Dr ≠Φ，则Dr 中存在惟一的元素xr， root,xr∈H，且存在Dr上的关系Hr∈H；H＝{root,xl, root,xr,Hl,Hr}； （4） (Dl,{Hl})是一棵符合本定义的二叉树，称为左子树， (Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 基本操作P：查找；插入；删除 }ADT BinaryTree 6.2.1 二叉树的定义 二叉树的五种基本形态： 6.2.2 二叉树的性质 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点 (i≥1) 。 6.2.2 二叉树的性质 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。 6.2.2 二叉树的性质 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。 两类特殊的二叉树： 完全二叉树？ 6.2.2 二叉树的性质 性质 4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n ? + 1 。 6.2.2 二叉树的性质 性质 5 ： 若对有n个结点的完全二叉树从 上到下、从左至右进行1至n的 编号，则对任一个结点i 有： (1) 若i=1，则结点i是二叉树的根，无双亲， 否则，其双亲为结点?i/2? ； (2) 若2in，则结点i (叶子结点)无左