第4章二叉树.pptVIP

第四章 二叉树 课程目标 ? 树的基本概念 ? 什么是二叉树 ? 用链表表示二叉树 ? 用数组表示二叉树 ? 二叉树的基本操作 本章体验项目——计算二叉树中叶子的个数 本程序启动后，建立一个二叉树，向树上添加节点，对其进行遍历并得到一共有多少片叶子 3.1 树 3.1.1树的基本概念 树形结构的特点是一个节点可以有多个直接后继，是一种常用的非线性结构。而我们前面讲到线性结构中一个节点最多只能有一个直接后继。因此树形结构可以表达更复杂的数据。 现实世界中的很多事物可以用树形结构来描述。 例如，人类社会中的家族成员之间的血统关系可以很自然地表示成一个树形结构 上图是描述“老王” 家族的成员及其血统关系的树形结构。 其中，“老王”有两个孩子“王一”和“王二”。“王一”有两个孩子“王小一”和“王小二”；“王二”又一个孩子“王小三”。这张图看上去很像一棵倒置的树。“树形结构”由此得名。 树的定义： 树是n（n=0）个节点的有穷集合，满足： (1)有且仅有一个称为根的节点； (2)其余节点分为m（m≥0）个互不相交的非空集合T1，T2，…，TM，这些集合中的每一个都是一棵树，成为根的子树。 在上图中，王一、王二的小家族就是两棵子树。 3.1.2树的相关名称及意义 1. 根节点：一棵树中没有父节点的节点，成为根节点。 2． 叶节点或终端节点：一棵树中没有子节点的节点，成为叶节点。 3． 非终端节点：除了叶节点与根节点以外的其他节点，成为非终端节点。 4. 父节点和子节点：若节点x有一个以节点y为树根子树，则x为y的父节 点，而y为x的子节点。 5． 兄弟：同一个父节点的节点，成为兄弟。如图4-2“王一”、“王二”的父节 点都为老王，所以“王一”、“王二”或为兄弟。 6． 分支度：每个节点所拥有的子节点个数。而一棵树中分支度值为其最大 分支度。如上图中“老王”的分支度为2，“王一”的分支度为2，“王二”的 分支度为1，所以这棵树的分支度为2。 7． 阶层：阶层为节点的特性值，将根节点的阶层设为１，其子节点为２， 以此类推。在上图中阶层为1的有节点“老王”，阶层为2的有“王一”、“王 二”，阶层为3的有“王小一”、“王小二”、“王小三”。 8． 高度或深度：一棵树中的最大阶层值，称为树的高度或深度。在图4-2中 最大阶层值为3，所以其高度为3。 9． 祖先：由某节点x到根节点的路径上的所有节点，均称为x的祖先。在上图中“王小一”到“老王”路径上的节点“王一”、“老王”即为“王小一”的祖先。 10． 树林：n≥0个树的集合成为树林。若将一棵树的根节点移去，所剩下的 恰是一个森林。 3.2 二叉树（Binart Tree） 3.2.1为什么使用二叉树 树及二叉树结合了另外两种数据结构的优点：一种是有序数组，另一种是链表。在树中查找数据和在数组中查找一样快，在树中添加删除数据的速度也和在链表中一样。 3.2.2 何谓二叉树 二叉树是树的一种，二叉树中的节点至多只能有两个子节点。 二叉树的定义如下： （1） 由有限个节点所构成的集合，此集合可以为空的。 （2） 二叉树的根节点下可分成两个子树，成为左子树和右子 树，左子树和右子树亦是二叉树。 图4-1中以“老王”为根节点，其左子树和右子树分别为 3.2.3二叉树和树的比较 （1）二叉树可为空，而树不可以（至少要有根节点） （2）二叉树的子树有顺序关系，而树没有 （3）二叉树的分支度比为0、1、2，而树的分支度可大于2 3.2.4二叉树的性质 在某些情况下，了解二叉树的下列性质是有帮助的。这些性质的证明并不难。 性质1： 二叉树第i（i≥1）层上至多有2i-1个节点。 性质2： 深度为k（k≥1）的二叉树至多有2k-1个节点。 性质3： 对任何二叉树，若2度节点数为n2，则叶子数 n0=n2+1。 歪斜树（Skewed Binary Tree） 在一棵树中，若所有节点的左子树均不存在，则次树为右歪斜树（Right Skewed Binary Tree），反之，所有节点的右子树均不存在，则此树为左歪斜树（Left Skewed Binary Tree）。 满二叉树（Full Binary Tree） 一棵树中所有叶节点均在同一阶层，而其他非终端节点的分支度均为2，则此树为一个满二叉树。若该书的高度为h，则此二叉树的节点为2h-1 完全二叉树 满二叉树上各层的节点数已达到了二叉树可以容纳的最大值。图4-7所示为一棵深度为3的满二叉树。如果在一棵深度为k（k≥1）的满二叉树上删去第k层上最有右的连续j（0≤j≤2k-1）个节点，就得到一棵深度为k的完全二叉树。 用链表表示二叉树 用Java表示二