数据结构上机实验6

《数据结构上机实验6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构上机实验（六）树和二叉树班级：学号：姓名：上机时间：地点：一、实验目的1.掌握二叉树的性质。2.掌握二叉树的基本运算和各种遍历算法的实现。二、实验内容1．实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能：（以P194图7.23所示的二叉树为例）（1）输出二叉树b；（2）输出H结点的左、右孩子结点值；（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的结点个数；（6）输出二叉树b的叶子结点个数。2．实现二叉树的先序、中序、后序遍历的递归和非递归算法，以及层次遍历的算法，并对P194图7.23所示

2、的二叉树b给出求解结果。三、实验过程1．了解常用函数所在的头文件stdlib.hstdlib头文件里包含了C语言的一些函数该文件包含了的C语言标准库函数的定义stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()

3、、srand()、exit()等等。具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。conio.hconio.h不是C标准库中的头文件。conio是ConsoleInput/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。&表示引用传递。在函数参数表中，出现带&这个的形参，表示引用传递。2．程序实现（以下代码仅起参考作用）（1）二叉树的各种运算#include#includ

4、e#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;//数据元素structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;voidCreateBTNode(BTNode*&b,char*str)//由str串创建二叉链{BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;//建立的二叉树初始时为空ch=str[

5、j];while(ch!='')//str未扫描完时循环{switch(ch){case'(':top++;St[top]=p;k=1;break;//为左结点case')':top--;break;case',':k=2;break;//为右结点default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)//p指向二叉树的根结点b=p;else//已建立二叉树根结点{switch(k){case1:St[top

6、]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode*FindNode(BTNode*b,ElemTypex)//返回data域为x的结点指针{BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b->rchild,x);}}BTNode*Lchi

7、ldNode(BTNode*p)//返回*p结点的左孩子结点指针{returnp->lchild;}BTNode*RchildNode(BTNode*p)//返回*p结点的右孩子结点指针{returnp->rchild;}intBTNodeDepth(BTNode*b)//求二叉树b的深度{intlchilddep,rchilddep;if(b==NULL)return(0);//空树的高度为0else{lchilddep=BTNodeDepth(b->lchild);//求左子树的高度为lchilddeprchilddep=BTN

8、odeDepth(b->rchild);//求右子树的高度为rchilddepreturn(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}voidDispBTNode(BTNod