树、森林与二叉树（详细介绍） 原创

说明：本文总结了 树、森林与二叉树的特点、三者之间的转换、遍历，线索二叉树，哈夫曼树/最优二叉树，树相关的知识，希望能帮到学习的你。

---

树（tree）  

树（tree）是n个结点的有限集，它或为空树（n=0）;或为非空树。

树的基本术语：

（1）结点：树中的一个独立单元；
（2）结点的度：结点拥有的子树称为结点的度；
（3）树的度：树内各结点度的最大值；
（4）叶子：度为0的结点称为叶子或中断结点；
（5）非终端结点：度不为0的结点称为非终端结点后或分支结点，也称内部结点；
（6）双亲和孩子：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲；
（7）兄弟：同一个双亲的孩子互称兄弟；
（8）祖先：从根到该结点所经分支上的所有结点；
（9）子孙：以某结点为根的子树中任意一结点都成为该结点的子孙；
（10）层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层，一次类推；
（11）堂兄弟：双亲在同一层的结点互为堂兄弟；
（12）树的深度：树中结点的最大层次称为数的深度或高度；
（13）有序数和无序数：如果将树中结点的各子树看成从左至右是有次序的（不能互换），则称该树为有序疏，否则称为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子；
（14）森林：m（m>=0）棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。所以也可以用森林和树相互递归的定义来描述树。

二叉树（binary tree）

二叉树（binary tree）是n（n>=0）个结点所构成的结合，他或为空树；或为非空树，对于非空树
（1）有且仅有一个称为根节点；
（2）除根节点外，其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身也是二叉树。

二叉树：
（1）二叉树每个结点之多只有两棵子树；（树的度不大于2）；
（2）二叉树的子树有左右之分，其次序不能任意颠倒；

二叉树的性质：

性质1：在二叉树的第i层至多有2^(i-1)个结点（i>=1）。
性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）。
性质3：对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

满二叉树：深度为k且包含2^k-1个结点的二叉树。（每一层上的结点数都是最大的即2^(i-1)个结点，除叶子结点外，每个结点都有两个孩子）。
完全二叉树：
深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的的满二叉中编号从1至n的结点一一对应，称之为完全二叉树。
理解：除了最后两层外其他层都是满的即满足2^(i-1)个结点，只有最后一层可以不满，其他都必须满，也就是叶子结点只能出现在最后两层。最后一层可以不满，但必须连着不能缺，一旦不连续就不是完全二叉树。

完全二叉树特点

（1）叶子结点只可能在层次最大的两层出现（最下两层）。
（2）对于任意结点，其有分支下的子孙的层次为l，则其做分支下的子孙最大层必须为l或l+1。（其实就是限定了必须连续，一个结点有右孩子，其左孩子就必定有，没有的话就不连续了）。

性质4：具有n个结点的完全二叉树的深度为[log(2)(n)]+1。

//二叉树实现
//1.顺序储存
//2.链式储存

//------------二叉树的顺序存储结构------------
#define MAXSIZE 100 //二叉树最大结点数
typedef TElemType SqBiTree[MAXSIZE]; //0号单元存储根结点
SqBiTree bt;
//顺序存储仅适用于完全二叉树，对于非完全二叉树，空间浪费极大，所以，对于一般的二叉树，更适合链式存储结构。

//------------二叉树的链式存储结构------------
typedef struct BiTNode{
TElemType data; //结点的数据域
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

二叉树的遍历

1、先序遍历（根-左-右）

2、中序遍历(左-根-右）
3、后序遍历 (左-右-根)
我们可以发现，他起的名字先中后是根据根的先后顺序来说的，所以也称为（（先、中、后）根遍历）左孩子始终是在右孩子前遍历，这样就很好记了。

1、先序遍历
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树；

2、中序遍历：
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树；

3、后序遍历
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点；

4、层次遍历
从上到下一层一层的从左到右遍历。

举例

代码实现

递归的，也可以不用递归的

//------------二叉树遍历------------
//先序遍历
void BeforeTraverse(BiTNode T)
{
if(T) //树不为空
{
visit_OutNode(T->data); //访问节点数据，自定义访问函数visit_OutNode
BeforeTraverse (T->lchild ); //递归遍历左子树
BeforeTraverse (T->rchild ); //递归遍历右子树
}
}
//中序遍历 ，，后序类似，换个顺序
void InTraverse(BiTNode T)
{
if(T) //树不为空
{
BeforeTraverse (T->lchild ); //递归遍历左子树
visit_OutNode(T->data); //访问节点数据，自定义访问函数visit_OutNode
BeforeTraverse (T->rchild ); //递归遍历右子树
}
}

线索二叉树

遍历二叉树是一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先、中、后序列。

//------------二叉树的二叉线索存储结构------------
typedef struct BiThrNode{
TElemType data; //结点的数据域
struct BiTNode *lchild,*rchild; //左右孩子指针
int LTag,RTag; //左右标志
}BiTNode,*BiTree;
//这种结构的二叉链表作为二叉树的存储结构，叫做线索链表，指向结点的前驱和后继指针，叫做线索链表。
//加上线索的二叉树称为线索二叉树（threaded binary tree）。
//对二叉树以某种次序遍历使其变为线索 二叉树的过程叫做线索化。

树、森林与二叉树相互转换

1、由树的二叉链表表示定义知道：任何一棵和树对应的二叉树的右子树必空。
2、把一棵树转换成二叉树后,这棵树的形态：唯一的，且根结点没有右子树。
3、树与森林转换：遵循左子树右兄弟表示法：左边的子树的根节点变成左子树，兄弟变成右子树。

1、树转换成二叉树

（遵循左子树右兄弟表示法：左边的子树的根节点变成左子树，兄弟变成右子树。）
1、将树的根结点A的第一个子结点B（长子）作为二叉树根结点A的左孩子;
2、若该子结点B存在兄弟节点C（可能有多个兄弟），则将该子结点B的第一个兄弟节点C（从左往右）作为该子节点的右孩子；
3、若结点C存在兄弟节点D（可能有多个兄弟），则将该结点C的第一个兄弟节点D（从左往右）作为该子节点的右孩子；
4、依次类推。
树转换成二叉树步骤
1、加线：从根结点开始，向下操作（从根到每个结点，是一个递归的过程）；将结点A的子结点（可能有多个兄弟）所有兄弟结点之间连线；
2、抹线：对每个结点，除了保留与其长子（第一个结点）的连线外（如果结点只有一个子结点那他就是长子），去掉该结点与其它孩子的连线。
3、旋转：将结点旋转一定角度，使之结构层次分明。
4、继续查看其它结点，重复前面步骤。

2、森林转换成二叉树

森林转换成二叉树步骤
1、将所有的树转换成二叉树；
2、将所有数的根结点作为兄弟结点，然后遵循左子树右兄弟表示法，就像树转换成二叉树一样。

3、二叉树转换成树

4、二叉树转换成森林

二叉树转换成森林步骤
1、先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
2、把分离后的每棵二叉树转换为树；
3、整理前两步得到的使之规范，这样得到森林。

实例：森林、树与二叉树相互转换

3、森林转成二叉树

4、树转换成二叉树

加深一下二叉树转换成树

二叉树、树、森林的遍历

二叉树：先序遍历、中序遍历、后序遍历、层次遍历；
树：先序遍历、中序遍历、后序遍历、层次遍历；
森林：先序遍历、中序遍历、层次遍历；

二叉树、树、森林的遍历对比
二叉树（树或森林对应的）	树	森林
先序遍历（先根遍历）	先序遍历 相等	先序遍历 相等
中序遍历	后序遍历 相等	中序遍历 相等
后序遍历	没有对应相等的	无后序遍历
说明：树和森林以二叉树作对比 。

树和二叉树遍历对比

树与对应二叉树遍历对比
1、树的先序遍历与其对应的二叉树的先序遍历序列相同；
2、树的后序遍历与其对应的二叉树的中序遍历序列相同；

森林与对应二叉树遍历对比

森林分两种遍历：先序遍历和中序遍历没有后序遍历，后续遍历只有树和二叉树才有的。
森林的先序遍历和中序遍历和他对应的二叉树的先序遍历和中序遍历是相同的！

森林与对应二叉树遍历对比
1、森林的先序遍历 与其对应的二叉树的先序遍历序列相同；
2、森林的中序遍历 与其对应的二叉树的中序遍历序列相同；

哈夫曼树（Huffman Tree）最优二叉树   

可参考

http://www.leixingke.com/article/detail/NT3r5Ua4