《数据结构课件、代码》第4章 树和二叉树.ppt

第4章树和二叉树 张成文北京邮电大学计算机学院 树的定义与基本术语 1 定义 树是n n 0 个结点的有限集合T 当n 0时 称为空树 当n 0时 该集合满足如下条件 1 其中必有一个称为根 root 的特定结点 它没有直接前驱 但有零个或多个直接后继 2 其余n 1个结点可以划分成m m 0 个互不相交的有限集T1 T2 T3 Tm 其中Ti又是一棵树 称为根root的子树 每棵子树的根结点有且仅有一个直接前驱 但有零个或多个直接后继 一 树 tree 的基本概念 A B C D E F G H I J M K L A B E F K L C G D H I J M T1 T3 T2 树根 例如 1 树型图示 2 嵌套集合 3 凹入 书目 4 广义表 用根作为表的名字写在表的左边 A B E K L F C G D H M I J 2 树的表示法 线性结构 树型结构 第一个数据元素 无前驱 根结点 无前驱 最后一个数据元素 无后继 多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它数据元素 一个前驱 多个后继 对比树型结构和线性结构的结构特点 结点 node 树的度 叶子结点 leaf 分支结点 数据元素 若干指向子树的分支 树各结点的度的最大值 度为零的结点 度大于零的结点 D H I J M 3 树的相关术语 结点的度 degree 结点拥有的子树数 结点的层次 level 假设根结点的层次为1 第l层的结点的子树根结点的层次为l 1 树的深度 depth 叶子结点所在的最大层次 分支 branch 表示数据元素与它的子树的关系 路径 path 常用家族树的术语表示结点关系孩子 child 结点双亲 parent 结点兄弟结点 由根到该结点所经的分支和结点构成 树的结点数n和分支数b的关系是 b n 1 任何一棵非空树是一个二元组Tree root F 其中 root被称为根结点F被称为子树森林 森林 forest 是m m 0 棵互不相交的树的集合 A root B C D E F G H I J M K L F 二叉树 1二叉树的定义与基本操作 定义 满足以下两个条件的树称做二叉树 BinaryTree 1 每个结点的度都不大于2 2 每个结点的孩子结点次序不能任意颠倒 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交的二叉树组成 注意 二叉树是有序树 它的子树有左右之分 二叉树的度数不超过二 但度数不超过二的树未必是二叉树 A B C D E F G H K 根结点 左子树 右子树 二叉树的五种基本形态 N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子树均非空树 用归纳法证明 归纳基 归纳假设 归纳证明 i 1层时 只有一个根结点 2i 1 20 1命题成立 假设i 1命题成立 即 第i 1层至多有结点 2i 1 1 2i 2个 二叉树每个结点至多有两棵子树 则第i层至多有结点 2i 2 2 2i 1个 2二叉树的重要特性 性质1 二叉树第i层上至多有2i 1个结点 证明 基于性质1 深度为k的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加 所以深度为k的二叉树上含结点数至多为 20 21 2k 1 2k 1 性质2 深度为k的二叉树上至多含2k 1个结点 k 1 证明 设二叉树上结点总数 n n0 n1 n2再根据树的性质 b n 1 n0 n1 n2 1由有二叉树分支总数 b n1 2n2两式右边相等得 n0 n2 1 性质3 对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 也可以用归纳法证明 满二叉树 在一个二叉树中 若第i层的结点数为2i 1 则称此层的结点数是满的 当树中的每一层都是满的 则称此二叉树为满二叉树 即如果一个二叉树中 除最下一层的各结点度数为0以外 其它各层结点的度数均等于2 则此二叉树为满二叉树 完全二叉树 如果一个二叉树各层都是 满 的 只是最下面一层从右边起连续缺n个结点 这种二叉树叫做完全二叉树 完全二叉树 树中所含的n个结点和满二叉树中编号为1至n的结点一一对应 a b c d e f g h i j 可用一维数组存储 bt n 顺序 完全二叉树中将编号i的结点存在bt i 中 一 二叉树的顺序存储 3二叉树的存储结构 二叉树是非线性结构 结点最多有两个后继 存储结构有两种 顺序存储结构和链式存储结构 例如 ABDCEF 1234567891011121314 一般二叉树 按完全二叉树结点的编号存放 无结点的单元存放空元素 会造成空间浪费 二 二叉树的链式存储表示 二叉链表 每个结点包括两个指针域 指向左孩子和右孩子 二叉树T 二叉链表 结点结构 lchilddatarchild 结点结构 二叉链表结点的结构用C语言描述为 typedefstructNode DataTypedata strctNode LChild structNode RChild BiTNode BiTree 一 问题的提出 二 先左后右的遍历算法 三 算法描述 二叉树的遍历 遍历 沿某条搜索路径巡访二叉树的结点 使每个结点均被访问一次 且仅被访问一次 一 问题的提出 访问 的含义很广 如 输出结点信息等 遍历 是任何类型均有的操作 对线性结构而言 只有一条搜索路径 因为每个结点只有一个后继 故不需要另加讨论 二叉树是非线性结构 每个结点有两个后继 则存在按什么样的搜索路径遍历的问题 二叉树 由三部分组成 根结点 左子树和右子树 若能依次遍历这三部分 就遍历了整个二叉树 用L D R表示遍历左子树 访问根结点 遍历右子树 则有8种遍历二叉树方案 先左后右 DLR LDR LRD 按层次先右后左 DRL RDL RLD 按层次 二 先左后右的遍历算法 先序的遍历算法DLR 中序的遍历算法LDR 后序的遍历算法LRD D L R 若二叉树为空树 则空操作 否则 1 访问根结点 2 先序遍历左子树 3 先序遍历右子树 先序的遍历算法 D L R 若二叉树为空树 则空操作 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 中序的遍历算法 D L R 若二叉树为空树 则空操作 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 后序的遍历算法 D L R a b c d e f g h i j 例如 先序序列 abdhiejcfg 中序序列 hdibjeafcg 后序序列 hidjebfgca 三 算法描述 1 先序遍历voidPreOrder BiTreebt 先序遍历 根指针为bt的二叉树 if bt NULL Visit bt data 访问根结点PreOrder bt LChild 遍历左子树PreOrder bt RChild 遍历右子树 2 中序遍历voidInOrder BiTreebt 中序遍历根指针为bt的二叉树 if bt NULL InOrder bt LChild 遍历左子树Visit bt data 访问根结点InOrder bt RChild 遍历右子树 3 后序遍历voidPostOrder BiTreebt 后序遍历根指针为bt的二叉树 if bt NULL PostOrder bt LChild 遍历左子树PostOrder bt RChild 遍历右子树Visit bt data 访问根结点 利用遍历结果确定二叉树问题先序序列 中序序列中序序列 后序序列先序序列 后序序列 x 先序序列 ABCDEFGH中序序列 BDCEAFHG A B F C G D E H 利用遍历结果确定二叉树问题 仅知二叉树的先序序列