树的存储结构

树是一种非线性存储结构，通常用来存储逻辑关系为 "一对多" 的数据。

结点：

树存储的每一个元素称为结点，如上图的A~M结点。

根结点：

将最上方的结点成为根结点，如上图的A结点。

子结点 & 父结点 & 兄弟结点（双亲结点）& 祖先结点：

与当前结点向下相连的结点，称为当前结点的子结点；如上图，B、C、D是A的子结点，反之，A是B、C、D的父结点（双亲结点）。

如果两个结点的父结点是同一个，称这两个结点为兄弟结点。如上图，B、C、D是兄弟结点。

某结点向上的结点都称为此结点的祖先结点。如上图，K的祖先结点为A、B、E。

叶子结点：

如果某结点没有任何子结点，称之为叶子结点。如上图，K、L、F、G、M、I、J都是                      叶子节点。

度：   

           ① 结点的度：每一个结点连接子结点的数目称为结点的度，如上图A结点的度为3。

           ② 树的度：各个结点度的最大值称为树的度，如上图A结点的度3就是树的度。

子树：

从某一结点的子结点开始延申到最后，形成一个新的树，称这个树为这一结点的子树。如上图，结点B及其之后延申的所有分支合在一起，称为结点A的子树。

深度：

从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。对于上图来说，A 结点在第一层，B、C、D 为第二层，E、F、G、H、I、J 在第三层，K、L、M 在第四层。树中结点层次的最大值，称为这棵树的深度或者高度。例如上图这棵树的深度为 4。

森林：

由 m（m >= 0）个互不相交的树组成的集合称为森林。

什么是二叉树

二叉树是一种特殊的树，他的度，也就是每个结点的度最大为2。如下图，第一个为二叉树，第二个由于1号结点的度为3，所以不是二叉树。

。 

二叉树的五种基本形态：

 二叉树的分类：

满二叉树：

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

完全二叉树：

如果二叉树中仅最后一层结点有空缺，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。所以我们可以这么说：一棵满二叉树，一定是完全二叉树。

树、森林和二叉树之间的互相转换

树转换成二叉树：

首先，我们先将树的所有兄弟结点连接起来，如图b;然后只保留最左侧兄弟结点与其父结点的连接，如图c；最后将所有的黑色线偏向左边，所有的橙色线偏向右边。我们发现，转换过后的二叉树是没有右子树的！

同样的，二叉树转换成树只需要将以上方法反推就行了。

森林转换成二叉树：

上图有一个三棵树组成的森林，我们先将他们分别转换成二叉树，然后再连接起来，怎么连接呢？很简单，因为由树转换成的二叉树都没有右子树，所以我们将后一个二叉树作为前一个二叉树的右子树就行了！最后的结果如下：

 二叉树的数学性质

性质一

对于一棵二叉树，第 k 层最多有 2^（k-1）个结点。

性质二

对于一棵深度为 k 的二叉树，此二叉树最多有 2^k-1 个结点。

一个满二叉树的总结点数为 1+4+8+. . .+2^（k-1）个，我们可以看出每一层的结点组成一个公比为2的等比数列，所以根据等比数列求和公式得，一个满二叉树得总节点数最多为：

a1 * (1 - q^n ) / ( 1 - q ) = 1 * ( 1 - 2^k ) / ( 1 - 2 ) = 2^k-1

性质三

假设度为0的结点有n0个，度为1的结点有n2个，度为3的结点有n3个，那么根据二叉树结点的度不大于2可知，二叉树的总结点数为:

N=n0+n1+n2

又因为二叉树的边永远比总结点数少1，一个度为2的结点有2条边，度为1的结点有1条边，所以我们还可以根据边数求二叉树的总结点数:

N=n1+2n2+1

两式相等并化简得：

n0=n2+1

性质四

满二叉树的深度k和总结点n的关系：

k=log2(n+1) 

完全二叉树的深度和总结点n的关系：

k=log2(n+1)

如果log2(n+1)为小数，则k向上取整。

性质五

 一个有n个结点的完全二叉树，现在对于人一个结点标号，标号顺序为从上往下，从左往右。

对于一个拥有左右孩子的结点来说，左孩子就是 2i，右孩子就是 2i+1。

如果 i=1，则此节点为根节点；如果 i>1，其父结点为 i/2。

如果 2i>n，则结点 i 没有左孩子；如果2i+1>n，则结点 i 没有右孩子。