20.二叉树的基本概念以及设计类

1、算法分析与设计（JAVA版）讲师：牛牧树与二叉树概念设计二叉树类 Lesson20树与二叉树的基本概念二叉树类设计树的概念树是由n（n0）个结点构成的满足以下条件的结点集合：（1）当n0时，有一个特殊的结点称为根结点，根结点没有前驱结点；（2）当n1时，除根结点外的其他结点被分成m（m0）个互不相交的集合T1, T2, Tm，其中每一个集合Ti（1im）本身又是一棵结构和树结构类同的子树。树的概念只有根结点的树 一般的树 树的基本概念结点：结点由数据元素和构造数据元素之间关系的指针组成。 结点的度：结点所拥有的子树的个数称为该结点的度。 叶结点：度为0的结点称为叶结点，叶结点也称作终端结点。

2、分支结点：度不为0的结点称为分支结点，分支结点也称 作非终端结点。 孩子结点：树中一个结点的子树的根结点称作这个结点的孩子结点。 树的基本概念双亲结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点。 兄弟结点：具有相同的双亲结点的结点称为兄弟结点。 树的度：树中所有结点的度的最大值称为该树的度。 结点的层次：从根结点到树中某结点所经路径上的分支数。树的基本概念树的深度：树中所有结点的层次的最大值称为该树的深度。 无序树：树中任意一个结点的各孩子结点的排列没有严格次序的树称为无序树。 有序树：树中任意一个结点的各孩子结点的排列有严格次序的树称为有序树。 森林：m（m0）棵树的集

3、合称为森林。 树的抽象数据类型 数据集合 ：树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）双亲结点parent() （2）左孩子结点leftChild() （3）右兄弟结点rightSibling() （4）遍历树traverse(vs) 树的存储结构双亲表示法 双亲表示法就是用指针表示出每个结点的双亲结点。 对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号的仿真指针域。树的存储结构树及其使用仿真指针的双亲表示法 树的存储结构孩子表示法 孩子表示法就是用指针表示出每个结点的孩子结点。常规指针的

4、孩子表示法树的存储结构双亲孩子表示法 双亲孩子表示法就是用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点。树的存储结构树的存储结构孩子兄弟表示法 孩子兄弟表示法就是用指针既表示出每个结点的孩子结点，也表示出每个结点的兄弟结点。二叉树二叉树的定义 二叉树是n（n0）个结点构成的、每个结点最多只有两个子树的有序树。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。 完全二叉树：如果一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构相同。二叉树两棵不同的二叉树二叉树满二叉树和完全二叉树 二叉树抽象数据类型数据集合：二叉树的结点

5、集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合： （1）双亲结点parent()： （2）左孩子结点leftChild() （3）右孩子结点rightSibling() （4）左插入结点insertLeftNode(x) （5）右插入结点insertRightNode(x)： （6）左删除子树deleteLeftTree() （7）右删除子树deleteRightTree() （8）遍历二叉树traverse(vs)二叉树的性质 性质1 若规定根结点的层次为0，则一棵非空二叉树的第i层上最多有2i（i0）个结点。 性质2 若规定空二叉树树的深度为-1(即根结点的深度为0)，

6、则深度为k的二叉树的最大结点数是2k+1-1（k-1）个。 性质3 具有n个结点的完全二叉树的深度k为不超过log2(n+1)-1的最大整数。 性质4 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0= n2+1。二叉树的性质性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从0开始顺序编号，则对于序号为i的结点，有： （1）如果i0，则序号为i结点的双亲结点的序号为 (i-1)/2（“/”表示整除）；如果i=0，则序号为i结点为根结点，无双亲结点。 （2）如果2i+1n，则序号为i结点的左孩子结点的序号为2i+1；如果2i+1n，则序号为i结点无左孩子结点。 （3）如果2i+2n，则序号为i结点的右孩子结点的序号为2i+2；如果2i+2n，则序号为i结点无右孩子结点。二叉树的存储结构二叉树的顺序存储结构 非完全二叉树的顺序存储结构如下图二叉树的存储结构 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。 二叉链存储结构的每个结点包含三个域 。leftChilddatarightChild二叉树的存储结构二叉链存储结构的二叉树（