树及二叉树

树

定义

树是一种非线性的数据结构，它由n个有限结点组成的有层次关系的集合。

• 如图所示，树的第一个结点是一个特殊的结点，它没有前驱结点，称为根结点。
• 此外，我们将没有后驱结点的结点称为叶结点。
• 值得注意的是，除了根结点外的其余结点有且只有一个前驱结点。由此我们可以看出，树是递归定义的，因为我们可以将树分为根和子树。

相关概念

由树引出的专业名词相当的丰富，它有如下概念：

• 结点的度：一个结点含有的子树个数称为这个结点的度，如上图“5”结点的度为2.
• 叶结点或终端结点：即没有子树的结点。
• 非终端结点或分支结点：即度不为零的结点。
• 双亲结点或父结点：即结点的前驱结点，需要注意的是根结点没有父结点。
• 孩子结点或子结点：即结点的后驱结点，叶结点没有子结点。
• 兄弟结点：拥有同一个父结点的结点互为兄弟结点，如果以血缘关系来形容那就是亲兄弟结点。
• 树的度：一棵树中，最大的结点的度为这棵树的度。
• 结点的层次：以根结点为第一层，根节点的子结点为第二层，依此类推。
• 树的高度或深度：树中结点的最大层次，如上述的树的高度为3.
• 堂兄弟结点：同一层次的结点互为堂兄弟结点。
• 节点的祖先：从根结点到该结点的分支所经过的所有结点，如“6”结点的祖先为“5”、“7”结点。
• 子孙：以某结点为根结点的子树的所有结点都是该结点的子孙。
• 森林：由m（m>0）棵不相交的树的集合称为森林。

树的表示

数的表示有很多种方式，其中比较经典的是左孩子右兄弟表示法：

typedef int DataType;
struct TreeNode
{
	struct TreeNode*leftchild;
	struct TreeNode*rightbrother;
	DataType val;
};
1
2
3
4
5
6
7

如果将上图的树表示出来逻辑结构就是如下效果：

二叉树

定义

二叉树即为，树的度不大于二的树

由此不难发现，二叉树由一个根结点和左子树、右子树组成，这显然是由递归定义的。
此外，二叉树是一个有序树，次数不能颠倒。
如下：

这便是一个二叉树。

特殊的二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^K-1，则它就是满二叉树。
  

• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
  

二叉树的性质

• 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^i-1个结点.
• 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
• 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= ${\log }_2(n+1)$
• 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子