数据结构设计二叉树：数据结构二叉树
数据结构设计二叉树：数据结构二叉树如果二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。满二叉树除了满足普通二叉树的性质，还具有以下性质：图2 二叉树的五种形态如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。图3 满二叉树
二叉树的定义二叉树（Binary Tree）是个结点所构成的集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如图1二叉树示例图：
图1 二叉树示例图
二叉树与树都具有递归性质，二叉树与树的区别主要有：
- 二叉树每个结点至多只有两棵子树，也就是说不存在度大于2的结点。
- 二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树具有的五种基本形态：
- 空二叉树。
- 只有一个根结点。
- 根结点只有左子树。
- 根结点只有右子树。
- 根结点既有左子树又有右子树。
图2 二叉树的五种形态
满二叉树如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。
图3 满二叉树
满二叉树除了满足普通二叉树的性质，还具有以下性质：
- 满二叉树中第层的结点数为个。
- 深度为的满二叉树必有个结点，叶子数为。
- 满二叉树中不存在度为1的结点，每一个分支点中都两棵深度相同的子树，且叶子结点都在最底层。
- 具有个结点的满二叉树的深度为。
如果二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
图4 完全二叉树示意图
如图4a) 所示是一棵完全二叉树，图4b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为。
表示取小于的最大整数。例如，而 结果也是2。
二叉树的性质- 在二叉树的第层上至多有个结点（）。
- 深度为的二叉树至多有个结点（）。
- 对任何一棵二叉树，如果其终端结点数为，度为2的结点数为，则。
- 具有个结点的完全二叉树的深度为 （[x]表示不大于x的最大整数）。
- 如果对一棵有个结点的完全二叉树（其深度为）的结点，按层序编号（从第1层到第层，每层从左到右），对任一结点有：
a. 如果，则结点是二叉树的根，无双亲；如果，则其双亲是结点。
b. 如果，则结点无左孩子（为叶子结点）；否则其左孩子是结点。
c. 如果，则结点无右孩子；否则其右孩子是结点。
