数据结构-吴跃-ch3.ppt

;第3章 树;树是非常重要和经常使用的一类非线性结构 ，树中的数据元素之间按某种规定存在一种层次关系。 二叉树 二叉树的变形 树和森林 树的变形 树的应用 ;3.1 二叉树;基本概念 结点的度——结点所拥有的子树的个数 叶子——度为0的结点 孩子——结点子树的根 双亲——孩子结点的上层结点 子孙——以某结点为根的子树中的任一结点 祖先——从根到该结点所经分支上的所有结点 结点的层次——从根结点起，根为第一层，它的孩子为第二层 ，孩子的孩子为第三层，……，L?L+1 兄弟 ——同一双亲的孩子互为兄弟 堂兄弟——其双亲在同一层的结点互为堂兄弟 二叉树的度——二叉树中最大的结点度数 二叉树的深度——二叉树中结点的最大层次数;基本概念 满二叉树——在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。 完全二叉树——对深度为k的满二叉树中的结点从上至下，从左至右从1开始连续编号。对一棵具有n个结点深度为k的二叉树，采用同样办法对树中结点从上至下，从左至右从1开始连续编号，如果编号为i（i=n）的结点都与满二叉树中编号为i的结点在同一位置，则称此二叉树为一棵完全二叉树。 ;基本性质 性质1：一棵非空二叉树的第i层最多有2i-1个结点。 ;基本性质 性质2：深度为k的二叉树至多有2k-1个结点 (k≥1)。 ;基本性质 性质3：对任何一棵二叉树T，如果叶子结点数为n0，度为2的结点数为n2，那么，n0=n2+1。 证明：假设度为1的结点数为n1，二叉树总结点数为n，那么： n=n0+n1+n2 孩子结点个数=n-1 孩子结点个数=n1+2n2 ? n=孩子结点个数+1=n1+2n2+1=n0+n1+n2，化简得： n0=n2+1 ;基本性质 性质4：具有n个结点的完全二叉树的深度为?log2n?+1 证明：深度为k的完全二叉树最少有2k-1个结点，最多有2k-1个结点，因此，结点数n满足2k-1≤n2k，两边取对数得： k-1≤log2nk，即：k≤log2n+1k+1 ? k=?log2n?+1 ;基本性质 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1?i?n)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是?i/2? (2) 如果2in，则结点i无左孩子；如果2i?n，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1?n，则其右孩子是2i+1 证明：假设结点i在第k层，其双亲j在第k-1层第q个结点，那么j的编号为： j=2k-2-1+q 如果i是j的左孩子 ：i=2k-1-1+2(q-1)+1=2k-1+2q-2 如果i是j的右孩子 ： i=2k-1-1+2(q-1)+2=2k-1+2q-1 ?结点i的双亲j =?i/2? 若结点j有左孩子，即2j≤n，则其左孩子为2j； 若结点j有右孩子，即2j+1≤n，则其右孩子为2j+1 ;3.1 二叉树;3.1 二叉树;顺序存储结构 一般二叉树的顺序存储 把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。 ;顺序存储结构 一般二叉树的顺序存储 ;链式存储结构 二叉链表 ;链式存储结构 三叉链表 ;3.1 二叉树;二叉树的递归遍历 先序遍历DLR;二叉树的递归遍历 中序遍历LDR;二叉树的递归遍历 后序遍历LRD;二叉树的层次遍历 二叉树的层次遍历是指从二叉树的根结点开始，从上到下逐层遍历，同一层中从左到右访问二叉树的结点。层次遍历中，对一层的结点访问完以后，再按照它们的访问次序依次访问各个结点的左孩子和右孩子，这样一层一层地进行，先遇到的结点先访问。 首先将根结点入队，然后从对头取一个元素，每取一个元素，执行如下3个动作： 1. 访问该元素所指结点； 2. 如果该元素所指结点有左孩子，则左孩子指针入队； 3. 如果该元素所指结点有右孩子，则右孩子指针入队。;二叉树的非递归遍历 先序，中序，后序都是沿着图中路线进行：从树根开始沿左子树一直深入，直到最左端无法深入时，返回，进入刚深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。 先序：遇到结点就访问 中序：左子树返回时访问 后序：右子树返回时访问 深入返回的过程满足栈的特征，可用栈实现二叉树的遍历;二叉树的非递归遍历 例子：中序遍历非递归算法;遍历算法的应用 由先序和中序遍历序列建立二叉树 仅知道二叉树的先序序列?二叉树？ 如果同时知道先序和中序呢？;a b c d e f g;遍历算法的应用 二叉树中叶子结点统计 空树：叶子=0 左右子树为空：叶子=1 其它