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，aj>「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> | 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