软件技术基础9.pptVIP

树的基本概念 3.1 树的基本概念 非线性结构 对于结构中的一个结点，可能有多个前趋和多个后继 线性表中是有且仅有一个前趋和一个后继 3.1.1树的定义 (教材p35） 树是以分支关系定义的层次结构。 倒生树：树根在上，根上分茎，茎上分叶 是族谱、社会组织机构一类实体的逻辑抽象 树的定义 对定义的理解 （1）有限集 （2）递归定义：树，根，子树 （3）有且仅有一个根结点不存在空树 （4）子树是互不相交的有限集 （5）树的层次性 树的定义 树是一种数据结构 Tree = ( D , R ) D：元素的集合 R：元素关系的集合 （父、子关系 前驱、后继关系） 各结点没有或仅有一个父结点 有且仅有一个根结点 各结点可以有任意个子树 树的术语 3.1.2 树的术语 1）结点 2）度与深度 树的术语 树的术语 4）路径（树枝，分支） 从K1出发自上而下到K2所经历的所有结点序列 树的术语 5）有序树与无序树 有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。 树的术语 6）森林 不相交的树的集合 树的存储 3.2树的存储 3.2.1连续顺序存储 树的存储 3.2.2、链接存储－－多重链表 树的节点 对应于 链表的链点 树节点间的分支关系用链点间的指针描述 链点可能有多个指针－－多重链表，每个指针描述对应节点的一个分支关系 有且仅有一个根链点 不同的指针指向不同的子树根链点 一个子树有仅有一个根链点 二叉树 3.3二叉树 3.3.1、定义 二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。 对比树的定义： 空二叉树 树的定义中没有空树的概念 不多于2个孩子 树的节点可以有任意个子树 子树有左右之分 无序树可不区分左右 树的其它定义适用于二叉树：根茎叶、度、路径 二叉树 （4）二叉树的形态 二叉树的性质 3.3.2、二叉树的性质 （1）在二叉树的第i层上最多有2i-1个结点 第i层的结点数最多是第i-1层的两倍 （2）深度为k的二叉树最多有2k - 1个结点 （3）叶结点数比具有两个孩子的结点数多 个 二叉树的性质 （3）叶结点数比具有两个孩子的结点数多1个 二叉树的性质 （4）深度为K的满二叉树，结点个数为2k-1 满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。 满二叉树：“装满”节点的二叉树 半满二叉树：深度为K的二叉树，K－1层是满二叉树，K层节点个数不足2K－1个 二叉树的性质 （5）具有n个节点的完全二叉树，深度为 [log2n]+1 完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。 如果对节点数为n的完全二叉树自上而下，从左至右依次编号，则节点i的父结点为[ i / 2 ] 完全二叉树 关于完全二叉树的其他描述形式 如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应 叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1 二叉树 顺序存储二叉树 3.3.3 顺序存储二叉树 将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点i，我们可以知道它的父结点为[ i/2 ]，两个孩子分别为2i和2i＋1。 一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系 如此存放，将浪费较多空间 顺序存储二叉树 例 用链表实现二叉树 3.4 用链表实现二叉树 二叉树链点的定义 二叉树的定义 用链表实现二叉树 二叉树的链表结构 二叉树的遍历 3.5、二叉树的操作 3.5.1遍历操作 分支及根的遍历顺序 二叉树的遍历 1）中根遍历（中序遍历） 二叉树的遍历 2）先根遍历（先序遍历） 二叉树的遍历 3）后根遍历（后序遍历） 课堂练习 写出这颗二叉树的三种遍历顺序 二叉树的遍历 中根遍历算法 算法实现分析 遍历过程： 从根开始 中根遍历算法（法一） 先根遍历算法 后根遍历 利用递归的遍历算法 方法二：利用递归调用来实现回溯 中根遍历递归算法 利用递归的遍历算法 后根遍历递归算法 利用递归的遍历算法 先根遍历递归算法 利用递归的遍历算法 二叉树的遍历 对比递归与非递归算法 递归算法更简洁，更多依靠系统提供的“用户程序调用栈”，该栈的使用对用户是不可见的 非递归算法在算法中直接掌握栈结构的调用 二叉树的深度决定了递归调用的深度，决定了栈的长度。 当二叉树的深度较深时，系统提供的“用户程序调用栈”可能出现溢出，这时需要算法自行掌握栈的使用。 二叉树的遍历