树（2）2二叉树2-1二叉树的定义1．定义二叉树是有n（n>=0）个结点的有限集合。（1）该集合或者为空（n=0）；（2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；（3）左子树和右子树同样又都是二叉树。通俗地讲：在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。2．二叉树的形态根据定义，二叉树可以有五种基本形态，如图所示。(a)(b)(c)(d)(e)二叉树的基本形态其中：（a）空二叉树；（b）仅有根结点的二叉树；（c）右子树为空的二叉树；（d）左子树为空的二叉树；（e）左、右子树均非空的二叉树。ФLchildLchildRchildRchild3．二叉树的基本操作：（1）isEmpty()：判断是否空树。(2)intcount();返回二叉树的结点个数(3)intheight();返回二叉树的高度(4)BinaryNodegetRoot()：返回根结点元素。（5）BinaryNodegetParent(BinaryNodechild)：返回child的父母结点。（6）voidpreOrder()：先根次序遍历二叉树。3．二叉树的基本操作：（7）voidinOrder()：中根次序遍历二叉树。（8）voidlevelOrder()：后根次序遍历二叉树。（9）BinaryNodesearch(Eelement)：查找并返回元素为element的结点。（10）voidinsert(BinaryNodep,Eelement,booleanleftChild)：插入element做为p的孩子左/右孩子结点。(11)voidremove(BinaryNodep,booleanleftChild)：删除p结点的左/右子树。(12)voidclear()：清空树。2-2二叉树的性质性质1一棵非空二叉树的第i层上最多有2i–1个结点（i≥1）。一棵非空二叉树的第一层有1个结点，第二层最多有2个结点，第三层最多有4个结点……，利用归纳法即可证明第i层上最多有2i–1个结点。性质2深度为h的二叉树中，最多具有2h-1个结点（h≥1）。证明：根据性质1，当深度为h的二叉树每一层都达到最多结点数时，它的和（n）最大，即：∴命题正确。（1）满二叉树一棵深度为h，且有2h‐1个结点的二叉树称为满二叉树。下图所示是一棵深度为4的满二叉树，其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续的编号，约定编号从根结点起，从上往下，自左向右，由此可以引出完全二叉树的定义。123876541091112131415满二叉树（2）完全二叉树深度为h，有n个结点的二叉树，当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。如下图（a）所示为一棵完全二叉树。ABCHGFEDJI图6-6（a）一棵完全二叉树如下图（b）所示则不是完全二叉树。图（b）一棵非完全二叉树完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。ABCGFEDH性质3对于一棵有n个结点的完全二叉树，若按满二叉树的同样方法对结点进行编号，则对于任意序号为i的结点，有：（1）若i>1，则序号为i的结点的父结点的序号为i/2；若i＝1，则序号为i的结点是根结点。（2）若2i≤n，则序号为i的结点的左孩子结点的序号为2i；若2i>n，则序号为i的结点无左孩子。（3）若2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；若2i＋1>n，则序号为i的结点无右孩子。性质4具有n（n>0）个结点的完全二叉树（包括满二叉树）的深度（h）为：证明：由性质2和完全二叉树定义可知，当完全二叉树的深度为h、结点个数为n时有：2h–1-1
