数据结构上机实验6.doc

数据结构上机实验（六） 树和二叉树班级： 学号： 姓名：上机时间： 地点：一、实验目的1. 掌握二叉树的性质。2. 掌握二叉树的基本运算和各种遍历算法的实现。二、实验内容1实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能：（以P194图7.23所示的二叉树为例）（1）输出二叉树b；（2）输出H结点的左、右孩子结点值；（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的结点个数；（6）输出二叉树b的叶子结点个数。2实现二叉树的先序、中序、后序遍历的递归和非递归算法，以及层次遍历的算法，并对P194图7.23所示的二叉树b给出求解结果。三、实验过程1了解常用函数所在的头文件stdlib.h stdlib 头文件里包含了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()、 srand()、exit()等等。 具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。 conio.h conio.h不是C标准库中的头文件。 conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。&表示引用传递。在函数参数表中，出现带&这个的形参，表示引用传递。2程序实现（以下代码仅起参考作用）（1）二叉树的各种运算#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串创建二叉链BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while (ch!=0)/str未扫描完时循环 switch(ch) case (:top+;Sttop=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) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)/返回data域为x的结点指针BTNode *p;if (b=NULL) return NULL;else if (b-data=x) return b;elsep=FindNode(b-lchild,x);if (p!=NULL) return p;else return FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p)/返回*p结点的左孩子结点指针 return p-lchild;BTNode *RchildNode(BTNode *p)/返回*p结点的右孩子结点指针 return p-rchild;int BTNodeDepth(BTNode *b)/求二叉树b的深度 int lchilddep,rchilddep; if (b=NULL) return(0); /空树的高度为0 else lchilddep=BTNodeDepth(b-lchild);/求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子树的高度为rchilddepreturn (lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)/以括号表示法输出二叉树if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();int BTWidth(BTNode *b) /求二叉树b的宽度struct int lno;/结点的层次编号BTNode *p;/结点指针 QuMaxSize;/定义顺序非循环队列int front,rear;/定义队首和队尾指针int lnum,max,i,n;front=rear=0;/置队列为空队 if (b!=NULL) rear+;Qurear.p=b;/根结点指针入队Qurear.lno=1;/根结点的层次编号为1while (rear!=front)/队列不为空front+;b=Qufront.p;/队头出队lnum=Qufront.lno;if (b-lchild!=NULL)/左孩子入队rear+;Qurear.p=b-lchild;Qurear.lno=lnum+1;if (b-rchild!=NULL)/右孩子入队rear+;Qurear.p=b-rchild;Qurear.lno=lnum+1;max=0;lnum=1;i=1;while (i=rear)n=0;while (imax) max=n;return max;elsereturn 0;int Nodes(BTNode *b)/求二叉树b的结点个数int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=Nodes(b-lchild); num2=Nodes(b-rchild); return (num1+num2+1);int LeafNodes(BTNode *b)/求二叉树b的叶子结点个数int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafNodes(b-lchild); num2=LeafNodes(b-rchild); return (num1+num2);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(n);printf(1)输出二叉树:);DispBTNode(b);printf(n);printf(2)H结点:);p=FindNode(b,H);if (p!=NULL)lp=LchildNode(p);if (lp!=NULL) printf(左孩子为%c ,lp-data);elseprintf(无左孩子 );rp=RchildNode(p);if (rp!=NULL) printf(右孩子为%c,rp-data);elseprintf(无右孩子 );printf(n);printf(3)二叉树b的深度:%dn,BTNodeDepth(b);printf(4)二叉树b的宽度:%dn,BTWidth(b);printf(5)二叉树b的结点个数:%dn,Nodes(b);printf(6)二叉树b的叶子结点个数:%dn,LeafNodes(b);printf(n);（2）二叉树的先序、中序、后序遍历的递归和非递归算法，以及层次遍历的算法#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;extern void CreateBTNode(BTNode *&b,char *str);extern void DispBTNode(BTNode *b);void PreOrder(BTNode *b) /先序遍历的递归算法if (b!=NULL) printf(%c ,b-data); /访问根结点PreOrder(b-lchild);/递归访问左子树PreOrder(b-rchild);/递归访问右子树void PreOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+;/根结点入栈 Sttop=b; while (top-1)/栈不为空时循环 p=Sttop;/退栈并访问该结点 top-; printf(%c ,p-data); if (p-rchild!=NULL)/右孩子入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL)/左孩子入栈 top+; Sttop=p-lchild;printf(n);void InOrder(BTNode *b) /中序遍历的递归算法if (b!=NULL) InOrder(b-lchild);/递归访问左子树printf(%c ,b-data);/访问根结点InOrder(b-rchild);/递归访问右子树void InOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top-1 | p!=NULL)while (p!=NULL)top+;Sttop=p;p=p-lchild;if (top-1)p=Sttop;top-;printf(%c ,p-data);p=p-rchild;printf(n);void PostOrder(BTNode *b) /后序遍历的递归算法if (b!=NULL) PostOrder(b-lchild); /递归访问左子树PostOrder(b-rchild); /递归访问右子树printf(%c ,b-data);/访问根结点void PostOrder1(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;/栈指针置初值if (b!=NULL)dowhile (b!=NULL)/将t的所有左结点入栈top+;Sttop=b;b=b-lchild;p=NULL;/p指向当前结点的前一个已访问的结点flag=1;while (top!=-1 & flag)b=Sttop;/取出当前的栈顶元素if (b-rchild=p)/右子树不存在或已被访问,访问之printf(%c ,b-data);/访问*b结点top-;p=b;/p指向则被访问的结点elseb=b-rchild;/t指向右子树flag=0; while (top!=-1);printf(n); void TravLevel(BTNode *b)BTNode *QuMaxSize;/定义循环队列int front,rear;/定义队首和队尾指针front=rear=0;/置队列为空队列 if (b!=NULL) printf(%c ,b-data); rear+;/结点指针进入队列Qurear=b; while (rear!=front)/队列不为空 front=(front+1)%MaxSize;b=Qufront; /队头出队列if (b-lchild!=NULL)/输出左孩子,并入队列printf(%c ,b-lchild-data);rear=(rear+1)%MaxSize;Qurear=b-lchild;if (b-rchild!=NULL)/输出右孩子,并入队列printf(%c ,b-rchild-data);rear=(rear+1)%MaxSize;Qurear=b-rchild; printf(n);void main()BTNode *b;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf( 二叉树b:);DispBTNode(b);printf(nn);printf( 层次遍历序列:);TravLevel(b);printf(n);printf( 先序遍历序列:n);print