二叉树基本操作实验报告

1、实验三二叉树的基本操作学院:物理与电子学院班级:电信1105班姓名:刘岩学号:1404110729一、实验目的1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1台windows环境的pc机，装有visual c+ 6.0。三、实验内容1、问题描述现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：1 创建二叉树createbtnode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。2 输出二叉树dispbtnode(*b)：以括号表示法输出

2、一棵二叉树。3 查找结点findnode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。4 求高度btnodedepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。5 求二叉树的结点个数nodescount(btnode *b)6 先序遍历的递归算法：void preorder(btnode *b) 7 中序遍历的递归算法：void inorder(btnode *b) 8 后序遍历递归算法：void postorder(btnode *b) 9 层次遍历算法void levelorder(btnode

3、*b)2、基本要求实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到h节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序abdcehjklmnfgi3、程序编写上图转化为二叉树括号表示法为a(b(d,e(h(j,k(l,m(,n),c(f,g(,i)程序:#include #include #define maxsize 100typedef char elemtype;typedef struct nodeelemtype data;/*数据元素*/struct node *lchild;/*指向左孩子*/struct node *rchild;/*

4、指向右孩子*/ btnode;void createbtnode(btnode *&b,char *str);/创建btnode *findnode(btnode *b,elemtype x);/查找节点int btnodeheight(btnode *b);/求高度void dispbtnode(btnode *b);/输出int nodescount(btnode *b);/二叉树的结点个数void preorder(btnode *b);/先序遍历递归void inorder(btnode *b);/中序遍历递归void postorder(btnode *b);/后序遍历递归void

5、levelorder(btnode *b);/层次遍历/创建void createbtnode(btnode *&b,char *str)btnode *stmaxsize,*p=null;int top=-1,k,j=0;char ch;b=null;ch=strj;while(ch!=0)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(

6、b=null)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;/输出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();/查找节点btnode *findnode(btnode *

7、b,elemtype x)btnode *p;if(b=null)return b;else if(b-data=x)return b;elsep=findnode(b-lchild,x);if(p!=null)return p;elsereturn findnode(b-rchild,x); /求高度 int btnodeheight(btnode *b) int lchildh,rchildh; if(b=null) return (0); else lchildh=btnodeheight(b-lchild); rchildh=btnodeheight(b-rchild); return

8、(lchildhrchildh)?(lchildh+1):(rchildh+1); /二叉树的结点个数 int nodescount(btnode *b)if(b=null)return 0;elsereturn nodescount(b-lchild)+nodescount(b-rchild)+1; /先序遍历递归void preorder(btnode *b)if(b!=null)printf(%c,b-data);preorder(b-lchild);preorder(b-rchild);/中序遍历递归void inorder(btnode *b)if(b!=null)inorder(b

9、-lchild);printf(%c,b-data);inorder(b-rchild);/后序遍历递归void postorder(btnode *b)if(b!=null)postorder(b-lchild);postorder(b-rchild);printf(%c,b-data);/层次遍历void levelorder(btnode *b)btnode *p;btnode *qumaxsize;int front,rear;front=rear=-1;rear+;qurear=b;while(front!=rear)front=(front+1)%maxsize;p=qufront

10、;printf(%c,p-data);if(p-lchild!=null)rear=(rear+1)%maxsize;qurear=p-lchild;if(p-rchild!=null)rear=(rear+1)%maxsize;qurear=p-rchild;void main()btnode *b,*p,*lp,*rp;char str=a(b(d,e(h(j,k(l,m(,n),c(f,g(,i);/根据树形图改写成的/二叉树括号表示法的字符串*str/char str100;scanf(%s,&str);/自行输入括号表示的二叉树createbtnode(b,str); /创建树bpr

11、intf(n);printf(输出二叉树:);/输出二叉树bdispbtnode(b);printf(n);printf(h结点:);/找到h节点，输出其左右孩子值p=findnode(b,h);printf(n);if (p!=null) printf(左孩子节点的值);printf(%c,p-lchild-data);printf(n);printf(右孩子节点的值);printf(%c,p-rchild-data);printf(n);/此处输出p的左右孩子节点的值printf(n);printf(二叉树b的深度:%dn,btnodeheight(b);/输出b的高度printf(二叉树

12、b的结点个数:%dn,nodescount(b);/输出b的节点个数printf(n);printf( 先序遍历序列:n);/输出b的四种遍历顺序printf( 算法:);preorder(b);printf(n);printf( 中序遍历序列:n);printf( 算法:);inorder(b);printf(n);printf( 后序遍历序列:n);printf( 算法:);postorder(b);printf(n); printf( 层次遍历序列:n);printf( 算法:);levelorder(b); printf(n);四、实验心得与小结通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理