下载文档第一篇：二叉树的建立及遍历
数据结构实验报告
实验三名称：二叉树
姓名：高宁鑫 学号：201417525 班级：2014175 专业：数学与应用数学
指导老师：黄春艳
一、实验目的
(1)掌握二叉树的定义和存储表示，学会建一棵二叉树的方法(2)掌握二叉树的遍历（前序，中序，后序）采用递归和非递归方法
二、实验要求(1)建二叉树(2)遍历
三、实验原理
(1)利用递归原理建立一棵二叉链表的二叉树：为了让每个结点确认是否有左右孩子，对原二叉树进行扩展，将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值“.”获得一个扩展二叉树，通过遍历序列确定一棵二叉树。
(2)进行二叉树的遍历：指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
四、实验环境
Windows XP系统, Vc6软件
五、算法实现及步骤 实现的主要算法：
(1)首先定义二叉树的存储形式，这里使用了二叉链表 typedef struct Node //创建结点类型结构体 { DataType data;struct Node *LChild;struct Node *RChild;}BitNode,*BitTree;(2)建立一个二叉树
void CreatBiTree(BitTree *bt)//用扩展前序遍历序列创建二叉树如果是当前树根置为空否则申请一个新节点// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} }(3)建立递归方法二叉树的前序、中序、后序遍历
void PreOrder(BitTree root)//前序遍历二叉树的递归算法 { if(root!=NULL){ visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } void InOrder(BitTree root)//中序遍历二叉树的递归算法 { if(root!=NULL){ InOrder(root->LChild);visit(root->data);InOrder(root->RChild);} } void PostOrder(BitTree root)//后序遍历求二叉树的递归算法 { if(root!=NULL){ PostOrder(root->LChild);PostOrder(root->RChild);visit(root->data);} }(4)建立非递归方法二叉树的前序、中序、后序遍历 void preOrder2(BinTree *root)//非递归前序遍历 { stack data<<“";s.push(p);p=p->lchild;}if(!s.empty()){ p=s.top();s.pop();p=p->rchild； }}} void inOrder2(BinTree *root)//非递归中序遍历 { stack data<<”“;s.pop();p=p->rchild;}}} void postOrder2(BinTree *root)//非递归后序遍历 { stack 六、实验结果 递归方法的遍历结果： 非递归方法的遍历结果： 七、心得体会 通过这次实验，让我对树有了更深入的认识，不仅再次熟悉了树以及二叉树的存储结构：顺序存储结构，链式存储结构；而且更加清楚二叉树的遍历原理以及三种遍历方法。在这次实验中，多次应用到了递归，这样让我进一步掌握了递归的算法思想。 然而在输入二叉树中的元素时，只能按设定的前序遍历的次序输入合法的结点的值，不然程序无法进行。总的来说，通过这次实验，让我对树有了更多的认识，明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。 主程序源代码： 递归方法： #include 非递归方法 #include data<<”“;s.push(p);p=p->lchild;} if(!s.empty()){ p=s.top();s.pop();p=p->rchild;} }} void inOrder2(BinTree *root)//非递归中序遍历 { stack data<<”“;s.pop();p=p->rchild;} } } void postOrder2(BinTree *root)//非递归后序遍历 { stack 武汉理工大学《数据结构》课程设计说明书 题 目: 二叉树的建立和遍历的演示 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1、系统应具备的功能： （1）选择树的存储结构,建立二叉树;（2）用递归算法和非递归算法实现二叉树的遍历（3）二叉树遍历的演示 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；（4）结束语；（5）参考文献。 时间安排： 202_年7月2日－7日（第18周） 7月2日 查阅资料 7月3日 系统设计，数据结构设计，算法设计 7月4日-5日 编程并上机调试 7月6日 撰写报告 7月7日 验收程序，提交设计报告书。 指导教师签名： 202_年7月2日 系主任（或责任教师）签名： 202_年7月2日 二叉树的建立及遍历的实现 武汉理工大学《数据结构》课程设计说明书 摘要：该程序主要部分有：基于静态二叉链的二叉树的建立及其遍历的实现，包括建立二叉树，先序.中序.后序遍历二叉树，以及根据遍历数序计算二叉树中 的结点数和叶子结点数等。 关键字：二叉树，建立，遍历，先序，中序，后序，结点数 0.引言 二叉树是一种树型结构，其特点是每个结点至多有两棵子树（有左右之分，次序不能颠倒）其多应用在查找.排序.存储二叉链等中。对那些都有很大帮助，二叉树的建立等只是基础，是对其的基本理解。 1.需求分析 二叉树的建立.遍历和结点数的计算等等。 2.数据结构设计 #include typedef struct TreeNode{ char data;/*树中结点的数据是一个字符*/ struct TreeNode *lchild; struct TreeNode *rchild;}TREENODE;int NodeNum = 0;/*统计数的结点数*/ int LeafNum = 0;/*统计数的叶子结点数*/ char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '};int inc = 0;3.算法设计 3.1二叉树建立 /*建立一颗二叉树*/ int CreateBiTree(TREENODE **T)/*按先序次序输入二叉树中结点的值,以空字符表示空树*/ { char i;if(ch[inc++]==' ') *T = NULL;else 武汉理工大学《数据结构》课程设计说明书 { printf(“%cn”,ch[inc-1]);if(!(*T =(TREENODE *)malloc(sizeof(TREENODE)))) return-1; (*T)->data = ch[inc-1]; printf(“%cn”,(*T)->data); CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild));} return 1;} 3.2先序遍历 /*先序遍历二叉树*/ int PreOderTraverse(TREENODE *T){ if(T){ printf(“%c ”,T->data); PreOderTraverse(T->lchild); PreOderTraverse(T->rchild);} return 1;} 3.3中序遍历 /* 中序遍历二叉树*/ int InOderTraverse(TREENODE *T){ if(T){ InOderTraverse(T->lchild); printf(“%c ”,T->data); InOderTraverse(T->rchild);} return 1;} 3.4后序遍历 /* 后序遍历二叉树*/ int BackOderTraverse(TREENODE *T) 武汉理工大学《数据结构》课程设计说明书 { if(T){ BackOderTraverse(T->lchild); BackOderTraverse(T->rchild); printf(“%c ”,T->data);} return 1;} 3.5计算结点树 /*利用先序遍历来计算树中的结点数*/ void CountNodeNum(TREENODE *T){ if(T){ NodeNum ++; CountNodeNum(T->lchild); CountNodeNum(T->rchild);} } 3.6计算叶子结点数 /*利用先序遍历计算叶子节点数*/ void CountLeafNum(TREENODE *T){ if(T){ if((!(T->lchild))&&(!(T->rchild))) LeafNum ++; CountLeafNum(T->lchild); CountLeafNum(T->rchild);} } 3.7界面的设计 int main(){ TREENODE *T;int i;CreateBiTree(&T); 武汉理工大学《数据结构》课程设计说明书 do { clrscr(); puts(“**************************************************”); puts(“* you can choose: *”); puts(“* 1: Traverse the Binary tree by pre order *”); puts(“* 2: Traverse the Binary tree by mid order *”); puts(“* 3: Traverse the Binary tree by back order *”); puts(“* 4: Count the node num of the Binary tree *”); puts(“* 5: Count the leaf node num of the Binary tree*”); puts(“**************************************************”); puts(“please input your choice:”); scanf(“%d”,&i); switch(i) { case 1: printf(“The preoder is:n”); PreOderTraverse(T); printf(“n”); break; case 2: printf(“The midoder is:n”); InOderTraverse(T); printf(“n”); break; case 3: printf(“The backoder is:n”); BackOderTraverse(T); printf(“n”); break; case 4: CountNodeNum(T); printf(“The nodenum of the tree is:%dn”,NodeNum); break; case 5: CountLeafNum(T); printf(“The leafnum of the tree is:%dn”,LeafNum); break; } printf(“please input any char to go onn”); getch();}while((i>=1)&&(i<6)); getch(); 武汉理工大学《数据结构》课程设计说明书 } return 1;4.程序运行结果 主界面： 先序遍历： 中序遍历： 武汉理工大学《数据结构》课程设计说明书 后序遍历： 计算树的结点数： 武汉理工大学《数据结构》课程设计说明书 计算叶子结点数： 5.相关原理 二叉树的遍历 由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。 遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。 武汉理工大学《数据结构》课程设计说明书 由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”: ①访问根根点; ②遍历左子树(即依次访问左子树上的全部结点);③遍历右子树(即依次访问右子树上的全部结点)。 因为左、右子树都是二叉树(可以是空二叉树)，对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下: 先根遍历 若需遍历的二叉树为空，执行空操作;否则，依次执行下列操作: ①访问根结点; ②先根遍历左子树; ③先根遍历右子树。 中根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作: ①中根遍历左子树;②访问根结点;③中根遍右子树。 后根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作: ①后根遍历左子树。②后根遍历右子树。③访问根结点。 显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先(最后、在中间)执行此子任务，则为先根(后根、中根)遍历。 按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。 树与二叉树之间的转换 一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是: ①加线:在兄弟结点直接加一虚线; 武汉理工大学《数据结构》课程设计说明书 ②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线; ③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。 二叉树还原为一般树的步骤是: ①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;②抹线:抹去原二叉树中所有结点与其右孩子的连线;③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。二叉树通常有两类存储结构，顺序存储结构和链式存储结构。 6.设计心得体会 通过编写这个比较基础的二叉树的建立和遍历的实现的程序，基本掌握了以前学习的一些C语言的知识。很多知识点都是通过二次看书才理解了，现在可以编写一些简单的C语言程序。借这个设计时间又掌握了一些C语言编程的用法，对以后编写大一点的程序有很大的帮助。 编写的时候虽然刚开始有些困难，但通过看书.询问同学和借由网络，都一点一点的解决了。虽然编程有点枯燥，但是通过不断努力编写出来后心里还是非常兴奋的。就像学习英语，一步一步的积累。在以后的学习中，希望通过不断的编写争取写出一些功能较为庞大的程序。 7.结束语 本文主要内容是二叉树的建立及其遍历的实现，计算结点数等等。是通过C语言编写的程序。 参考文献 [1] 严蔚敏，吴伟名。《数据结构》，清华大学出版社 [2] 张颖江，胡燕。《C语言程序设计》，科学出版社 [3] 潭浩强。《C程序设计》，清华大学出版 # 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.心得体会不可为空（可写对此次实验的看法，亦可写自己近来学习数据结构的感受等等，内容不限）第二篇：二叉树的建立和遍历的演示
第三篇：二叉树的遍历
第四篇：二叉树遍历课程设计】
第五篇：第四次实验--二叉树遍历
