二级基础知识3.pptVIP

1.6 树和二叉树 1.6.1 树的基本概念 树的定义 树是由n (n ? 0)个结点组成的有限集合。如果n = 0，称为空树；如果n 0，则： ? 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； ? 除根以外的其它结点划分为m (m ? 0)个互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 1.6.4 二叉树的遍历 遍历:指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 “访问”的含义，如：输出结点的信息等。 “遍历”是任何类型均有的操作。 对线性结构而言，只有一条有哪些信誉好的足球投注网站路径(因为每个结点均只有一个后继)。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的有哪些信誉好的足球投注网站路径遍历的问题。 * * 思考：树与线性结构的区别？ 树的表示 树型表示 b a c g h d e f i j A B C F E D B A E D C F G 结点(node)： 数据元素 + 若干指向子树的分支 结点的度(degree)： 结点的子树个数 树的度(degree)： 树中所有结点的度的最大值 分支(branch)结点： 度不为0的结点 叶(leaf)结点： 度为0的结点 孩子(child)结点： 某结点子树的根结点 双亲(parent)结点： 某个结点是其子树之根的双亲 1 2 3 4 4 兄弟(sibling)结点 具有同一双亲的所有结点 祖先(ancestor)结点 从根到该结点所经分支上的所有结点。 子孙(descendant)结点 以某一结点 为根的子树中的任一结点。 结点所处层次(level) 根结点的层数为1，其余结点的层数为双亲结点的层数加1 树的深度(depth) 树中结点的最大层数 1.6.2 二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i-1 个结点。(i ? 0) 二叉树的性质 性质2 深度为k的二叉树最多有 2k-1个结点。 (k ? 1) 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0＝n2＋1 性质4 具有n个节点的二叉树， 其深度至少为[log2n]+1 定义1 满二叉树(Full Binary Tree) 一棵深度为k 且有2k-1个结点的二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1?h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。 4 1 2 3 5 6 1 2 3 6 7 (a)完全二叉树 1 2 3 4 5 7 (b)非完全二叉树 ( c)非完全二叉树 2 4 5 3 6 7 1 满二叉树 性质5 具有n个结点的完全二叉树的高度 为 log2n +1 完全二叉树的性质 性质6 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 ? i ? n)。则有以下关系： 若i =1, 则 i 无双亲 若i 1, 则 i 的双亲为?i /2? 若2*i = n, 则 i 的左子女为2*i；否则，i无左子女，必定是页结点，二叉树中i ? n/2? 的结点必定是页结点 若2*i+1 = n, 则 i 的右子女为2*i+1，否则，i无右子女 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。 1.6.2 二叉树的链式存储结构 二叉树链表表示的示例 若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则