二叉树是一种常用的数据结构，熟练掌握二叉树的各种算法，是必须的。本科时学过数据结构课程，但因当时课程繁多，且对很多概念理论不甚熟悉，数据结构课程也是得过且过，虽言考试顺利通过，但有许多盲点，还有很多知识点，虽然知道其基本思路，但一旦说要动手实现，抓耳挠腮半响，还是一堆的error。痛定思痛，与其忍受这种痛苦，还不若痛下决心将其一一击破。

问题描述一：
假设二叉树采用二叉链存储结构，设计一个算法，输出从每个叶子结点到根结点的路径。

有一个好的想法是简单，但要实现它可不是容易的事，这在编程中经常体现。我使用的李春葆李老师的《数据结构》一书中使用了队列实现，设计的队列为非循环队列，将所有已扫描过的结点指针进队列，并在队列中保存双亲结点的位置。当找到一个叶子结点时，在队列中通过双亲结点的位置输出该叶子结点到根结点的路径。

这种方法是可行的。但因为我先前用堆实现过二叉树遍历的非递归算法，这一次我便想尝试看用堆是否能够实现。实现思想是先将根结点的所有左子结点入栈，并置所有栈内结点的标记为0，代表是其右节点还未访问，而后弹出栈顶结点，输出其到根结点路径，再取栈顶结点（它应该是刚弹出栈顶结点之父结点），将其标记置1, 代表其右结点已经访问，然后将其右子节点与其右子结点的所有左子结点入栈，并置入栈结点标记为0, 弹出栈顶结点，输出其到根结点路径，并不断弹出标记为1的栈顶结点，再取栈顶结点，将其标记置1,代表其右结点已经访问，如上循环，直至栈空。

简要思想是：将所有左结点入栈，输出，弹出左右结点都已访问的父结点，再访问右结点。

算法实现如下：
void leaf2root(BiNode* _node)
{
struct stack
{
BiNode* data;
int flag;
}st[MAX];
int top=-1;
BiNode* p, *s;

while(_node!=NULL)
{
top++;
st[top].data=_node;
st[top].flag=0;
_node=_node->lchild;
} //压入根结点及其所有左子结点，并设标记为0

while(top>-1)
{
p=st[top].data;
if(p->lchild==NULL&&p->rchild==NULL)
{
for(int i=top;i>=0;i--)
cout<<st[i].data->data<<"->";
cout<<endl;
top--;
} //输出叶子结点到根结点的路径

while(top>-1&&st[top].flag==1)
{
top--;
} //如果栈顶结点是父节点，且其左右子结点均已访问过，就弹出之

if(top>-1)
{
st[top].flag=1;
p=st[top].data;
s=p->rchild;
while(s!=NULL)
{
top++;
st[top].data=s;
st[top].flag=0;
s=s->lchild;
} //将栈顶结点的右子结点及其右子结点的所有左子结点压栈，并设标记为0
}
}
}

李老师的算法实现如下：
void leaf2root_1(BiNode* _node)
{
struct snode
{
BiNode* node;
int parent;
}q[MAX];
int front, rear, p;
front=rear=-1;
rear++;
q[rear].node=_node;
q[rear].parent=-1;
while(front<rear)
{
front++;
_node=q[front].node;
if(_node->lchild==NULL&&_node->rchild==NULL)
{
p=front;
while(q[p].parent!=-1)
{
cout<<q[p].node->data<<"->";
p=q[p].parent;
}
cout<<q[p].node->data<<endl;
}
if(_node->lchild!=NULL)
{
rear++;
q[rear].node=_node->lchild;
q[rear].parent=front;
}
if(_node->rchild!=NULL)
{
rear++;
q[rear].node=_node->rchild;
q[rear].parent=front;
}
}
}

问题描述二：如何创建二叉树？

二叉树的创建既可用递归算法实现，也可用非递归实现。

递归实现：
输入采用先序输入，先构建根结点，而后左结点，右结点
void create_bitree(BiNode*& _node)
{
char c;
cin>>c;
if(c=='*')
{
_node=NULL;
return;
}
else
{
_node=(BiNode*)malloc(sizeof(BiNode));
_node->data=c;
_node->lchild=NULL;
_node->rchild=NULL;
create_bitree(_node->lchild);
create_bitree(_node->rchild);
}
return;
}

非递归实现：
非递归实现使用一个string类型的字符串，将二叉树序列用字符串表示起来，用逗号将左右结点隔开，用（）将左右结点包括，表示一个结点的子结点。遍历输入字符串，若为（，说明下一个输入应该是左结点，若为，，说明下一个结点应该是右结点，若为），说明有一个结点输入完毕，可以弹栈；若为字母，压栈。。。
void create_bitree_1(BiNode*& root, string str)
{
BiNode* st[MAX], *p;
int top=-1,flag=0;
string::size_type i=0;
p=root;
while(i<str.size())
{
switch(str[i])
{
case '(':
flag=1;
break;
case ',':
if(str[i-1]!='(')
top--;
flag=2;
break;
case ')':
if(str[i-1]!=',')
top--;
break;
default :
p=(BiNode*)malloc(sizeof(BiNode));
p->data=str[i];
p->lchild=NULL;
p->rchild=NULL;

if(flag==1)
{
st[top]->lchild=p;
}

if(flag==2)
{
st[top]->rchild=p;
}
top++;
st[top]=p;
if(i==0)
root=p;
p=NULL;
}
i++;
}
}

问题描述3：先序，中序，后序实现二叉树遍历

遍历也有递归及非递归实现，递归实现起来较为简单，非递归实现用栈保存信息，较为麻烦，但常是考点。

递归算法：
void pre_order(BiNode* _node)
{
if(_node==NULL)
return;
cout<data<<" ";
pre_order(_node->lchild);
pre_order(_node->rchild);
}

void in_order(BiNode* _node)
{
if(_node==NULL)
return;
in_order(_node->lchild);
cout<data<<" ";
in_order(_node->rchild);
}

void post_order(BiNode* _node)
{
if(_node==NULL)
return;
post_order(_node->lchild);
post_order(_node->rchild);
cout<data<<" ";
}

非递归算法
先序算法1：
先将（根结点指针，1）进栈；
while（栈不空）
{
if（栈顶元素未访问过）
{
p=st[top].pt; 退栈；
将*p结点的右孩子结点指针进栈，tag=1;
将*p结点的左孩子结点指针进栈，tag=1;
将*p结点指针进栈，tag=0;
}
else if（栈顶元素可直接访问）
访问栈顶元素并退栈；
}
其中心思想也就是先将右孩子结点，再左孩子结点一一进栈，最后父亲结点进栈，始终保证父亲结点在孩子结点之前
void pre_order_1(BiNode* _node)
{
struct stack_node
{
bool flag;
BiNode* pt;
}stack[MAX];
int top=-1;

top++;
stack[top].flag=false;
stack[top].pt=_node;

while(top>-1)
{
if(!stack[top].flag)
{
BiNode* p=stack[top].pt;
top--;
if(p!=NULL)
{
top++;
stack[top].flag=false;
stack[top].pt=p->rchild;
top++;
stack[top].flag=false;
stack[top].pt=p->lchild;
top++;
stack[top].flag=true;
stack[top].pt=p;
}
}

if(stack[top].flag&&top>=0)
{
cout<<(stack[top].pt)->data<<" ";
top--;
}
}
}

中序算法1
中序算法1和先序算法1的思想相似，不过进栈顺序有些变化，它先将右孩子结点进栈，再父亲，再左孩子结点进栈
void in_order_1(BiNode* _node)
{
struct stack_node
{
bool flag;
BiNode* pt;
}stack[MAX];
int top=-1;

top++;
stack[top].flag=false;
stack[top].pt=_node;

while(top>-1)
{
if(!stack[top].flag)
{
BiNode* p=stack[top].pt;
top--;

if(p!=NULL)
{
top++;
stack[top].flag=false;
stack[top].pt=p->rchild;
top++;
stack[top].flag=true;
stack[top].pt=p;
top++;
stack[top].flag=false;
stack[top].pt=p->lchild;
}
}

if(stack[top].flag&&top>-1)
{
cout<<stack[top].pt->data<<" ";
top--;
}
}
}

后序算法1
后序算法1和先序算法1的思想亦类似，不过进栈顺序不一样，它先将父亲结点进栈，再右孩子，再左孩子进栈
void post_order_1(BiNode* _node)
{
struct stack_node
{
bool flag;
BiNode* pt;
}stack[MAX];
int top=-1;

top++;
stack[top].flag=false;
stack[top].pt=_node;

while(top>-1)
{
if(stack[top].flag==false)
{
BiNode* p=stack[top].pt;
top--;

if(p!=NULL)
{
top++;
stack[top].flag=true;
stack[top].pt=p;
top++;
stack[top].flag=false;
stack[top].pt=p->rchild;
top++;
stack[top].flag=false;
stack[top].pt=p->lchild;
}
}

if(stack[top].flag&&top>-1)
{
cout<<stack[top].pt->data<<" ";
top--;
}
}
}

先序算法2：
由先序遍历过程可知，先访问根结点，再访问左子树，最后访问右子树，因此，先将根结点进栈，在栈不空时循环，出栈p, 访问*p结点，将其右孩子结点进栈，再将左孩子结点进栈
void post_order_1(BiNode* _node)
{
struct stack_node
{
bool flag;
BiNode* pt;
}stack[MAX];
int top=-1;

top++;
stack[top].flag=false;
stack[top].pt=_node;

while(top>-1)
{
if(stack[top].flag==false)
{
BiNode* p=stack[top].pt;
top--;

if(p!=NULL)
{
top++;
stack[top].flag=true;
stack[top].pt=p;
top++;
stack[top].flag=false;
stack[top].pt=p->rchild;
top++;
stack[top].flag=false;
stack[top].pt=p->lchild;
}
}

if(stack[top].flag&&top>-1)
{
cout<<stack[top].pt->data<<" ";
top--;
}
}
}

中序遍历算法2：
由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点将它们一一进栈，然后出栈一个结点，显然该结点没有左孩子结点或者左孩子结点已访问过，访问它，然后将该结点的右孩子结点，进栈，再将该右孩子结点的所有左孩子结点一一进栈，如此这样，直到栈空为止
void in_order_2(BiNode* _node)
{
BiNode* st[MAX],*p;
int top=-1;

if(_node!=NULL)
{
p=_node;

while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
st[top]=p;
p=p->lchild;
}

if(top>-1)
{
p=st[top];
top--;
cout< data<<" ";
p=p->rchild;
}
}
}
}

后序遍历算法2：
后序遍历采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点一一进栈，出栈一个结点，将该结点的右孩子结点入栈，再扫描该右孩子结点的所有左结点入栈。当一个结点的左右孩子结点均访问后再访问该结点，如此这样，直到栈空。显然，难点在于如何判断左右结点俱已访问。
void post_order_2(BiNode* _node)
{
BiNode* st[MAX],*p;
int flag,top=-1;
if(_node!=NULL)
{
do
{
while(_node!=NULL)
{
top++;
st[top]=_node;
_node=_node->lchild;
}

p=NULL;
flag=1;

while(top!=-1&&flag)
{
_node=st[top];
if(_node->rchild==p)
{
cout<data<<" ";
top--;
p=_node;
}
else
{
_node=_node->rchild;
flag=0;
}
}
}while(top!=-1);
}
}

问题描述3：如何销毁二叉树？
在二叉树创建时，手动申请了内存，因此也要手动进行释放，释放过程中先保存父亲结点指针，将父亲结点占用空间删除后，再将左孩子及右孩子结点占用的空间删除
void del_tree(BiNode* _node)
{
BiNode* left;
BiNode* right;
if(_node!=NULL)
{
left=_node->lchild;
right=_node->rchild;
delete _node;

del_tree(left);
del_tree(right);
}
}

以下是一些简单的算法实现，实现诸如二叉树的高度，宽度等等
BiNode* find_node(BiNode* _node, char c)
{
if(_node==NULL)
return NULL;
else if(_node->data==c)
return _node;
else
{
if(find_node(_node->lchild,c)!=NULL)
return _node->lchild;
else
return find_node(_node->rchild,c);
}
}

BiNode* lchild(BiNode* _node)
{
return _node->lchild;
}

BiNode* rchild(BiNode* _node)
{
return _node->rchild;
}

int tree_height(BiNode* _node)
{
if(_node==NULL)
return 0;
int left=tree_height(_node->lchild);
int right=tree_height(_node->rchild);
return left>right?left+1:right+1;;
}

int tree_width(BiNode* _node)
{
if(_node==NULL)
return 0;
if(_node->lchild==NULL&&_node->rchild==NULL)
return 1;
int left=tree_width(_node->lchild);
int right=tree_width(_node->rchild);
return left+right;
}

int node_total(BiNode* _node)
{
if(_node==NULL)
return 0;
int left=node_total(_node->lchild);
int right=node_total(_node->rchild);
return left+right+1;
}

问题描述4：如何层次遍历二叉树？
层次遍历有两种方法
第一种方法，我们可以使用两个栈a,和b
开始将根结点压入栈a
while(栈a及栈b都不空)
{
while(栈a不空)
{
将a中所有元素弹栈，输出
将a中所有元素的孩子结点压入栈b
}
while(栈b不空)
{
将b中所有元素弹栈，输出
将b中所有元素的孩子结点压入栈a
}
}
算法实现如下：
void layer_order(BiNode* _node)
{
BiNode* st_1[MAX], *st_2[MAX],*p;
int top_1=-1,top_2=-1;

if(_node==NULL)
return;
top_1++;
st_1[top_1]=_node;

while(top_1>-1||top_2>-1)
{
while(top_1>-1)
{
p=st_1[top_1];
top_1--;
cout< data<<" ";
if(p->rchild!=NULL)
{
top_2++;
st_2[top_2]=p->rchild;
}
if(p->lchild!=NULL)
{
top_2++;
st_2[top_2]=p->lchild;
}
}
cout<<endl;
while(top_2>-1)
{
p=st_2[top_2];
top_2--;
cout< data<<" ";
if(p->lchild!=NULL)
{
top_1++;
st_1[top_1]=p->lchild;
}
if(p->rchild!=NULL)
{
top_1++;
st_1[top_1]=p->rchild;
}
}
cout<<endl;
}
}

第二种方法稍难理解些，采用递归算法，设h返回p所指结点的高度,其初值为0.找到指定结点时，返回其层次，否则返回0.lh作为一个中间变量在计算搜索层次时使用，其初值为1.
void level(BiNode* _node,char data,int &h, int lh)
{
if(_node==NULL)
h=0;
else if(_node->data==data)
h=lh;
else
{
level(_node->lchild,data,h,lh+1);
if(h==0)
level(_node->rchild,data,h,lh+1);
}
}

问题描述5：输出二叉树
其实以上的遍历算法也对二叉树进行了输出，但是少了一种输出方法，在创建的时候，我们曾用过A（B，C）这种类似的格式来创建二叉树，而今我们也想以这种方式进行输出，那该怎么办呢？
void disp_tree(BiNode* _node)
{
if(_node!=NULL)
{
cout<data;
if(_node->lchild==NULL&&_node->rchild==NULL)
return;
cout<<"(";
if(_node->lchild!=NULL)
disp_tree(_node->lchild);
cout<<",";
if(_node->rchild!=NULL)
disp_tree(_node->rchild);
cout<<")";
}
}

问题描述6：如何构建哈夫曼树
构建哈夫曼树稍为简单
首先创建一个vector，用来保存哈夫曼树结点的指针。
while(vector的大小！＝1）
{
找出vector中最小的两个元素，用left right表示；
将最小的两个元素从vector中删除；
取left right的权重和，新创建一个结点，插入vector;
}
HTNode* create_HTTree(vector<HTNode*>& list_htnode)
{
int smallest1,smallest2;
vector<HTNode*>::const_iterator beg;
HTNode* left,*right;
while(list_htnode.size()>1)
{
smallest1=htnode_smallest(list_htnode);
left=*(list_htnode.begin()+smallest1);
list_htnode.erase(list_htnode.begin()+smallest1);
smallest2=htnode_smallest(list_htnode);
right=*(list_htnode.begin()+smallest2);
list_htnode.erase(list_htnode.begin()+smallest2);

HTNode* temp_root=(HTNode*)malloc(sizeof(HTNode));
temp_root->weight=left->weight+right->weight;
temp_root->lchild=left;
temp_root->rchild=right;
list_htnode.push_back(temp_root);
}
return list_htnode[0];
}

以上算法我都一一实现过，对于二叉树的知识点涵盖较全，除了没有线索二叉树以及中后序创建二叉树外。一一实现大约花费了我一个星期的工夫，花了这么长时间，也真是值了，终于把盲点清扫一空，把二叉树弄完，下一步开始图算法的清扫了。