第四次实验--二叉树遍历

第一篇：第四次实验--二叉树遍历

一、二叉链表的声明.BinaryNode public class BinaryNode //二叉树的二叉链表结点类，泛型T指//定结点的元素类型 {

public T data;

//数据域，存储数据元素

public BinaryNode left, right;

//链域，分别指向左、右孩子结点

//构造结点，参数分别指定元素和左、右孩子结点

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ 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)obj).data);

}

public booleanisLeaf()

//判断是否叶子结点

{ returnthis.left==null &&this.right==null;

} } 二、二叉树中的遍历方法的声明.BinaryTree public class BinaryTree {

public BinaryNode root;

//根结点，结点结构为二叉链表

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)

//先根次序遍历以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)

//返回先根次序遍历以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)

//中根次序遍历以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)

//后根次序遍历以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 create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ 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 p=new BinaryNode(elem);

//创建叶子结点 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 create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String

{

p = new BinaryNode(elem);

//创建叶子结点 p.left = create(prelist);

//创建p的左子树 p.right = create(prelist);

//创建p的右子树

}

} return p;

}

}

三、运行程序

.BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树

public class BinaryTree_make {

public static BinaryTree make()

//构造给定的一棵二叉树

{ BinaryTreebitree=new BinaryTree();//创建空二叉树

BinaryNodechild_f, child_d, child_b, child_c;//创建4个二叉链表域 child_d = new BinaryNode(”D“, null, new BinaryNode(”G“));child_b = new BinaryNode(”B“, child_d, null);child_f = new BinaryNode(”F“, new BinaryNode(”H“), null);child_c = new BinaryNode(”C“, new BinaryNode(”E“), child_f);bitree.root = new BinaryNode(”小唐“, child_b, child_c);//创建根结点 returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍历二叉树 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 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍历

bitree1.inOrder();//中根遍历

bitree1.postOrder();

} }

//后根遍历

四、运行结果

五、实验内容

1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历

六、附加实验内容

在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。

七、实验报告要求

1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。

2.心得体会不可为空（可写对此次实验的看法，亦可写自己近来学习数据结构的感受等等，内容不限）

第二篇：二叉树遍历课程设计】

数据结构程序设计报告

学院： 班级： 学号：

姓名：

实验名称：二叉树的建立与遍历

一、实验目的：

1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法；

3.掌握二叉树的先序、中序、后序的递归实现方法。

二、实验内容和要求：

创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。

三、叉树的建立与遍历代码如下：

#include #include struct tnode//结点结构体 {

};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)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。

六、心得体会：

本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入地了解。在写程序的过程中，我重复地读课本上的知识，并且渐渐领悟到数据结构编程的方法。在编程中，虽然遇到了一些困难，但我并不气馁。当程序运行出来时，我感到了快乐。总之，通过自己地探索和努力，思维得到了锻炼，编程能力也有了较大地改善。

第三篇：二叉树的遍历学习心得

二叉树的非递归遍历学习心得

对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。

鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。

typedef struct BitNode { char data;

树的结点的数据域（以字符型数据为

树的结点的结构

例）

struct BitNode *lchild,*rchild;

树的子树指针

}BitNode,*BitTree;

typedef struct node { BitNode stack;

栈的数据域类型为树的 结点

栈的结点结构

struct node *next;}LinkStack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。BitTree Creat_BitTree(){

BitTree bt;

树的根结点 char x;scanf(“%c”,&x);

树的建立的子函数类型为树的指针类型

} if(x=='#')bt=NULL;else {

} return bt;

如果输入为’#’，则返回空结点

bt=(BitTree)malloc(sizeof(BitNode));若输入有效，则申请结点空间 bt->data=x;

装填结点 插入左子树 插入右子树 bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();

建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为

那么输入应该为ABD##EG###。

接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。int Init_Stack(LinkStack **s){

}

int Push_Stack(LinkStack *s,BitNode *x)

*s=(LinkStack*)malloc(sizeof(LinkStack));(*s)->next=NULL;return 1;{

}

int Pop_Stack(LinkStack *s,BitNode *e){

return 0;}

}

int Empty_Stack(LinkStack *s){

}

if(s->next==NULL)return 1;return 0;LinkStack *p;

if(Empty_Stack(s)){ printf(“Stack is NULLn”);p=s->next;s->next=p->next;*e=p->stack;free(p);return 1;LinkStack *p;

p=(LinkStack*)malloc(sizeof(LinkStack));p->stack=*x;p->next=s->next;s->next=p;return 1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。void Pre_Order(BitTree T){

} 以下是主函数。int main(){

BitTree T;

printf(“nt********************欢迎来到二叉LinkStack *s;BitTree p;p=T;

Init_Stack(&s);Push_Stack(s,p);while(!Empty_Stack(s)){

Pop_Stack(s,p);

printf(”t[%c]“,p->data);

if(p->rchild)Push_Stack(s,p->rchild);if(p->lchild)Push_Stack(s,p->lchild);} 树世界********************n”);

printf(“nt请输入二叉树结点，”#“为空树nt”);T=Creat_BitTree();printf(“n”);

printf(“t先序遍历二叉树如下：”);printf(“n”);

}

Pre_Order(T);printf(“nt”);getch();以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。void In_Order(BitTree T){

}

LinkStack *s;BitTree p,q;

q=(BitTree)malloc(sizeof(BitNode));p=T;

Init_Stack(&s);

while(p ||!Empty_Stack(s)){ if(p){

} else {

} }

Pop_Stack(s,q);

printf(“t[%c]”,q->data);p=q->rchild;Push_Stack(s,p);p=p->lchild;二叉树的遍历中要数后序遍历最为复杂，它的栈的构造与前面两种遍历方法有所不同，在栈里加了一个标记元素rvisited用来标记其结点的右子树是否被访问过，由此来达到最后才访问根结点的效果。由于程序比较复杂，下面为大家一步步分析。

typedef struct node {

}LinkStack;int Push_Stack(LinkStack *s,BitNode *x){

} void Post_Order(BitTree T){

BitTree p,q;LinkStack *s,*top;Init_Stack(&s);p=T;

q=(BitTree)malloc(sizeof(BitNode));while(p)

从左子树插入到底 {

LinkStack *p;

p=(LinkStack *)malloc(sizeof(LinkStack));p->stack=*x;p->rvisited=0;p->next=s->next;s->next=p;return 1;

插入栈的时候先设为右子树未被访问

int rvisited;BitNode stack;struct node *next;

标记元素，记录右子树是否已被访问

}

Push_Stack(s,p);p=p->lchild;

while(!Empty_Stack(s)){

top=s->next;

取栈顶元素

if(!top->stack.rchild || top->rvisited)若栈顶元素的右子树不存在或者被访问过，访问栈顶元素同时出栈

} else

若栈顶元素的右子树存

{

Pop_Stack(s,q);

printf(“t[%c]”,q->data);在而且未被访问过，先将其rvisited值设为1再向右检测右子树

} 二叉树的几种遍历方法就介绍到这里，以上程序均在ＶＣ++6.0编译环境下运行通过，值得注意的是，三种遍历方法不能放在同一个程序中使用，因为树的遍历过程伴随着销毁，遍历一次以后下一次的遍历就变得毫无意义。由于本人水平有限,难免有纰漏差错之处,请谅解.} } } {

top->rvisited=1;p=top->stack.rchild;while(p){

Push_Stack(s,p);p=p->lchild;

从根结点的左子树插入栈到底 参考文献

(稻草人)[ 1 ] 徐孝凯.数据结构简明教程[M ].北京: 清华大学出版社, 1995: 71291.[ 2 ] 严蔚敏,吴伟民.数据结构[M ].北京: 清华大学出版社, 2000: 962106.[ 3 ] 耿国华.数据结构—C语言描述[M ].西安: 西安电子科技大学 出版社, 2006: 1012104.[ ４]崔进平,郭小春,王霞.数据结构(Ｃ语言版)[M ].北京:清华大学出版社,2011: 245868.(稻草人)

第四篇：数据结构-二叉树的遍历实验报告

实验报告

课程名：数据结构（C语言版）实验名：二叉树的遍历 姓名：

班级：

学号：

时间：2014.11.03

一 实验目的与要求

1.掌握二叉树的存储方法 2.掌握二叉树的三种遍历方法

3.实现二叉树的三种遍历方法中的一种 二 实验内容

• 接受用户输入一株二叉树

• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序 三 实验结果与分析

//*********************************************************** //头文件

#include #include //*********************************************************** //宏定义

#define OK 1 #define ERROR 0 #define OVERFLOW 0

//***********************************************************

typedef struct BiTNode { //二叉树二叉链表存储结构 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树 //构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} }

//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} }

//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树

printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}

图1:二叉树的遍历运行结果

第五篇：数据结构实验报告——中序遍历二叉树

班级：380911班

学号：57000211 姓名：徐敏

实验报告

一，实验目的：

·掌握二叉树的链式存储结构； ·掌握构造二叉树的方法；

·加深对二叉树的中序遍历的理解； 二，实验方法：

·用递归调用算法中序遍历二叉树。三，实验步骤：

·通过链式存储建立一颗二叉树。

·设计一个算法实现中序遍历二叉树。四，具体实验步骤：

#include #include #define LEFT 0 #define RIGHT 1 #define TRUE 1 #define FALSE 0

typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE;

void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p);

void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf(“Input the data:”);ConstructBTree(p);PrintBTree(p,0);printf(“Now InorderTraverse:”);InorderTraverse(p);printf(“nPress any key to continue...”);getchar();}

void PrintBTree(PBTNODE p,int depth){

班级：380911班

学号：57000211 姓名：徐敏

int i;if(p==NULL){

return;}else{ for(i=0;i

printf(“--”);} printf(“>”);

printf(“%cn”,p->c);

PrintBTree(p->lchild,depth+1);

PrintBTree(p->rchild,depth+1);} }

void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){

scanf(“%c”,&c);

if(c=='n'){

//printf(“EOFn”);

return;

} // printf(“%dn”,c);

switch(c){

case '|':

break;

case')':

return;

case',':

side=RIGHT;

break;

case'(':

if(side==LEFT){

if(p->lchild==NULL){

p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));

}

ConstructBTree(p->lchild);

}else{

if(p->rchild==NULL){

p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));

}

班级：380911班

学号：57000211 姓名：徐敏

ConstructBTree(p->rchild);

}

break;

default:

if(side==LEFT){

p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));

p->lchild->c=c;

}else{

p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));

p->rchild->c=c;

}

} } }

void InorderTraverse(PBTNODE p){ if(p==NULL){

return;}else{

InorderTraverse(p->lchild);

printf(“[%c] ”,p->c);

InorderTraverse(p->rchild);} return;} 五，实验过程：

·输出：Input the date;

·输入：1(2(3,4),5(6,7));

·输出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上机实验体会：

·体会到熟练掌握各种程序算法的重要性；

·通过上机练习，充分理解了链式建立二叉树的算法；

·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。