7.2二叉树7.2.1二叉树的概念1.二叉树的定义二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用ne表示叶子结点个数，n,表示单分支结点个数，n,表示双分支结点个数。1/35
二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由 一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 二叉树中许多概念与树中的概念相同。 在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结 点个数，n1表示单分支结点个数，n2表示双分支结点个数。 1. 二叉树的定义 1/35
提示二叉树与度为2的树是不同的。度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。2/35
度为2的树至少有3个结点，而二叉树的结点数可以为0。 度为2的树不区分子树的次序，而二叉树中的每个结点最多有 两个孩子结点，且必须要区分左右子树，即使在结点只有一棵 子树的情况下也要明确指出该子树是左子树还是右子树。 提示 二叉树与度为2的树是不同的。 2/35
归纳起来，二叉树的5种形态：(a) 空二(b） 只有（c）右子树(d）左子树（e）左、右子叉树为空的二叉树为空的二叉树树非空的二叉树一个根结点的二叉树3/35
归纳起来，二叉树的5种形态： Ø (a) 空二 叉树 (b) 只有 一个根结点 的二叉树 (c) 右子树 为空的二叉树 (d) 左子树 为空的二叉树 (e) 左、右子 树非空的二叉树 3/35
2.二叉树抽象数据类型的描述ADTBTree(数据对象：D={ai丨1≤i≤n，n≥0，a,为E类型}//为了简单，除了特别说明外假设E为char数据关系：R=(r)r={「ai，ajED，1≤i，j≤n，当n=o时，称为空二叉树；否则其中有一个根结点，其他结点构成根结点的互不相交的左、右子树，该左、右两棵子树也是二叉树子基本运算：voidCreateBTree（stringstr)：根据二叉树的括号表示串建立其存储结构。Stringtostring()：返回由二叉树树转换的括号表示串。BTNodeFindNode（x）：在二叉树中查找值为x的结点。intHeight()：求二叉树的高度。4/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且有2h-1个结点的二叉树称为满二叉树。10141511312M5/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个结点的满二叉树的高度为1og2(n+1)，叶子结点个数为Ln/2]+1度为2的结点个数为Ln/2]。n=15h=1og2(n+1)=4101415111312MA6/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，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。1011L7/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的结点，只可能有一个，且该结点只有左孩子而无右孩子；按层序编号后，一旦出现某结点（其编号为）为叶子结点或只有左孩子则编号大于的结点均为叶子结点。108/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
二叉树性质7.2.2性质1非空二叉树上叶结点数等于双分支结点数加1。即ng=n2+1。证明：总结点数n=ne+ni+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则ni+2n2=ng+ni+n2-1,求出ng=n2+1。在二叉树中计算结点时常用的关系式有：①所有结点的度之和归纳=n-1②所有结点的度之和=n1+2n2③n=ne+ni+n2。9/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层上至多有2i-1个结点，这里应有≥1。由树的性质2可推出。性质3 高度为h的二叉树至多有2h-1个结点（h≥1）。由树的性质3可推出。18/35
性质2 非空二叉树上第i层上至多有2 i-1个结点，这里应有i≥1。 由树的性质2可推出。 性质3 高度为h的二叉树至多有2 h-1个结点（h≥1）。 由树的性质3可推出。 10/35