第一篇：二叉树的遍历算法
实验三 二叉树遍历算法
一、实验目的
1． 进一步理解掌握二叉树二叉链表存储结构。2． 掌握二叉树遍历的递归与非递归算法。
二、实验要求
1． 认真阅读和掌握（先序、中序、后序和层次）遍历的递归与非递归算法。2． 上机调试（先序、中序、后序和层次）遍历的递归与非递归算法。3． 保存和打印出程序的运行结果，并结合程序进行分析。
4． 上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。
三、实验内容
先序、中序、后序遍历的递归与非递归算法和层次遍历的算法实现
程序：
#include “stdio.h” #include “stdlib.h” #include “conio.h” #define maxsize 100 typedef int datatype;typedef struct bnode{ datatype data;struct bnode *lchild,*rchild;}bnode,*btree;typedef struct { bnode *node;int flag;}DataType;typedef struct{ DataType data[maxsize];int top;}SeqStack,*PSeqStack;typedef struct { btree data[maxsize];int front,rear;}SeqQueue,*PSeqQueue;typedef struct{ btree data[maxsize];int top;}SeqStack1,*PSeqStack1;//建立一个二叉树
btree create(){ btree t;char ch;scanf(“%c”,&ch);if(ch=='?')
t=NULL;else {
t=(btree)malloc(sizeof(bnode));
t->data=ch;
t->lchild=create();
t->rchild=create();} return t;} //先序遍历
//入栈操作
void push1(PSeqStack1 s,btree sq){ if(s->top==maxsize-1)
printf(“栈满不得入栈”);else {
s->top++;
s->data[s->top]=sq;} } //出栈操作
void pop1(PSeqStack1 s,btree *sq){ if(s->top==-1)
printf(“栈空不得出栈”);else {
*sq=s->data[s->top];
s->top--;} } //先序遍历的递归算法
void PreOrder1(btree t){ if(t){
printf(“%c”,t->data);
PreOrder1(t->lchild);
PreOrder1(t->rchild);} } //先序遍历的非递归算法
void PreOrder2(btree t){ PSeqStack1 s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btree p=t;s->top=-1;while(p||s->top!=-1){
if(p)
{
printf(“%c”,p->data);
push1(s,p);
p=p->lchild;
}
else
{
pop1(s,&p);
p=p->rchild;
} } } //中序遍历的递归算法
void InOrder1(btree t){ if(t){
InOrder1(t->lchild);
printf(“%c”,t->data);
} } InOrder1(t->rchild);//中序遍历的非递归算法
void InOrder2(btree t){ PSeqStack1 s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btree p=t;s->top=-1;while(p||s->top!=-1){
if(p)
{
push1(s,p);
p=p->lchild;
}
else
{
pop1(s,&p);
printf(“%c”,p->data);
p=p->rchild;
} } } //后序遍历的递归算法
void PostOrder1(btree t){ if(t){
//t=(btree)malloc(sizeof(bnode));
PostOrder1(t->lchild);
PostOrder1(t->rchild);
printf(“%c”,t->data);} } //后序遍历的非递归算法
//入栈操作
void push(PSeqStack s,DataType sq){ if(s->top==maxsize-1)
printf(“栈满不得入栈”);else {
s->top++;
s->data[s->top]=sq;} } //出栈操作
void pop(PSeqStack s,DataType *sq){ if(s->top==-1)
printf(“栈空不得出栈”);else {
*sq=s->data[s->top];
s->top--;} } //后序遍历的非递归算法
void PostOrder2(btree t){ PSeqStack s;DataType sq;btree p=t;s=(PSeqStack)malloc(sizeof(SeqStack));s->top=-1;while(p||s->top!=-1){
if(p)
{
//s=(PSeqStack)malloc(sizeof(SeqStack));
sq.flag=0;sq.node=p;
push(s,sq);
p=p->lchild;
}
else
{
pop(s,&sq);
p=sq.node;
if(sq.flag==0)
{
sq.flag=1;
push(s,sq);
p=p->rchild;
}
}
} } else { printf(“%c”,p->data);p=NULL;} //按照层次遍历二叉树
//队列的初始化 PSeqQueue init(){ PSeqQueue q;q=(PSeqQueue)malloc(sizeof(SeqQueue));if(q){
q->front=0;
q->rear=0;} return q;} //判断队空
int empty(PSeqQueue q){ if(q&&q->front==q->rear)
return 1;else return 0;} //入队
void input(PSeqQueue q,btree x){ if((q->rear+1)%maxsize==q->front)
printf(“队满”);else {
q->rear=(q->rear+1)%maxsize;
q->data[q->rear]=x;} } //出队
void output(PSeqQueue q,btree *x){
} if(empty(q))printf(“队空”);else { q->front=(q->front+1)%maxsize;*x=q->data[q->front];} //按照层次遍历二叉树 void LevelOrder1(btree t){ PSeqQueue q;btree p=t;q=init();input(q,p);while(!empty(q)){
output(q,&p);
printf(“%c”,p->data);
if(p->lchild)
input(q,p->lchild);
if(p->rchild)
input(q,p->rchild);} } void main(){ btree t;t=create();printf(“此二叉树的先序递归遍历输出为：”);PreOrder1(t);printf(“n”);
printf(“此二叉树的先序非递归遍历输出为：”);PreOrder2(t);printf(“n”);printf(“此二叉树的中序递归遍历输出为：”);InOrder1(t);printf(“n”);printf(“此二叉树的中序递归遍历输出为：”);InOrder2(t);printf(“n”);printf(“此二叉树的后序递归遍历输出为：”);PostOrder1(t);printf(“n”);
} printf(“此二叉树的后序递归遍历输出为：”);PostOrder2(t);printf(“n”);printf(“此二叉树的层次遍历输出为：”);LevelOrder1(t);printf(“n”);程序结果：
五：实验心得、体会：
熟练地掌握递归算法的核心内容，能够较为熟练地使用递归算法的思想，了解二叉树的各种遍历的特点，了解各种遍历算法的递归算法和非递归算法。
第二篇：二叉树的遍历
# include
{ Etype data;
struct BiTNode *lch,*rch;
}BiTNode;/* 函数原形声明 */ BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void numb1(BiTNode *p);void numb2(BiTNode *p);void numb3(BiTNode *p);BiTNode *t;int n,n0,n1,n2;/* 主函数 */ main(){ char ch;int k;
do { printf(“nnn”);
printf(“nn
1.建立二叉树方法1 ”);
printf(“nn
2.建立二叉树方法2”);
printf(“nn
3.前序递归遍历二叉树”);
printf(“nn
4.中序递归遍历二叉树”);
printf(“nn
5.后序递归遍历二叉树”);
printf(“nn
6.前序计算树中结点个数”);
printf(“nn
7.中序计算树中结点个数”);
printf(“nn
8.后序计算树中结点个数”);
printf(“nn
9.结束程序运行”);
printf(“n======================================”);
printf(“n
请输入您的选择(1-9)”);scanf(“%d”,&k);
switch(k)
{ case 1:t=creat_bt1();break;/* 调用性质5建立二叉树算法 */
case 2:t=creat_bt2();break;/* 调用递归建立二叉树算法
*/
case 3: { preorder(t);
/* 调用前序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 4: { inorder(t);
/* 调用中序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 5: { postorder(t);
/* 调用后序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 6:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb1(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 7:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb2(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 8:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb3(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 9: exit(0);
} /* switch */
printf(“n----------------”);
}while(k>=1 && k<9);
printf(“n
再见！”);
printf(“n
打回车键，返回。”);ch=getch();} /* main */
/* 利用二叉树性质5，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1(){ BiTNode *t,*p,*v[20];int i,j;Etype e;
/* 输入结点的序号i、结点的数据e */
printf(“n 序号i,数据data=?”);scanf(“%d%d”,&i,&e);
while(i!=0 && e!=0)
/* 当 i ,e都为0时，结束循环
*/
{ p=(BiTNode *)malloc(sizeof(BiTNode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
/* 序号为1的结点是根 */
else{ j=i/2;
if(i%2==0)v[j]->lch=p;/* 序号为偶数，做左孩子*/
else
v[j]->rch=p;/* 序号为奇数，做右孩子*/
}
printf(“n i,data=?”);scanf(“%d%d”,&i,&e);
}
return(t);} /* creat_bt1 */ /* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2()
{ BiTNode *t;
int e;
printf(“n data=”);scanf(“%d”,&e);
if(e==0)t=NULL;
/* 对于0值，不分配新结点 */
else { t=(BiTNode *)malloc(sizeof(BiTNode));
t->data=e;
t->lch=creat_bt2();/* 左孩子获得新指针值
*/
t->rch=creat_bt2();/* 右孩子获得新指针值
*/
}
return(t);
} /* creat_bt2 */ /* 前序递归遍历二叉树
*/ void preorder(BiTNode *p){ if(p){
printf(“%3d”,p->data);
preorder(p->lch);
preorder(p->rch);
} } /* preorder */ /* 中序递归遍历二叉树
*/ void inorder(BiTNode *p){ if(p){ inorder(p->lch);
printf(“%3d”,p->data);
inorder(p->rch);
} } /* inorder */ /* 后序递归遍历二叉树
*/ void postorder(BiTNode *p){ if(p){
postorder(p->lch);
postorder(p->rch);
printf(“%3d”,p->data);
} } /* posorder */ /* 利用前序递归遍历二叉树的方法，计算树中结点个数 */ void numb1(BiTNode *p){ if(p){
{ printf(“%3d”,p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
numb1(p->lch);
numb1(p->rch);
} } /* numb1 */
/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */ void numb2(BiTNode *p){ if(p){ numb2(p->lch);
{ printf(“%3d”,p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
numb2(p->rch);
} } /* numb2 */
/* 利用后序递归遍历二叉树的方法，计算树中结点个数 */ void numb3(BiTNode *p){ if(p){ numb3(p->lch);
numb3(p->rch);
{ printf(“%3d”,p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
} } /* numb3 */
第三篇：二叉树遍历课程设计】
数据结构程序设计报告
学院： 班级： 学号：
姓名：
实验名称：二叉树的建立与遍历
一、实验目的：
1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法；
3.掌握二叉树的先序、中序、后序的递归实现方法。
二、实验内容和要求：
创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。
三、叉树的建立与遍历代码如下：
#include
};typedef struct tnode TNODE;
TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild;
int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch;printf(“建立二叉树，请输入结点:（#表示虚节点,!表示结束)n”);
ch=getchar();
while(ch!='!'){ if(ch!='#')
{ p=(TNODE *)malloc(sizeof(TNODE));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;rear++;
queue[rear]=p;//把非#的元素入队
if(rear==0)//如果是第一个元素，则作为根节点 {
} else {
if(counter%2==1)//奇数时与其双亲的左子树连接 {
}
if(counter%2==0)//偶数时与其双亲的右子树连接 {
queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter++;
}
}
}
}
front++;
counter++;
else//为#时，计数，但不连接结点 {
if(counter%2==0)
front++;counter++;
}
ch=getchar();} return root;void preorder(TNODE *bt)//先序遍历 {
if(bt!=NULL){
printf(“%c
”,bt->data);preorder(bt->lchild);preorder(bt->rchild);
} } void inorder(TNODE *bt)//中序遍历 {
if(bt!=NULL){
inorder(bt->lchild);printf(“%c
”,bt->data);inorder(bt->rchild);
} }
void postorder(TNODE *bt)//后序遍历 {
if(bt!=NULL){
postorder(bt->lchild);postorder(bt->rchild);printf(“%c
”,bt->data);
} } int main(){
TNODE *root;
root=creat();printf(“递归先序遍历是:”);
preorder(root);
printf(“n”);printf(“递归中序遍历是：”);inorder(root);printf(“n”);
} printf(“递归后序遍历是：”);postorder(root);printf(“n”);return 0;
四、程序运行结果：
五、程序设计指导：
1.创建二叉树的算法：首先对一般的二叉树，添加若干个虚结点使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，否则将新结点链接至它的双亲结点上。如此重复下去，直至遇到输入结束符（自定）为止。为了使新结点能够与双亲结点正确相连，并考虑到这种方法中先建立的结点其孩子结点也一定先建立的特点，可以设置一个指针类型的数组构成的队列来保存已输入结点的地址，并使队尾(rear)指向当前输入的结点，队头(front)指向这个结点的双亲结点的前一个位置。由于根结点的地址放在队列的第一个单元里，所以当rear为奇数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。若一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。
2.void preorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先读取，再进行进入下一个递归循环中。
3.void inorder(TNODE *bt)函数 ：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先左子树，再读取结点元素，再进行进入下一个递归循环中。
4.void postorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。
六、心得体会：
本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入地了解。在写程序的过程中，我重复地读课本上的知识，并且渐渐领悟到数据结构编程的方法。在编程中，虽然遇到了一些困难，但我并不气馁。当程序运行出来时，我感到了快乐。总之，通过自己地探索和努力，思维得到了锻炼，编程能力也有了较大地改善。
第四篇：第四次实验--二叉树遍历
一、二叉链表的声明.BinaryNode
public T data;
//数据域，存储数据元素
public BinaryNode
//链域，分别指向左、右孩子结点
//构造结点，参数分别指定元素和左、右孩子结点
publicBinaryNode(T data, BinaryNode
{ this.data = data;this.left = left;this.right = right;
}
public BinaryNode(T data)
//构造指定值的叶子结点
{ this(data, null, null);
} publicBinaryNode()
{ this(null, null, null);
}
//可声明以下方法 public String toString()
{ returnthis.data.toString();
}
public boolean equals(Object obj)
//比较两个结点值是否相等，覆盖Object
//类的equals(obj)方法
{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode
}
public booleanisLeaf()
//判断是否叶子结点
{ returnthis.left==null &&this.right==null;
} } 二、二叉树中的遍历方法的声明.BinaryTree
public BinaryNode
//根结点，结点结构为二叉链表
public BinaryTree()
//构造空二叉树
{ this.root=null;
}
public booleanisEmpty()
//判断二叉树是否空
{ returnthis.root==null;
}
//二叉树的先根、中根和后根次序遍历算法
public void preOrder()
//先根次序遍历二叉树
{ System.out.print(“先根次序遍历二叉树：
”);preOrder(root);//调用先根次序遍历二叉树的递归方法 System.out.println();
}
public void preOrder(BinaryNode
//先根次序遍历以p结点为根的子二叉
//递归方法
{ if(p!=null)
//若二叉树不空
{ System.out.print(p.data.toString()+“ ”);//访问当前结点
preOrder(p.left);
//按先根次序遍历当前结点的左子树，//递归调用 preOrder(p.right);
//按先根次序遍历当前结点的右子树
//递归调用
}
}
public String toString()
//返回先根次序遍历二叉树所有结点的描述字符串
{ returntoString(root);
}
private String toString(BinaryNode
//返回先根次序遍历以p为根的子树描述字
//符串，递归算法
{ if(p==null)return “";
return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//递归调用
}
public void inOrder()
//中根次序遍历二叉树
{ System.out.print(”中根次序遍历二叉树：
“);inOrder(root);System.out.println();
}
public void inOrder(BinaryNode
//中根次序遍历以p结点为根的子二叉
//递归方法
{ if(p!=null)
{ inOrder(p.left);
//中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+” “);inOrder(p.right);
//中根次序遍历右子树，递归调用
}
}
public void postOrder()
//后根次序遍历二叉树
{ System.out.print(”后根次序遍历二叉树：
“);postOrder(root);System.out.println();
}
public void postOrder(BinaryNode
//后根次序遍历以p结点为根的子二叉树，//递归方法
{ if(p!=null)
{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);
}
}
public BinaryTree(T[] prelist, T[] inlist)
//以先根和中根序列构造二叉树
{ this.root = create(prelist, inlist, 0, 0, prelist.length);
} //以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度.//返回所创建子树的根结点
privateBinaryNode
{ System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println();
if(n<=0)return null;
T elem=prelist[preStart];
//根结点值 BinaryNode
//创建叶子结点 inti=0;while(i //在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i); //创建左子树 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//创建右子树 return p; } private void print(T[] table, int start, int n) { for(inti=0;i } public BinaryTree(T[] prelist) //以标明空子树的先根序列构造二叉树 { this.root = create(prelist); } //以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 privateinti=0;privateBinaryNode { BinaryNode { T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String { p = new BinaryNode //创建叶子结点 p.left = create(prelist); //创建p的左子树 p.right = create(prelist); //创建p的右子树 } } return p; } } 三、运行程序 .BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树 public class BinaryTree_make { public static BinaryTree //构造给定的一棵二叉树 { BinaryTree BinaryNode } public static void main(String args[]) { BinaryTree //先根次序遍历二叉树 bitree.inOrder();//中根遍历 bitree.postOrder(); //后根遍历 String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根两种遍历 String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"}; //确定一颗二叉树 BinaryTree bitree1.preOrder();// 先根遍历 bitree1.inOrder();//中根遍历 bitree1.postOrder(); } } //后根遍历 四、运行结果 五、实验内容 1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历 六、附加实验内容 在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。 七、实验报告要求 1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。 2.心得体会不可为空（可写对此次实验的看法，亦可写自己近来学习数据结构的感受等等，内容不限） 目录 一 设计思想..........................................2 1递归遍历二叉树算法思想：.......................................2 2非递归遍历二叉树算法思想：.....................................2 二 算法流程图........................................4 三 源代码............................................4 四 运行结果.........................................16 五 遇到的问题及解决.................................16 1遇到的问题：..................................................16 2解决方法：....................................................16 六 心得体会.........................................17 一 设计思想 1递归遍历二叉树算法思想： （1）先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。 （2）中序遍历：首先判断根结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。 （3）后序遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。 2非递归遍历二叉树算法思想： （4）先序遍历：建立一个栈，当指针到达根结点时，打印根结点，并进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左 右指向子结点的指针都为空结束循环即完成了先序遍历 （5）中序遍历：建立一个栈，当指针到达根结点时，结点进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈，每次弹栈都读取结点，然后判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了中序遍历 （6）后序遍历：建立一个栈，并建立一个数组，数组伴随进栈出栈更改对应的值，数组里的数值代表进栈次数，1代表进栈1次，2代表进栈两次。当指针到达根结点时，进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点若没有或已经进栈两次则读取结点的值并继续弹栈，一直到有右结点且只进过一次栈为止，然后将其第二次进栈，并将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了后序遍历。二 算法流程图 开始T传入根结点T==Null？结点是否为空 No结束YesVisit（T）打印根结点的值T->child访问左子结点T->child访问右子结点 表1 递归先序流程图 开始T结束T==Null？ T->childVisit（T） 表2 递归中序遍历流程图 T->child5 开始T结束T==Null？ T->childT->child 表3 递归后序遍历流程图 Visit（T） 开始T，st传入树根指针，和栈指针a=T;b=T;aa！=Null有左子结点Yesvisit(a);IntoStack(st,a);a=a->lchild;NoOutStack(st,&b);Yes b=b->rchild;Yes St->top!=1栈不空No bvisit(b);IntoStack(st,b);a=b->lchild;b!=NULL有右子结点Yes No st->top!=1&&b==NULL栈不空且没有右子结点Yes OutStack(st,&b);b=b->rchild;st->top!=1&&(a!=NULL||b!=NULL)栈不空且有子节点No 结束No 表4 非递归先序遍历流程图 开始T，sta=T;b=T;aa！=NullNoOutStack(st,&b);visit(b);Yes b=b->rchild;YesIntoStack(st,a);a=a->lchild;St->top!=1Yes bb!=NULLYes No IntoStack(st,b);a=b->lchild;NoIntoStack(st,b);a=b->lchild;YesNob!=NULLst->top!=1&&b==NULLYes OutStack(st,&b);visit(b);b=b->rchild;No 结束表5 非递归后序遍历流程图 st->top!=1&&(a!=NULL||b!=NULL)No 开始T，sta=T;b=T;int i[max];int j=0;aa！=NullNoOutStack(st,&b);--j;a=b;b=b->rchild;YesIntoStack(st,a);i[j++]=1;a=a->lchild;Yes St->top!=1Yes bb!=NULLNoNo Yes IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild;visit(a);IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild;Yesvisit(a);a=NULL;b=NULL;Noi[j]!=2&&b!=NULLst->top!=1&&b==NULLYes OutStack(st,&b);--j;a=b;b=b->rchild;No 结束st->top!=1&&(a!=NULL||b!=NULL)No 表6 非递归后序遍历流程图 三 源代码 #include B s[max];}stack;//创建栈 void IntoStack(stack *st,B in){ if(st->top==max-1){printf(“wrong”);} st->s[(st->top)++]=in;}//进栈函数 void OutStack(stack *st,B *out){ if(st->top==0){printf(“wrong”);} *out=st->s[--(st->top)];}//出栈函数 void visit(B T){ if(T->data!='#'){printf(“%c ”,T->data);} }//访问结点的值 int creatBitree(B &T){ char data;scanf(“%c”,&data);if(data=='#'){T=NULL;} else{ T=(Bitreea*)malloc(sizeof(Bitreea)); T->data=data; creatBitree(T->lchild);creatBitree(T->rchild);}return(0);}//先序创建二叉树 //递归遍历二叉树 int pre(B T){ if(T!=NULL){visit(T);pre(T->lchild);pre(T->rchild);} }//先序遍历 int zhong(B T){ if(T!=NULL){ zhong(T->lchild);visit(T);zhong(T->rchild);} }//中序遍历 int hou(B T){ if(T!=NULL){ hou(T->lchild); hou(T->rchild);} visit(T);}//后序遍历 //非递归遍历 int fpre(B T, stack *st){B a,b;a=T;b=T; do{ if(a!=NULL){visit(a);IntoStack(st,a);a=a->lchild;} else {if(st->top!=1) {OutStack(st,&b);b=b->rchild; if(b!=NULL) { visit(b);IntoStack(st,b);a=b->lchild; } else { while(st->top!=1&&b==NULL){OutStack(st,&b);b=b->rchild; if(b!=NULL){ visit(b);IntoStack(st,b);a=b->lchild; } } } } } }while(st->top!=1&&(a!=NULL||b!=NULL));} //先序遍历 int fzhong(B T, stack *st){B a,b;a=T;b=T; do{ if(a!=NULL){IntoStack(st,a);a=a->lchild;} else {if(st->top!=1) { OutStack(st,&b);visit(b);b=b->rchild;if(b!=NULL) { IntoStack(st,b);a=b->lchild; } else { while(st->top!=1&&b==NULL){OutStack(st,&b);visit(b);b=b->rchild; if(b!=NULL){ IntoStack(st,b);a=b->lchild; } } } } } }while(st->top!=1&&(a!=NULL||b!=NULL));} //中序遍历 int fhou(B T, stack *st){B a,b;a=T;b=T;int i[max];int j=0; do{ if(a!=NULL){IntoStack(st,a);i[j++]=1;a=a->lchild;} else {if(st->top!=1) { OutStack(st,&b);--j;a=b;b=b->rchild;if(b!=NULL){ IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild; } else {visit(a);while(st->top!=1&&b==NULL){OutStack(st,&b);--j;a=b;b=b->rchild; if(i[j]!=2&&b!=NULL){IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1; a=b->lchild; }else{ visit(a);a=NULL;b=NULL; } } } } } }while(st->top!=1&&(a!=NULL||b!=NULL));} //后序遍历 int main(){ stack st;st.top=1;B ss;creatBitree(ss);printf(“递归:nn”);printf(“ 先序：”);pre(ss);printf(“nn”);printf(“ 中序：”);zhong(ss);printf(“nn”);printf(“ 后序：”);hou(ss);printf(“nn”);printf(“非递归:nn”);printf(“ 先序：”);fpre(ss,&st);printf(“nn”);printf(“ 中序：”);fzhong(ss,&st);printf(“nn”);printf(“ 后序：”);fhou(ss,&st);printf(“nn”);system(“pause”);}//主函数 四 运行结果 表7 运行结果 五 遇到的问题及解决 1遇到的问题： (1)在非递归遍历中遇到结点值两次进栈的问题，在弹栈过程中虽然弹出同一值但根据进栈的次数不同处理方式不同必须有一标示指出结点是否已进过两次栈。 (2)树结点的返回查找问题，由于二叉树总是由根节点指向子节点的所以查到左子节点就不能查找右节点了。 2解决方法： （1）创建了一个数组数组里的每一项存的值会根据结点的进栈出栈做出相应的改变在进行处理是添加对数组值得判断以保证结点不会第三次进栈。 （2）创建一个栈来保存根节点，当需要查询右节点是弹栈返回查找右节点。六 心得体会 课程设计期间，遇见一些问题，一个就是怎样后序非递归遍历二叉树，经过分析和斟酌，终于得到比较满意的程序，使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑，独立实践的机会，应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深，进一步培养我们的综合能力。灵活运用各种数据类型组成一个具有系统性的程序。在这之中，虽然每个人的思路不一样，但是拿一颗真诚热心去探讨问题就能更好的解决问题。我们应该更能了解我们自己，自己还是太嫩，需要我们学习的还有很多很多，成功是百分之九十九的汗水加上百分之一的灵感，所以我们的路还很长很长，或许是万里长城，或许还要翻山越岭，但是我们都应该永不放弃，不断提高，更好地运用课堂学习的知识。通过这次作业我学到了很多东西，将以前学过的C语言知识与现在的课堂知识进行结合应用。重要的是使我知道了自学知识和合作的重要性，提高了自己动手能力和沟通能力，学到了许多解决实际问题的宝贵经验．同时也挖掘出了我们潜在的能力，使我们对编程更有兴趣。我相信，只要努力、勤奋、坚持不懈，就没有什么做不到的事，不能还没开始就退缩，要勇于拼搏，敢于创新。总之，在通过又一次的真正动手之后，我在C语言设计方面获益匪浅，我会更加努力的学习编程方面的更多知识，提高自己的能力。然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较。 注：源代码可以优化，从流程图可以看出，自己修改了第五篇：二叉树遍历
鲁公网安备37028302000876号