二叉树 数据结构实验 c语言写的控制台程序

#include <iostream> #include <math.h> using namespace std; typedef char TElemType; typedef struct BiTNode{ //定义节点 TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int DLRcreat(BiTree &T) //先序建立二叉树 { char d; cin>>d; if(d=='#')T=NULL; else { T=new BiTNode; if(!T)exit(1);//内存分配失败！ T->data=d; DLRcreat(T->lchild);//递归调用 DLRcreat(T->rchild); } return 0; } int florder(BiTree T) //层序遍历 指针数组 { BiTNode *Q[100]; //树节点指针数组，用于存放遍历到的元素地址 if(T==NULL)cout<<"空的二叉树"<<endl; Q[0]=T; //存入树根 int i=0,j=1; for(i=0;i<j;i++) { if(Q[i]->lchild!=NULL) //如果有左孩子，存入地址，j加一 ，否则没操作 { Q[j]=Q[i]->lchild ; j++; } if(Q[i]->rchild!=NULL) //如果有右孩子，存入地址，j加一 ，否则没操作 { Q[j]=Q[i]->rchild ; j++; } } for(i=0;i<j;i++)cout<<" "<<Q[i]->data; return 0; } int howmuch(BiTree T,int h)//计算叶子数和深度 { BiTNode *Q[100]; //树节点指针数组，用于存放遍历到的元素地址 if(T==NULL)cout<<"空的二叉树"<<endl; Q[0]=T; //存入树根 int i=0,k=0,j=1;//j为节点数，k为叶子数，i为深度 for(i=0;i<j;i++) { if(Q[i]->lchild!=NULL) //如果有左孩子，存入地址，j加一 ，否则没操作 { Q[j]=Q[i]->lchild ; j++; } if(Q[i]->rchild!=NULL) //如果有右孩子，存入地址，j加一 ，否则没操作 { Q[j]=Q[i]->rchild ; j++; } if(Q[i]->lchild==NULL&&Q[i]->rchild==NULL)k++; //计算叶子数 } i=ceil(log(j-1))+1; //log为数学中的ln //计算深度//有问题？？？？？ if(h==0)return j;//结点数 else if(h==1)return k;//叶子数 else if(h==2)return i;//深度 else {cout<<"参数错误";} return 0; } int DLRorder(BiTree T) //先序遍历 递归 { if(T) { cout<<" "<<T->data; // 访问根结点 DLRorder(T->lchild); // 前序遍历左子树 DLRorder(T->rchild); // 前序遍历右子树 } return 0; } int LDRorder(BiTree T) //中序遍历 递归 { if(T) { LDRorder(T->lchild); cout<<" "<<T->data; LDRorder(T->rchild ); } return 0; } int LRDorder(BiTree T) //后序遍历 递归 { if(T) { LRDorder(T->lchild); LRDorder(T->rchild ); cout<<" "<<T->data; } return 0; } int exchang(BiTree &T) //交换左右子树 { if(T) { if(T->lchild&&T->rchild) //当有左右孩子时才交换 { char t; t=T->lchild->data; T->lchild->data=T->rchild->data; T->rchild->data=t; //交换数据 } exchang(T->lchild); // 递归调用 exchang(T->rchild); } return 0; } int IsEmpty(BiTree &T) //判断是树否为空 { if(T) return 1; else return 0; } int DestroyBiTree(BiTree &T)//销毁二叉树 { if(T) { DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); T=NULL; } return 0; } int choose(BiTree T) //功能选择 { int a,b; cin>>a; b=IsEmpty(T);//判断二叉树是否为空 switch(a) { case 0: { cout<<"请输入数据："; DLRcreat(T); cout<<"创建成功！"<<endl;break;} case 1: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"先序遍历";DLRorder(T);break;} case 2: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"中序遍历";LDRorder(T);break;} case 3: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"后序遍历";LRDorder(T);break;} case 4: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"层序遍历";florder(T);break;} case 5: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"总节点数："<<howmuch(T,0);break;} case 6: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"总叶子数："<<howmuch(T,1);break;} case 7: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"树的深度："<<howmuch(T,2);break;} case 8: {if(!b) {cout<<"二叉树为空！"<<endl;break;} cout<<"交换前"<<endl;florder(T); exchang(T); cout<<"交换后";florder(T);break;} case 9: {if(b) cout<<"二叉树非空！"; else cout<<"二叉树为空！";break;} case 10: {if(!b) {cout<<"二叉树为空！"<<endl;break;} DestroyBiTree(T); cout<<"销毁成功！"<<endl;break;} default: exit(1); } cout<<endl<<"操作完成,请输入下一个操作"<<endl; choose(T); return 0; } int main() //主函数 { cout<<"----------------二叉树的基本操作----------------"<<endl; cout<<"请先建立二叉树，按先序的方式输入如果数据为空输入#"<<endl; BiTree T; //定义二叉树，初始化 T=NULL; cout<<"0.********创建二叉树********"<<endl; cout<<"1.先序遍历二叉树 2.中序遍历二叉树"<<endl; cout<<"3.后序遍历二叉树 4.层序遍历二叉树"<<endl; cout<<"5.求总节点数 6.求叶子总数"<<endl; cout<<"7.深度-完全二叉树有效 8.左右子树交换"<<endl; cout<<"9.判断二叉树是否为空 10.销毁二叉树"<<endl; cout<<"11.其他键退出"<<endl; choose(T); return 0; }