实验三 二叉树的基本运算

实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容1、问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：

(1).按先序序列构造一棵二叉链表表示的二叉树T；

(2).对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；

(3).求二叉树的深度/结点数目/叶结点数目；(选做)

(4).将二叉树每个结点的左右子树交换位置。（选做）2、基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。3、测试数据如输入：abc00de0g00f000（其中ф表示空格字符）

先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代码#include<malloc.h> #include<iostream.h> #defineOK1 #defineERROR-1 typedefcharTElemType; inti; typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild; }BiTNode,*BiTree; intCreateBiTree(BiTree&T)//创建二叉树 { chara; cin>>a; if(a=='0')T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))){returnERROR;} T->data=a; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } returnOK; } intPreOrderTraverse(BiTree&T)//先序遍历二叉树 { if(T) { //cout<<"此为先序遍历"<<endl; cout<<T->data<<"->"; if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) returnOK; returnERROR; }elsereturnOK; } intInOrderTraverse(BiTree&T)//中序遍历二叉树 { if(T) { //cout<<"此为中序遍历"<<endl; if (InOrderTraverse(T->lchild)) { cout<<T->data<<"->"; if(InOrderTraverse(T->rchild)) returnOK; } returnERROR; }elsereturnOK; } intPostOrderTraverse(BiTree&T) //后序遍历二叉树 { if(T) { //cout<<"此为后序遍历"<<endl; if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) { cout<<T->data<<"->"; i++; return(OK); } return(ERROR); } else return(OK); } intCountDepth(BiTree&T)//计算二叉树的深度 { if(T==NULL) { return0; } else { intdepl=CountDepth(T->lchild); intdepr=CountDepth(T->lchild); if(depl>depr) { returndepl+1; } else { returndepr+1; } } } voidmain()//主函数 { BiTreeT; cout<<"请输入二叉树节点的值以创建树"<<endl; CreateBiTree(T); cout<<"此为先序遍历"; PreOrderTraverse(T); cout<<"end"<<endl; cout<<"此为中序遍历"; InOrderTraverse(T); cout<<"end"<<endl; cout<<"此为后序遍历"; PostOrderTraverse(T); cout<<"end"<<endl<<"此树节点数是"<<i<<endl<<"此树深度是"<<CountDepth(T)<<endl; }四、调试结果及运行界面：实验心得通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。还有很多很多知识我是通过看书本、请教同学老师的，但是想深一层，这都是暴露了我对知识掌握得不牢固的表现，我不能够过分依赖，而是应该平常多多上机实践来巩固知识，发现问题并解决问题。把学过的二叉树的操作的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。最佳答案#include<stdio.h>#include<malloc.h>#defineM10typedefintDataType;/*元素的数据类型*/typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BitTNode,*BiTree;intfront=0,rear=0;BitTNode*que[10];BitTNode*creat(){BitTNode*t;DataTypex;scanf("%d",&x);if(x==0)t=NULL;else{t=(BitTNode*)malloc(sizeof(BitTNode));t->data=x;t->lchild=creat();t->rchild=creat();}return(t);}/*creat*//*前序遍历二叉树t*/voidpreorder(BiTreet){if(t!=NULL){printf("%4d",t->data);preorder(t->lchild);preorder(t->rchild);}}/*中序遍历二叉树t*/voidinorder(BiTreet){if(t!=NULL){inorder(t->lchild);printf("%4d",t->data);inorder(t->rchild);}}/*后序遍历二叉树t*/voidpostorder(BiTreet){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%4d",t->data);}}voidenqueue(BitTNode*t){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}/*enqueue*/BitTNode*delqueue(){if(front==rear)returnNULL;{front=(front+1)%M;return(que[front]);}}/*delqueue*//*按层次遍历二叉树t*/voidlevorder(BiTreet){BitTNode*p;if(t!=NULL){enqueue(t);while(front!=rear){p=delqueue();printf("%4d",p->data);if(p->lchild!=NULL)enqueue(p->lchild);if(p->rchild!=NULL)enqueue(p->rchild);}}}/*levorder*////////////////////////////////////////////////////////////////////计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法intBTreeDepth(BitTNode*BT){intleftdep,rightdep;if(BT==NULL)return(0);else{leftdep=BTreeDepth(BT->lchild);rightdep=BTreeDepth(BT->rchild);if(leftdep>rightdep)return(leftdep+1);elsereturn(rightdep+1);}}intnodecount(BitTNode*BT){if(BT==NULL)return(0);elsereturn(nodecount(BT->lchild)+nodecount(BT->rchild)+1);}intleafcount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL&&BT->rchild==NULL)return(1);elsereturn(leafcount(BT->lchild)+leafcount(BT->rchild));}intnotleafcount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL&&BT->rchild==NULL)return(0);elsereturn(notleafcount(BT->lchild)+notleafcount(BT->rchild)+1);}intonesoncount(BitTNode*BT){if(BT==NULL)return(0);elseif((BT->lchild==NULL&&BT->rchild!=NULL)||(BT->lchild!=NULL&&BT->rchild==NULL))return(onesoncount(BT->lchild)+onesoncount(BT->rchild)+1);elsereturn(onesoncount(BT->lchild)+onesoncount(BT->rchild));}inttwosoncount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL||BT->rchild==NULL)return(twosoncount(BT->lchild)+twosoncount(BT->rchild));elseif(BT->lchild!=NULL&&BT->rchild!=NULL)return(twosoncount(BT->lchild)+twosoncount(BT->rchild)+1);}main(){BitTNode*root;root=creat();printf("\n按先序遍历次序生成的二叉树");printf("\n前序遍历二叉树");preorder(root);printf("\n中序遍历二叉树");inorder(root);printf("\n后序遍历二叉树");postorder(root);printf("\n层次顺序遍历二叉树");levorder(root);printf("\n二叉树深度:%d\n",BTreeDepth(root));printf("总结点个数:%d\n",nodecount(root));printf("叶子结点个数:%d\n",leafcount(root));printf("非叶子结点个数:%d\n",notleafcount(root));printf("具有双孩子结点个数:%d\n",twosoncount(root));printf("具有单孩子结点个数:%d\n",onesoncount(root));}#include"iostream.h"#include"stdlib.h"#include"conio.h"#include"stdio.h"char*str="";//二叉树结点的定义typedefstructBTNode{chardata;structBTNode*lc;structBTNode*rc;}BTNode,*BiTree;//教材P131算法6.4：二叉树的建立voidCreat(BiTree&T){charch;ch=getche();//cin.get(ch);if(ch=='@')T=NULL;else{T=newBTNode;T->data=ch;Creat(T->lc);Creat(T->rc);}}//先序遍历voidPreOrder(BiTreeT){inti=0;if(T){cout<<T->data<<'';str[i]=T->data;i++;PreOrder(T->lc);PreOrder(T->rc);}}//中序遍历voidInOrder(BiTreeT){if(T){InOrder(T->lc);cout<<T->data<<'';InOrder(T->rc);}}//后序遍历voidPostOrder(BiTreeT){if(T){PostOrder(T->lc);PostOrder(T->rc);cout<<T->data<<'';}}voidmain(){intc;BiTreeT;printf("Inputnodesofbinarytree:(NULL<=>'@')\n");Creat(T);while(1){cout<<"\nPleaseselectaservice:\n";cout<<"\n1:PreOrderTraverse\n2:InOrderTraverse\n3:PostOrderTraverse\n0:Exit\n";cin>>c;switch(c){case1:{cout<<"\nPreOrdertraverse:\n";PreOrder(T);break;}case2:{cout<<"\nInOrdertraverse:\n";InOrder(T);break;}case3:{cout<<"\nPostOrdertraverse:\n";PostOrder(T);break;}default:{cout<<"GameOver!\n";exit(1);}}}}#include"stdio.h"#include"string.h"#defineNULL0typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreate(BiTreeT){charch;ch=getchar();if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}returnT;}voidP