森林、树、二叉树的性质与关系
这篇博客写的太累了。。。
本文中对于这部分的讲解没有提到的部分：
对于二叉树的遍历：重点讲了非递归遍历的实现方式和代码（递归方法使用的相对较多，请直接参考博客代码）
对于哈夫曼编码和线索二叉树的代码实现没有列出。
树
我们对于树和二叉树这一部分的内容主要研究树的逻辑结构和存储结构，由于计算机的特殊性存储结构及二叉树的简单性，我们更主要讨论二叉树的逻辑结构和存储结构并对其进行实现（其中包含二叉树的一些重要性质），另外我们在研究这一类问题时，首先要考虑到树与森林之间的转换，以及树与二叉树之间的转换。从而简化为最简单的二叉树问题。
知识体系结构图：
树的定义：（采用递归方法去定义树）
树：n（n≥0）个结点的有限集合。
当n＝0时，称为空树；
任意一棵非空树满足以下条件：
（1）有且仅有一个特定的称为根的结点；
（2）当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。（用图的定义法去描述树：连通而不含回路的无向图称为无向树，简称树，常用T表示树）
树的基本术语：
结点的度：结点所拥有的子树的个数。
树的度：树中各结点度的最大值。
叶子结点：度为0的结点，也称为终端结点。
分支结点：度不为0的结点，也称为非终端结点。
孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；
兄弟：具有同一个双亲的孩子结点互称为兄弟。
祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。
路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2, …, nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。
结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。
树的深度：树中所有结点的最大层数，也称高度。
层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。
有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。（数据结构中讨论的一般都是有序树）
森林：m (m≥0)棵互不相交的树的集合。
同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。
例：
树的抽象数据类型定义：（ADT Tree）
Operation：（功能）
InitTree（Create）：构造一棵树。
DestroyTree：销毁一棵树。（释放该树占用的存储空间）
Root：求树的根节点信息。
Parent：求树的双亲信息。（输入结点x输出x双亲的信息）
Depth：求树的深度。
PreOrder：前序遍历。
InOrder：中序遍历。（错误），在树（或者森林）中是不能中序遍历的（存在多个子树的情况）（二叉树是存在中序遍历的：先左子树后父节点后右子树）
PostOrder：后序遍历。
LevelOrder：层序遍历。
树的存储结构：
一、顺序存储：本质上是静态指针
1.双亲表示法
2.双亲、孩子表示法
3.双亲、兄弟表示法
二、链式存储：
1.孩子表示法–多重链表示法（出现空间浪费或结点结构不一致的缺点）
2.孩子表示法–孩子链表表示法
3.孩子兄弟表示法
一、顺序存储：本质上是静态指针
1.双亲表示法：
template
struct PNode{
T data; //数据域
int parent; //指针域，双亲在数组中的下标
} ;
2.双亲、孩子表示法：
3.双亲、兄弟表示法：
二、链式存储：
1.孩子表示法–多重链表示法（出现空间浪费或结点结构不一致的缺点）
方案一：指针域的个数等于树的度（空间浪费）
方案二： 指针域的个数等于该结点的度（结点结构不一致）
2.孩子表示法-孩子链表表示法（每个节点创建一个单链表）（n个结点共有 n 个孩子链表）
这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，为了便于进行查找采用顺序存储存储每个链表的头指针。
存储结构：
孩子结点：
struct CTNode
{
int child;
CTNode *next;
};
表头结点：
template
struct CBNode
{
T data;
CTNode *firstchild;
};
3.孩子兄弟表示法：设置两个分别指向该结点的第一个孩子和右兄弟的指针。
template
struct TNode{
T data;
TNode *firstchild, *rightsib;
};
二叉树：
下面我们来进入二叉树的讲解：
我们学习使用二叉树的原因：二叉树结构简单，适合计算机处理。我们可以将树转化为二叉树，从而利用二叉树解决树的有关问题。
二叉树的定义 ：
二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点：
⑴ 每个结点最多有两棵子树；
⑵ 二叉树是有序的，其次序不能任意颠倒。
特殊的二叉树：
斜树：（从结构上将，我们可以将其看成是单链表）
1 .所有结点都只有左子树的二叉树称为左斜树；
2 .所有结点都只有右子树的二叉树称为右斜树；
3.左斜树和右斜树统称为斜树。
例：
特点：
- 在斜树中，每一层只有一个结点；
2.斜树的结点个数与其深度相同。
满二叉树：
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
例：
满二叉树：
非满二叉树：
特点：
1.叶子只能出现在最下一层；
2.只有度为0和度为2的结点。
3.满二叉树在同样深度的二叉树中结点个数最多
4.满二叉树在同样深度的二叉树中叶子结点个数最多
完全二叉树：
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同则称该树为完全二叉树。（可以理解为完全二叉树降低了满二叉树的标准：只要求位置，不要求是否全部填充满。）
例：（上面为满二叉树，下面的则为完全二叉树）
特点：
- 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；（由完全二叉树的性质和层序编号的方式所决定）
- 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。
- 深度为k的完全二叉树在k-1层上一定是满二叉树。（层序编号性质决定）
二叉树的基本性质：
1.二叉树的第i层上最多有2的(i-1)次个结点（i≥1）
2.一棵深度为k的二叉树中，最多有2的k次-1个结点，最少有k个结点。
3.在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。
3.证明：
证明一：（利用二叉树结点总数等于度为0,1,2的和与二叉树结点总数等于根节点+度为1的节点数+2*度为2的节点数（利用了分枝））设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：
n＝n0＋n1＋n2
在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：
n＝n1＋2n2＋1
因此可以得到：n0＝n2＋1 。
证明二：（可能更好理解一些）：假设我们要求的二叉树都是满二叉树，那么此时叶子结点数n0=n2+1（此时所有的点度都为2，但是最后一层上的节点数等于上面层数的节点数和+1：2的k次等于2的0次+2的1次+…+2的k-1次+1，即此时满足n0=n2+1） 我们在该满二叉树的基础上减去实际并不存在的叶子结点，那么叶子结点数n0-1,但同时度为2的结点数n2-1，等式依然成立。如果我们对度为2的结点操作，减去其上的两个叶子结点，那么n0-2，但是该点变为叶子结点，n0+1，最后为n0-1，同时n2-1，等式依然成立。
二叉树的遍历操作（通过给定的遍历序列模拟建树过程）：
对于二叉树的遍历，给定其前序序列和后序序列不能确定该二叉树：
例：
已知前序遍历序列为ABC，后序遍历序列为CBA：
满足条件的二叉树：
已知一棵二叉树的前序序列和中序序列，可以唯一确定这棵二叉树：
例：
前序：A B C D E F G H I中序：B C A E D G H F I
由根节点：
前序：B C
中序：B C
依次循环查找：
前序： D E F G H I
中序： E D G H F I
直到最后求出解。
void create(char preorder[],char inorder[],int start_p, int end_p,int start_i,int end_i, char data[],int root){
if(start_p>end_p)
return ;
else{
int k;
for(int i=start_i;i<=end_i;i++){
if(inorder[i]==preorder[start_p]){
k=i;
break;
}
}
data[root]=preorder[start_p];
create(preorder,inorder,start_p+1,start_p+k-start_i,start_i,k-1,data, 2*root);//左子树遍历填充
create(preorder,inorder,start_p+k-start_i+1,end_p,k+1,end_i,data,2*root+1); //右子树遍历填充
}
return ;
}
int main(){
char * data;
int total=1;
char preorder[100],inorder[100];
cin>>preorder>>inorder;
int length=0;
while(preorder[length]!=' ')
length++; //求出树的深度（结点个数）
data=new char[pow(2,length+1)]; //利用结点个数模拟树的结构（对应深度为length时，树的length层最多结点个数为2的length次，那么总的结点个数最多为2的（length+1）次-1，这里直接写2的（length+1）次）
memset(data,' ',pow(2,length+1)); //首先将树的模型搭建好，然后设该树为一棵空树，填充相应数据即可得到所求树
create(preorder,inorder,0,length-1,0,length-1,data,1); //创建该树（在树的模型上填充数据建立该树）
order(1,data);
return 0;
}
我们通过上面的程序可以看出，上面的思想是模拟建树的过程，模拟建立了一棵二叉树的结构放在那里用于填充数据，但是当我们数据量较小时（比如斜树），我们就会造成不必要的空间浪费（存在很多空节点）。因此二叉树的顺序存储结构一般仅存储完全二叉树。
下面我们
采用二叉链表的基本思想去实现树的建立：
具有n个结点的二叉链表中，有n+1个空指针。
二叉链表的储存声明：
template <class T>
class BiTree
{
public:
BiTree();
~BiTree( );
void PreOrder(){PreOrder(root);}
void InOrder() {InOrder(root);}
void PostOrder() {PostOrder(root);}
void LevelOrder(){LeverOrder(root)};
private:
BiNode<T> *root;
BiNode<T> * Creat( );
void Release(BiNode<T> *root);
void PreOrder(BiNode<T> *root);
void InOrder(BiNode<T> *root);
void PostOrder(BiNode<T> *root);
void LevelOrder(BiNode<T> *root);
};
但是很明显二叉链表只适合于求树上某结点的孩子，却不适合找某结点的双亲，我们可以在二叉链表的基础上添加结点的双亲，使之成为三叉链表，以便我们对某结点双亲的求取。
三叉链表：
结点结构：
代码实现：（跟二叉链表实际是一样的，只不过传参时把父节点传给子节点，子节点记录下来继续递归传递）
template <class T>
BiNode<T> * BiTree<T>::Creat(BiNode<T> * &root ,BiNode<T> *parent){
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
root->parent=parent;
Creat(root->lchild,root ); //递归建立左子树
Creat(root->rchild,root); //递归建立右子树
}
return root;
}
template<class T>
BiTree<T>::BiTree( int i)
{
number=0;
Creat(root,NULL); //根节点父节点为空（根节点不存在父节点）
}
二叉树遍历分为递归调用与非递归调用两种：
在前中后序遍历中，递归调用的使用方式都是类似的，只是调用的顺序有所不同。
对于非递归调用：（遵循从左至右的遍历原则，体现深度优先搜索的思想）
在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针是非递归调用的关键。
我们可以利用栈的存储结构性质来实现非递归调用：栈是实现递归的最常用的结构。
前序遍历非递归算法：
思想：
遇到一个结点，就访问该结点，并把此结点推入栈中，然后遍历它的左子树；
遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。
代码实现：
template <class T>
void BiTree::PreOrder(BiNode<T> *root) {
SeqStack<BiNode<T> *> s;
while (root!=NULL | | !s.empty()) { //结点指向为空（结点处不存在子树）且栈空（不存在后继结点）则树空（遍历完毕）
while (root!= NULL) {
cout<<root->data;
s.push=root; //访问节点后压栈
root=root->lchild; //然后遍历其左子树
//左子树遍历完毕后指针指向为空，跳出内部while进入if语句访问父节点的右子树
}
if (!s.empty()) {
root=s.pop(); //删除该节点（空节点），访问其父节点的右子树
root=root->rchild;
}
}
}
中序遍历非递归算法：
当我们遇到树的结点时，我们不能立刻去访问它，而是先去访问该节点的左子树，那么我们在遇到该节点时不访问（不输出），访问过程放到遍历左子树完毕后（再输出），即每次遇到后先将其压栈，然后遍历左子树直至为空，然后访问输出节点后继续访问右子树。（遇见节点不等于访问输出节点）
后续遍历非递归算法1：
与前序和中序遍历有所不同的是后续遍历先访问其左子树后访问其右子树，最后访问该节点，但是我们遇到该节点一共两次（第一次是从其父节点遍历过来，另一次是从其左子树遍历完成后返回到该节点，最后一次遇见（右子树遍历完毕后返回）便成了访问输出），对于栈来说可以设置一个flag标志：
flag=1代表遍历完左子树，该点不能访问，flag=2代表遍历完右子树，该节点可以访问。
具体过程：
设根指针为bt:
若bt不等于NULL，则bt及标志flag（置为1）入栈，遍历其左子树。
若bt等于NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕（简单的说就是栈不空表示该节点还没有被访问），若栈顶的标志flag=1，则表明栈顶节点的左子树已遍历完毕，将flag修改为2，并遍历栈顶点的右子树；若栈顶点的标志flag=2，则表明栈顶点的右子树也遍历完毕，输出栈顶结点并压出即可。
代码实现：
template<class DataType>
void BiTree<DataType>::PostORder(BiNode<DataType>*bt){
top=-1; //采用顺序栈，并假定栈不会发生上溢
while(bt!=NULL||top!=-1){
while(bt!=NULL){
top++;
s[top].ptr=bt;
s[top].flag=1;
bt=bt->lchild;
}
while(top!=-1&&s[top].flag==2){
bt=s[top--].ptr; //相当于出栈操作
cout<<bt->data;
}
if(top!=-1){ //与上述while循环不可颠倒（不是递归操作，无法直接调用，如果if写在前面便不会访问右子树，而是直接输出该节点返回该节点的父节点了）
s[top].flag=2;
bt=s[top].ptr->rchild;
}
}
}
后续遍历非递归算法2：
需要用栈实现，根据后续遍历的要求及栈操作的特点（FILO），依次将
根结点、根结点的右儿子、根节点的左儿子入栈（不访问），当结点出栈时再进行访问。
当栈顶出现叶子结点时，直接进行出栈操作，当刚出栈元素和栈顶元素之间关系是“儿子-双亲”关系时，进行出栈操作。
代码实现：
void tree::T_print(bnode *bt){
stack<bnode*> s;
bnode *cur， *pre=NULL;
if (root==NULL) return;
s.push(bt);
while (!s.empty()) {
cur=s.top();
if ((cur->Lchild==NULL&&cur->Rchild==NULL) ||(pre!=NULL&&(pre==cur->Lchild||pre==cur->Rchild)))
{
cout<<cur->data; s.pop(); pre=cur; //每次pre都会指向刚刚出栈的结点（然后如果刚出栈元素和栈顶元素之间关系是“儿子-双亲”关系时，直接再进行出栈操作）
}
else
{
if (cur->Rchild!=NULL) s.push(cur->Rchild);
if (cur->Lchild!=NULL) s.push(cur->Lchild);
}
}
}
二叉树的层序遍历：（利用队列来进行遍历）
1.队列Q初始化；
2. 如果二叉树非空，将根指针入队；
3. 循环直到队列Q为空
3.1 q=队列Q的队头元素出队；
3.2 访问结点q的数据域；
3.3 若结点q存在左孩子，则将左孩子指针入队；
3.4 若结点q存在右孩子，则将右孩子指针入队；
代码实现：
#include <queue>
using namespace std;
template<class T>
void BiTree<T>::LevelOrder(BinaryTreeNode<T>* root){
queue<BiTreeNode<T>*> aQueue;
if(root)
aQueue.push(root);
while(!aQueue.empty())
{
root=aQueue.front(); //取队列首结点
aQueue.pop();
cout<<pointer->data;//访问当前结点
if(root->lchild) //左子树进队列
aQueue.push(root->lchild);
if(root->rchild) //右子树进队列
aQueue.push(root->rchild);
}//end while
}
上面对二叉树的遍历操作完成后：
我们通过遍历序列来建立一棵二叉树：
为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的
扩展二叉树:
扩展二叉树的前序遍历序列:A B # D # # C # #
代码实现：
template <class T>
void BiTree<T>::Creat(BiNode<T> * &root )
{
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
Creat(root->lchild ); //递归建立左子树
Creat(root->rchild); //递归建立右子树
}
}
对于一棵树来说，在我们进行操作完成之后，我们要对其进行析构销毁，避免造成空间的浪费：
二叉树的析构：
template<class T>
void BiTree<T>::Release(BiNode<T>* root){
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
树、森林与二叉树的转换：
我们一开始的思路是简化分析树，森林，研究最简单的二叉树。那么我们在研究完二叉树的基本构造与析构和不同的遍历操作之后，又该把问题回到相对复杂的树与森林上，下面我们通过对树和森林与二叉树之间的转换，将树与森林问题转换为相对简单的二叉树问题进行求解。
树与二叉树之间的转换：
树：兄弟关系 <–> 二叉树：双亲和右孩子
树：双亲和长子 <–> 二叉树：双亲和左孩子
树转化为二叉树具体实现过程：
1.兄弟加线.
2.保留双亲与第一孩子连线,删去与其他孩子的连线.
3.顺时针转动,使之层次分明.
例：
性质：左儿子右兄弟：
树的前序遍历等价于二叉树的前序遍历：
只是兄弟之间加线，兄弟变成父子关系（长子为父，其余为孩子），而且父节点与长子之间的连线是确定的，这样的构造并没有影响前序遍历的顺序，所以结果是不变的。
树的后序遍历等价于二叉树的中序遍历：
例：
森林转换为二叉树 ：
⑴ 将森林中的每棵树转换成二叉树；
⑵ 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。
例：
二叉树转化为树或森林：
⑴ 加线：若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；
⑵ 去线：删去原二叉树中所有的双亲结点与右孩子结点的连线；
⑶ 层次调整：整理由⑴、⑵两步所得到的树或森林，使之层次分明。
例：
最优二叉树-哈夫曼树及哈夫曼编码：
叶子结点的权值：对叶子结点赋予的一个有意义的数值量。
二叉树的带权路径长度（weighted path length（WPL））：
设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。
哈夫曼树：
给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。（不一定唯一）
哈夫曼树的特点：
- 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
- 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。（由哈夫曼树的构造决定的）
哈夫曼算法基本思想：
⑴ 初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；
⑵ 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；
⑶ 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；
⑷ 重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。
根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，其中有n-1个是非叶子结点，它们是在n-1次合并中生成的。
那我们就可以设置一个数组huffTree[2n-1]保存哈夫曼树中各点的信息：
其中：
weight：权值域，保存该结点的权值；
lchild：指针域，结点的左孩子结点在数组中的下标；
rchild：指针域，结点的右孩子结点在数组中的下标；
parent：指针域，该结点的双亲结点在数组中的下标。
struct element
{ int weight;
int lchild, rchild, parent;
};
例：
代码实现：
void HuffmanTree(element huffTree[ ], int w[ ], int n ) {
for (i=0; i<2*n-1; i++) { //初始化构造：双亲结点与孩子结点都设为-1（其中有n个叶子结点，需要2*n-1个结点位置）
huffTree [i].parent= -1;
huffTree [i].lchild= -1;
huffTree [i].rchild= -1;
}
for (i=0; i<n; i++) //初始化构造：前n个结点初始化构造为带权的叶子结点
huffTree [i].weight=w[i];
for (k=n; k<2*n-1; k++) { //对n到2*n-1这n-1个结点进行构造，每次寻找权值最小的两个结点构成一棵新树
Select(huffTree, &i1, &i2);
huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;
huffTree[i1].parent=k;
huffTree[i2].parent=k;
huffTree[k].lchild=i1;
huffTree[k].rchild=i2;
}
}
哈夫曼树应用——哈夫曼编码：
编码：给每一个对象标记一个二进制位串来表示一组对象。
例：ASCII，指令系统
等长编码：表示一组对象的二进制位串的长度相等。
不等长编码：表示一组对象的二进制位串的长度不相等。
前缀编码：
一组编码中任一编码都不是其它任何一个编码的前缀 。
前缀编码保证了在解码时不会有多种可能。
例：
一组字符{A, B, C, D, E, F, G}出现的频率分别是{9, 11, 5, 7, 8, 2, 3}，设计最经济的编码方案。
线索二叉树：
（合理利用二叉链表的空链域， 将遍历过程中结点的前驱、 后继信息保存下来，也便于查找结点的前驱和后继）
我们知道，在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用的非空链域，其余n+1个链域是空的。
我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱和后继信息。
线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；
线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；
线索二叉树：加上线索的二叉树称为线索二叉树。
例：
结点结构：
基本思想：
在遍历的过程中完成线索化
可以采用前序、中序、后序遍历建立前序线索二叉树、中序线索二叉树和后序线索二叉树。