愿你我都能与靠谱之人同行，也都能成为靠谱之人，一路向阳不负时光。
——文记
目录
二叉树
二叉树的遍历与线索化
树、森林和二叉树的关系
哈夫曼树及其应用
总结与提高
二叉树
二叉树的遍历与线索化
以二叉链表作为存储结构，讨论二叉树的遍历算法
1) 先序遍历
void PreOrder(BiTree root)
{ if (root!=NULL)
{Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
2) 中序遍历
void InOrder(BiTree root)
{ if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
3) 后序遍历
void PostOrder(BiTree root)
{ if(root!=NULL)
{
PostOrder(root ->LChild);
PostOrder(root ->RChild);
}
}
以中序遍历为例来说明中序遍历二叉树的递归过程
遍历算法应用 1.输出二叉树种的结点
【算法思想】输出二叉树中的结点并无次序要求，因此可用三种遍历算法中的任何一种完成，只需将访问操作具体变为打印操作即可。下面给出采用前序遍历实现的算法。
【算法描述】
void PreOrder(BiTree root)
{
if (root!=NULL)
{
printf (root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
2.输出二叉树中的叶子结点
【算法思想】输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否满足叶子结点的条件。
【算法描述】
void PreOrder(BiTree root)
{
if (root!=NULL)
{
if (root ->LChild==NULL && root ->RChild==NULL)
printf (root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
3.统计叶子结点数目
方法一：【算法思想】统计二叉树中的叶子结点数目并无次序要求，因此可用三种遍历算法中的任何一种完成，只需将访问操作具体变为判断是否为叶子结点及统计操作即可。
【算法描述】
void leaf(BiTree root)
{
if(root!=NULL)
{
leaf(root->LChild);
leaf(root->RChild);
if (root ->LChild==NULL && root ->RChild==NULL)
LeafCount++;
}
}
方法二： 【算法思想】采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和。
【算法描述】
int leaf(BiTree root)
{
int LeafCount;
if(root==NULL)
LeafCount =0;
else if ((root->LChild==NULL)&&(root->RChild==NULL))
LeafCount =1;
else
LeafCount =leaf(root->LChild)+leaf(root->RChild);
return LeafCount;
}
4.建立二叉链表方式存储的二叉树
【算法思想】采用类似先序遍历的递归算法，首先读入当前根结点的数据，如果是’.’则将当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用当前根结点的左子域和右子域进行递归调用，创建左右子树。
【算法描述】
void CreateBiTree(BiTree *bt)
{ char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild));
CreateBiTree(&((*bt)->RChild));
}
}
5.求二叉树的高度
设函数表示二叉树bt的高度，则递归定义如下:
若bt为空，则高度为0
若bt非空，其高度应为其左右子树高度的最大值加1
【算法思想】二叉树bt的高度可以递归定义如下：
若bt为空，则高度为0
若bt非空，其高度应为其左右子树高度的最大值加1
【算法描述】
int PostTreeDepth(BiTree bt)
{
int hl, hr, max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max=hl>hr?hl:hr;
return(max+1);
}
else return(0);
}
求二叉树的高度是也可用前序遍历的方式实现。 【算法思想】二叉树的高度（深度）为二叉树中结点层次的最大值。设根结点为第1层的结点，所有h层的结点的左右孩子结点在h+1层。故可以通过遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的高度。
【算法描述】
void PreTreeDepth(BiTeee bt, int h)
{
if(bt!=NULL)
{
if(h>depth) depth = h;
PreTreeDepth(bt->Lchild, h+1);
PreTreeDepth(bt->Rchild, h+1);
}
}
6. 按树状打印的二叉树
假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母，要求实现如下图的打印结果。
分析：这是二叉树的横向显示问题，横向显示应是竖向显示的900旋转，又由于二叉树的横向显示算法一定是中序遍历算法，所以把横向显示的二叉树算法改为RDL结构，实现算法为：
【算法思想】 （1）二叉树的横向显示应是二叉树竖向显示的90。旋转。分析图6.15图示可知，这种树形打印格式要求先打印右子树，再打印根，最后打印左子树，按由上而下顺序看，其输出的结点序列为：CFEADB，这恰为逆中序顺序。解决二叉树的横向显示问题采用“逆中序”遍历框架，所以横向显示二叉树算法为先右子树、再根结点、再左子树的RDL结构。 （2）在这种输出格式中，结点的左右位置与结点的层深有关，故算法中设置了一个表示当前根结点层深的参数，以控制输出结点的左右位置，每当递归进层时层深参数加1。这些操作应在访问根结点时实现。
【算法描述】
void PrintTree(BiTree bt, int nLayer)
{
if(bt = =NULL) return;
PrintTree(bt ->RChild, nLayer+1);
for(int i=0; idata);
PrintTree(bt ->LChild , nLayer+1);
}
思考：对二叉树实现左右子树交换，是否可采用先序、中序、后序中的任何一种算法实现，请简要说明原因。
基于栈的递归消除
