二叉树实验报告
实 验 报 告
课程名称 算法与数据结构
专 业
学号
姓名 实验日期
算法与数据结构实验报告
一、实验目的
1.了解二叉树的结构特点及有关概念,掌握二叉树建立的基本算法
2.了解二叉树遍历的概念,掌握遍历二叉的算法
3.进一步掌握树的结构及非线性特点,递归特点和动态性。
二、实验内容
二叉树的实现和运算
三、实验要求
1.用C++/C完成算法设计和程序设计并上机调试通过。
2.撰写实验报告,提供实验结果和数据。
3.分析算法,并简要给出算法设计小结和心得。
四、算法步骤
用户以三元组形式输入二叉树的结点元素及其位置关系,建立二叉树,并打印输出该二叉树。
用户输入选择结点,程序调用BiTNode* Find Node(char tag, BiTNode* node)函数,返回子树的根结点,然后调用BiTreeDepth(BiTree T)函数,求出子树的深度,并输出该值。
3.用户可以选择是否继续执行程序,若继续,则输入1,否则输入0,结束程序。
五、主程序代码:
int main(void)
{
BiTree T;
TElemType e1;
char node; // node为用户选择输入的结点//
int b,choose; // b为以选定结点为子树的深度,choose为实现多次选择输入的标志//
BiTNode* a; // a为选定结点为子树的根结点//
choose=1; // 多次选择的标志,当choose为1时运行程序,为0时结束程序// InitBiTree(T);
printf("构造空二叉树后,树空否?%d(1:是0:否), 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1 = Root(T);
if(e1 != Nil)
#ifdef CHAR
printf("二叉树的根为: %c\n",e1);
#endif
#ifdef INT
printf("二叉树的根为: %d\n",e1);
#endif
else
printf("树空,无根\n"); //三元组构建二叉树string x;
printf("输入格式说明:三元组(P,C,L/R)方式输入,P:parent, C: child, L/R: C is P's left child / right child, 输入end 结束输入\n");
printf("eg. the root: input ^AL, its left child is B: input ABL, its right child is C: input ACR!\n");
GetUserWord(x);
while(x!="end")
{
AddNode(T, x[0], x[1], x[2]);
GetUserWord(x);
} //输出树 PrintTreeLevel( T );
//以三元组形式输入任意二叉树(以大写字母表示结点),求以任意一选定结点为子树的深度。
while(choose) // 实现多次选择输入//
{
printf("Please select a node: ");
fflush(stdin);
scanf("%c",&node);
a= FindNode(node,T); // a为生成子树的根//
b=BiTreeDepth(a);
printf("the Depth of BiTree is : %d\n",b);
printf("\nif you want to cointue choose 1,else choose 0: ");
fflush(stdin);
scanf("%d",&choose);
}
DestroyBiTree( T );
return EXIT_SUCCESS;
}
六、心得体会
树是常用的数据结构。通过实验加深了我对树的遍历的认识,巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。
通过实验,有如下几点收获和体会:
1、通过实验还提高了一点改错能力,对于一些常见问题加深了印象。
2、编程需要有耐心,尤其实在单步调试的时候,更是马虎不得,有时候关键就是那么一步,错过了就得从头来过了。编程也需要勇气,要勇于发现自己的错误,
也要勇于推翻自己之前的思路,要坚信“没有最好,只有更好”。编程,最好是一鼓作气,得天天“摸摸”它,时时想着它,要是过一阵再去碰它那就得先去读懂自己的程序了,一切的一切几乎都得从头开始。编程需要细心,有时一个不注意小错误就能引出大问题。编程也需要规范,不仅为了他人能看得懂程序,也为了方便自己以后程序的更改与进一步的完善。
3、程序由算法和数据结构组成,一个好的程序不仅算法重要,数据结构的设计也很重要。
4.以前在学C语言时总觉得函数的递归调用是一样很复杂的算法,经常会理解不了而导致编程的错误。但在这次实验中,二叉树的先序、中序与后序的输出都用了递归算法。而且用起来并不复杂,这使我更进一步学习理解了函数的递归调用并得到灵活的运用。 经过本次实验基本上解决的一些所遇到的问题,我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的,相信在越来越多的尝试之后,自己会不断进步。