第6章 树 (后半部分).ppt

Chapter 6 树和二叉树 6.1树的基本定义 树的基本定义 树是由有限个（n个）相同结点构成的集合。如果n=0，称为空树；如果n0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 如果和线性表相对比，则树 有一个根节点，它没有前驱 有多个尾节点，它们没有后继 对于其他节点，有唯一的前驱和不止一个的后继 树的基本定义 树的基本术语 树的基本操作 课本P118 森林 有m(m=0)棵互不相交的树构成的集合。 6.2二叉树的基本定义与性质 二叉树的定义 二叉树是一种特化的树。 首先它是一棵树，其元素遵从树的定义。 特化体现在结构方面，每个节点至多只有两个子树，并且子树是有顺序的，不能颠倒。 二叉树的定义 与树类似，二叉树也有一个递归的定义。 二叉树或者为空，或者是由一个根节点加上两棵分别成为左子树和右子树的、互不相交的二叉树组成。并且这两棵子树也是二叉树。 二叉树的五种形态。 二叉树的定义 思考：如何递归的定义一个线性表？ 二叉树的基本操作 课本P121 二叉树的性质 性质1：在二叉树的第i层上至多有 2^(i－1)个结点。(i?1) 二叉树的性质 性质2：深度为 k 的二叉树至多有2k-1个结点(k?1)。 二叉树的性质 性质3：对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0＝n2＋1. 二叉树的性质 新的定义： 满二叉树 完全二叉树 二叉树的性质 完全二叉树： 课本定义，P124 更直观的定义：若设二叉树共有h层。除第 h 层外，其它各层 (0 ? h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树 二叉树的性质 二叉树的性质 性质4：具有 n (n ? 0) 个结点的完全二叉树的深度为?log2(n)?＋1 6.3二叉树的物理实现 二叉树的顺序存储 用一组连续的地址自上而下、自左至右的存储二叉树的节点，并且将节点与完全二叉树对照，不存在节点存为特定的标志值。 二叉树的顺序存储 二叉树的链式存储 二叉链表 回忆：链表的节点，由一个数据域和一个指针域组成。 二叉树每个节点至多有两个子树，则可以由一个数据域和两个指针域构成。 二叉树的链式存储 二叉树的链式存储 某些特定问题中，为了能够方便的访问上层节点，也可以再加入一个指针域。 二叉树的链式存储 二叉树的链式存储 二叉链表的类型定义。 课本P127 用BiTree代表一棵二叉树，它实际上是一个指向树的根节点的指针（与链表类似）。 树的某个节点：BiTNode T; 指向树某个节点的指针：BiTNode *T,BiTree *T 节点的左子树：T-lchild 节点的右子树：T-rchild 6.4二叉树的遍历 二叉树的遍历 遍历：按某种次序访问数据结构中的元素，要求每个元素访问一次且仅访问一次。 线性表的遍历：有一定的方向，很容易实现。 树的遍历：难点在于确定访问的顺序。 二叉树的遍历 二叉树常用的四种遍历方法 先序。 中序。 后序。 层序。 二叉树的先序遍历 二叉树的先序遍历 如果二叉树为空，则什么都不做。 如果二叉树不为空，则 访问根节点 先序遍历左子树 先序遍历右子树 先序遍历是一个递归的过程，因为在描述这个过程时使用了它本身。 二叉树的先序遍历 先序遍历示例 访问根节点 A 先序遍历节点A的左子树 节点A左子树的根节点 B 先序遍历节点B的左子树 节点B左子树的根节点 D 先序遍历节点D的左子树 空，直接结束 先序遍历节点D的右子树 空，直接结束，至此对节点B左子树的遍历结束。 二叉树的先序遍历 先序遍历示例 先序遍历节点B的右子树 节点B右子树的根节点 E 先序遍历节点E的左子树 空，直接结束 先序遍历节点E的右子树 空，直接结束，至此对节点B右子树的遍历结束。同时：对节点A的左子树的遍历也已经完成。 二叉树的先序遍历 先序遍历示例 先序遍历节点A的右子树 节点A右子树的根节点 C 先序遍历节点C的左子树 空，直接退出，对节点C左子树的遍历完成。 先序遍历节点C的右子树 节点C右子树的根节点 F 先序遍历节点F的左子树 空，直接结束 先序遍历节点F的右子树 空，直接结束，遍历全部结束 二叉树的先序遍历 先序遍历较复杂的例子 - + a * b - c d / e f 二叉树的中序遍历 二叉树的中序遍历 如果二叉树为空，则什么都不做。 如果二叉树不为空，则 中序遍历左子树 访问根节点 中序遍历右子树 中序遍历仍然是递归进行的 二叉树的中序遍历 中