河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.2 二叉树

二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由 一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 二叉树中许多概念与树中的概念相同。 在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结 点个数，n1表示单分支结点个数，n2表示双分支结点个数。 1. 二叉树的定义 1/35

度为2的树至少有3个结点，而二叉树的结点数可以为0。 度为2的树不区分子树的次序，而二叉树中的每个结点最多有 两个孩子结点，且必须要区分左右子树，即使在结点只有一棵 子树的情况下也要明确指出该子树是左子树还是右子树。 提示 二叉树与度为2的树是不同的。 2/35

归纳起来，二叉树的5种形态： Ø (a) 空二 叉树 (b) 只有 一个根结点 的二叉树 (c) 右子树 为空的二叉树 (d) 左子树 为空的二叉树 (e) 左、右子 树非空的二叉树 3/35

ADT BTree { 数据对象： D={ai | 1≤i≤n，n≥0，ai为E类型} //为了简单，除了特别说明外假设E为char 数据关系： R={r} r={ | ai，aj∈D， 1≤i，j≤n，当n=0时，称为空二叉树；否则其中 有一个根结点，其他结点构成根结点的互不相交的左、右子树，该 左、右两棵子树也是二叉树 } 基本运算： void CreateBTree(string str)：根据二叉树的括号表示串建立其存储结构。 String toString()：返回由二叉树树转换的括号表示串。 BTNode FindNode(x)：在二叉树中查找值为x的结点。 int Height()：求二叉树的高度。 . } 2.二叉树抽象数据类型的描述 4/35

3. 满二叉树和完全二叉树 在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且 叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。 可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层 数从小到大、同一层从左到右的次序进行。 满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h 且有2 h-1个结点的二叉树称为满二叉树。 A B D H I E J K C F L M G N O 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 5/35

满二叉树的特点如下： 叶子结点都在最下一层。 只有度为0和度为2的结点。 含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为n/2+1， 度为2的结点个数为n/2。 A B D H I E J K C F L M G N O 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 n=15 h=log2(n+1)=4 6/35

若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下 面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉 树称为完全二叉树。 同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二 叉树相同，图中每个结点外边的数字为对该结点的编号。 A B D H I E J K C F G 1 2 4 8 9 5 10 11 3 6 7 7/35

完全二叉树的特点如下： 叶子结点只可能出现在最下面两层中。 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子； 按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子， 则编号大于i的结点均为叶子结点。 A B D H I E J K C F G 1 2 4 8 9 5 10 11 3 6 7 8/35

性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。 总结点数n=n0+n1+n2。 一个度为1的结点贡献1个度，一个度为2的结点贡献2个度， 所以总的度数=n1+2n2。 总的度数=总分支数=n-1。 则n1+2n2=n0+n1+n2-1，求出n0=n2+1。 证明： 在二叉树中计算结点时常用的关系式有：①所有结点的度之和 =n-1 ②所有结点的度之和＝n1＋2n2 ③n=n0+n1+n2。 归纳 9/35

性质2 非空二叉树上第i层上至多有2 i-1个结点，这里应有i≥1。 由树的性质2可推出。 性质3 高度为h的二叉树至多有2 h-1个结点（h≥1）。 由树的性质3可推出。 10/35