二叉树的遍历河北联合大学.docx
《二叉树的遍历河北联合大学.docx》由会员分享，可在线阅读，更多相关《二叉树的遍历河北联合大学.docx（16页珍藏版）》请在冰点文库上搜索。
二叉树的遍历河北联合大学
一、设计思想
程序代码是用两种算法实现二叉树的遍历，并输出遍历后的值。
第一种算法是递归实现二叉树的遍历
首先对于先序遍历，若二叉树为空，则空操作；否则，先访问根结点，然后先序遍历左子树，再先序遍历右子树。
对于中序遍历，若二叉树为空，则空操作；否则，先中序遍历左子树，然后访问根节点，在中序遍历右子树。
对于后续遍历，若二叉树为空，则空操作；否则，先后续遍历左子树，然后后续遍历右子树，在访问跟结点。
第二种算法是非递归实现二叉树的遍历
首先对于先序非递归遍历，先序遍历是借用栈来实现的。
先声明并初始化一个栈。
首先站在根节点上，对于根节点直接访问它，即打印它的data，再将其压入栈中，再判断栈stack是否为空，如果stack为空，则循环结束，遍历结束；如果不为空，则访问该根结点。
对于其它结点上如果它有左子，则访问它的左子，即打印其左子中成员data的值，然后再将该左子压入栈中；如果该结点没有左子，则弹出栈顶元素，站在其右子所在的结点上，再对当前所在的结点是否有左子进行判断，此时进入了一个循环。
循环结束的条件是栈stack和最后所在结点也为空。
此时，所输出的结果即为先序遍历的结果。
对于中序非递归遍历，也是借用一个栈来实现的，先声明并初始化一个栈，站到一个结点a上，如果当前结点a有左子b，则将其左子b入栈，如果其左子b还有左子c也将当前所站的结点b入栈，循环此过程直到遇到没有左子的结点p，此时弹出栈顶元素p，并访问它，即打印p结点的data，然后判断p结点的成员指针变量right，把right当成第一个开始的结点进行处理，直到最后栈为空且当前所站得结点为NULL，则中序遍历结束。
所输出的结果即为中序遍历的结果。
对于后续非递归遍历，它与前面两个不同，要使用两个栈来实现。
先分别声明并初始化两个栈stack和output，首先站在根结点上，对于根结点是直接将根节点压入栈stack中。
如果是其它的结点则首先要判断栈stack是否为空，然后才往下执行。
如果当前栈stack不为空，则将stack中得栈顶元素A弹出并压入到栈output中，现在站在结点A上，先依次判断它是否有左右子，如果它有左子，则将其左子压入栈stack中，如果它有右子也将它压入栈stack中，然后再判断栈stack是否为空，如果不为空，则弹出栈顶元素，并将其压入栈output中，再对该元素进行左子、右子的判断。
到最后，stack为空时，则此循环结束，而此时栈output中存储的则是已经按后续遍历排好的各个结点。
依次访问栈顶元素并弹出栈顶元素，直到此栈为空，则所输出的结果即为后序遍历的结果。
二、算法流程图
图1为使用递归实现的先序遍历二叉树的流程图。
图2为使用递归实现的中序遍历二叉树的流程图
图3为使用递归实现的中序遍历二叉树的流程图
图4为使用非递归实现的先序遍历二叉树的流程图
图5为使用非递归实现的中序遍历二叉树的流程图
图6为使用非递归实现的后序遍历二叉树的流程图
图1先序遍历二叉树流程图
图2中序遍历二叉树流程图
图3后序遍历二叉树流程图
图4非递归先序遍历二叉树流程图
图5非递归中序遍历二叉树流程图
图6非递归后序遍历二叉树流程图
三、源代码
下面给出的是用中缀表达式转后缀表达式再计算结果算法实现的程序的源代码：
#include
#include
#defineStackSize100//栈大小为StackSize
typedefstructtreenode*TreeNode;//定义treenode类型指针变量TreeNode
structtreenode//
{
chardata;//数值为char类型
TreeNodeleft;//左子
TreeNoderight;//右子
};
TreeNodeCreateTree（）//建立二叉树
{
intj;
TreeNodea,b,c,d,e,f,g,h;//声明结点
TreeNodenodes[8];//声明TreeNode类型数组
for（j=0;j<8;j++）//建立空结点
{
nodes[j]=（TreeNode）malloc（sizeof（TreeNode））;//为每个结点开辟内存
nodes[j]->left=NULL;//左子为空
nodes[j]->right=NULL;//右子为空
}
//以下为各个节点赋值
h=nodes[0];
d=nodes[1];
g=nodes[2];
b=nodes[3];
c=nodes[4];
f=nodes[5];
a=nodes[6];
e=nodes[7];
h->data='H';
h->left=d;
h->right=g;
d->data='D';
d->left=b;
d->right=c;
g->data='G';
g->right=f;
b->data='B';
b->right=a;
c->data='C';
f->data='F';
f->left=e;
a->data='A';
e->data='E';
returnh;//返回根节点
}
voidvisit（TreeNodep）//结点访问方法
{
printf（"%c",p->data）;//打印该结点数据
}
voidpreorder（TreeNoderoot）//先序遍历递归
{
TreeNodenode=root;//将根节点root赋给node
if（node!
=NULL）//判断当前node是否为空
{
visit（node）;//访问node
preorder（node->left）;//先序遍历左子树
preorder（node->right）;//先序遍历右子树
}
}
voidinorder（TreeNoderoot）//中序遍历递归
{
TreeNodenode=root;//将根节点root赋给node
if（node!
=NULL）//判断当前node是否为空
{
inorder（node->left）;//中序遍历左子树
visit（node）;//访问node
inorder（node->right）;//中序遍历右子树
}
}
voidpostorder（TreeNoderoot）//后续遍历递归
{
TreeNodenode=root;//将根节点root赋给node
if（node!
=NULL）//判断当前node是否为空
{
postorder（node->left）;//后序遍历左子树
postorder（node->right）;//后序遍历右子树
visit（node）;//访问node
}
}
typedefstruct//定义栈
{
TreeNodetext[StackSize];
inttop;//游标
}Stack;
voidInit（Stack*s）//初始化栈
{
s->top=-1;
}
voidpush（Stack*s,TreeNodep）//入栈函数
{
if（s->top{
s->top=s->top+1;//游标加1
s->text[s->top]=p;//将p赋给栈顶
}
else//如果栈已满
{
return;//退出
}
}
TreeNodepop（Stack*s）//出栈函数
{
TreeNodetemp;//定义临时结点
if（-1==s->top）//判断栈是否为空
{
returnNULL;//如果栈为空则返回NULL
}
else
{
temp=s->text[s->top];//将栈顶元素赋给temp
（s->top）--;//游标减1
returntemp;//返回值为栈顶元素
}
}
intnotEmpty（Stack*s）//栈判空函数
{
return（s->top）;//返回当前游标值
}
TreeNodepeek（Stack*s）//看栈顶
{
if（s->top>=0）
{
returns->text[s->top];//返回值为栈顶元素
}
}
voidpreOrder2（TreeNoderoot）//前序遍历非递归
{
TreeNodetemp=root->left;//将根节点的左子赋给temp
Stack*stack;//声明stack
Init（stack）;//初始化stack
visit（root）;//访问根节点
push（stack,root）;//将根节点压入栈stack中
while（notEmpty（stack）||temp!
=NULL）//判断stack和当前节点是否为空
{
while（temp!
=NULL）//判断当前节点temp是否为空
{
visit（temp）;//访问temp
push（stack,temp）;//将temp压入栈中
temp=temp->left;//将temp左子赋给temp
}
temp=pop（stack）;//将弹出的栈顶元素赋给temp
temp=temp->right;//将当前temp的右子赋给temp
}
}
voidinOrder2（TreeNoderoot）//中序遍历非递归
{
TreeNodetemp=root->left;//将根节点的左子赋给temp
Stack*stack;//声明栈stack
Init（stack）;//初始化stack
push（stack,root）;//将根节点root压入栈stack中
while（notEmpty（stack）||temp!
=NULL）//判断stack和当前节点是否为空
{
while（temp!
=NULL）//判断当前节点temp是否为空
{
push（stack,temp）;//将当前节点temp压入栈stack中
temp=temp->left;//将temp的左子赋给temp
}
temp=pop（stack）;//将弹出的栈顶元素赋给temp
visit（temp）;//访问temp
temp=temp->right;//将temp的右子赋给temp
}
}
voidpostOrder2（TreeNoderoot）//后续遍历非递归
{
TreeNodecurr=NULL;//声明并初始化curr
TreeNodepeektmp=NULL;//声明并初始化peektmp
Stack*stack;//声明stack
Stack*output;//声明output
Init（stack）;//初始化栈stack
Init（output）;//初始化栈output
push（stack,root）;//将根节点压入栈stack中
while（notEmpty（stack））//判断栈stack是否为空
{
curr=pop（stack）;//将弹出的栈顶元素赋给curr
push（output,curr）;//将curr压入栈output中
if（curr->left!
=NULL）//判断当前节点是否有左子
{
push（stack,curr->left）;//将当前节点的左子压入栈stack中
}
if（curr->right!
=NULL）//判断当前节点是否有右子
{
push（stack,curr->right）;//将当前节点的右子压入栈stack中
}
}
while（notEmpty（output））//判断栈output是否为空
{
peektmp=peek（output）;//看栈顶，并将栈顶元素赋给peektmp
visit（peektmp）;//访问peektmp
pop（output）;//output的栈顶元素出栈
}
}
intmain（）
{
TreeNoderoot;//声明TreeNode类型的根节点
root=CreateTree（）;//给根节点赋值
printf（"递归前序遍历:
"）;
preorder（root）;//调用先序递归函数
printf（"\n递归中序遍历:
"）;
inorder（root）;//调用中序递归函数
printf（"\n递归后序遍历:
"）;
postorder（root）;//调用后序递归函数
printf（"\n================================"）;
printf（"\n非递归前序遍历:
"）;
preOrder2（root）;//调用先序非递归函数
printf（"\n非递归中序遍历:
"）;
inOrder2（root）;//调用中序非递归函数
printf（"\n非递归后序遍历:
"）;
postOrder2（root）;//调用后序非递归函数
return0;
}
四、遇到的问题及解决
这部分我主要遇到了如下几个问题，其内容与解决方法如下所列：
●怎样建立二叉树?
要完成二叉树的遍历，首先得建立二叉树。
这是我开发中遇到的第一个难题。
二叉树有两种存储结构：
顺序存储结构和链式存储结构。
如果用顺序存储结构实现，是用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素，即将二叉树上的编号为i的结点元素存储在一维数组中下标为i-1的分量中，但是顺序存储结构即用数组实现仅适用于完全二叉树，这样的二叉树遍历不具有代表性。
所以我选择第二种实现方法，即链式存储结构来存储二叉树的各个结点。
我首先定义一个名为treenode的结构体，它里面包含三个成员：
data,left,right；data为char类型，left和right都为TreeNode类型的指针变量。
这样一个结点就可以实现二叉树中结点的功能了。
data为数据元素，left和right分别是指向左子和右子的指针变量。
然后到了具体建二叉树的环节，先声明一个TreeNode类型的数组nodes[]；然后用malloc函数在内存中为每一个结点分配一个长度为sizeof（TreeNode）的连续空间，并把结点中的指针变量赋值为NULL。
然后按照二叉树中结点的情况相应的各个已开辟内存的结点赋值。
如果结点没有左子、右子，则该结点中的两个指针变量可赋值为NULL。
●怎样实现二叉树的后序非递归遍历？
对于先序非递归遍历和中序非递归遍历很快都可以用一个栈做出来，而后序非递归遍历使用一个栈则相对复杂，我开始用的是一个栈来实现，里面又要用很多的辅助变量，十分复杂，而且算法也不易理解。
之后我尝试了用双栈来处理，竟然很快就能实现出来。
而且思路也很清晰，代码也很短。
升级会员 