二叉树的参数计算

实验六二叉树的参数计算实验学时：2实验类型：（综合型）一、实验目的1.理解二叉树遍历算法的应用；2.掌握计算二叉树结点个数、高度、叶子结点个数算法实现；3.掌握交换二叉树左右子树以及复制一棵二叉树算法的实现；4.二、实验条件VisualC++6.0三、实验原理及相关知识1.二叉树的存储结构描述；2.求二叉树结点个数、高度、叶子结点个数算法的基本思想；3.交换二叉树左右子树以及复制一棵二叉树算法的基本思想。四、实验步骤1.确定存储结构，写出二叉链表结构类型的具体定义。2.二叉树参数计算的算法实现(1)求结点个数、高度、叶子结点个数、交换二叉树左右子树以及复制一棵二叉树的递归算法的基本思想及算法实现；(2)求结点个数、叶子结点个数的非递归算法的基本思想及算法实现；五、思考题及其它1.二叉树遍历算法求解二叉树的其他相关问题。2.树的遍历算法的实现。3.赫夫曼编码和解码算法实现。【参考程序】#includestdio.h#includemalloc.h#includemath.h#defineMaxSize20typedefintElemType;#defineOK1intcount;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//建立二叉树（按先序序列生成二叉树,#表示空节点）voidCreateBiTree(BiTree*T){charch;scanf(%c,&ch);getchar();/*回车键（每次输入一个字符后，需敲回车键）*/if(ch=='#'){printf(不产生子树。\n);*T=NULL;}else{if(!(*T=(BiTNode*)malloc(sizeof(BiTNode)))){printf(分配空间失败);return;}//生成一个新节点(*T)-data=ch;printf(产生左右子树。\n);CreateBiTree(&((*T)-lchild));CreateBiTree(&((*T)-rchild));}}intCount_Tree(BiTreet)//计算二叉树的结点个数。{intlcount,rcount;if(t==NULL)return0;lcount=Count_Tree(t-lchild);//求左子树的结点个数rcount=Count_Tree(t-rchild);//求右子树的结点个数returnlcount+rcount+1;}intNCount_Tree(BiTreet)//非递归算法计算二叉树的结点个数。{}intHeight(BiTreet)//计算二叉树的高度{inth1,h2;if(t==NULL)return0;else{h1=Height(t-lchild);//求左子树的高度h2=Height(t-rchild);if(h1h2)returnh1+1;//求右子树的高度returnh2+1;}}voidCountleaf(BiTreet,int*count)//计算二叉树的叶子结点的个数{if(t==NULL)*count=0;if(t-lchild==0&&t-rchild==0)(*count)++;if(t-lchild!=0)Countleaf(t-lchild,count);if(t-rchild!=0)Countleaf(t-rchild,count);}voidNCountleaf(BiTreet,int*count)//非递归算法计算二叉树的叶子结点的个数{}voidSwapbitree(BiTreet)//交换二叉树的左右子树{BiTreep;if(t==NULL)return;Swapbitree(t-lchild);Swapbitree(t-rchild);p=t-lchild;t-lchild=t-rchild;t-rchild=p;}voidCopybitree(BiTreet1,BiTreet2)//复制一棵二叉树{if(t1==NULL){t2=NULL;return;}t2=(BiTree)malloc(sizeof(BiTNode));t2-data=t1-data;Copybitree(t1-lchild,t2-lchild);Copybitree(t1-rchild,t2-rchild);}voidPreorder(BiTreeT){if(T){printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);}}voidmain(){BiTreeT=NULL,T1=NULL;intj;intsign=1;intnum;count=0;printf(本程序可以建立二叉树、求二叉树的结点个数、高度、叶子结点个数，交换二叉树的左右子树，复制一棵二叉树。\n);printf(请将二叉树的先序序列输入以建立二叉树。\n);printf(您必须一个一个地输入字符。\n);while(sign){printf(请选择:\n);printf(1.生成二叉树（#表示空结点）\n);printf(2.递归求结点个数3.非递归求结点个数\n);printf(4.递归求高度5.递归求叶子结点个数\n);printf(6.非递归求叶子结点个数7.递归交换二叉树左右子树\n);printf(8.递归复制一棵二叉树9.输出二叉树\n);printf(0.退出程序\n);scanf(%d,&j);getchar();switch(j){case1:printf(生成二叉树:);CreateBiTree(&T);printf(\n);printf(\n);break;case2:if(T){printf(递归求二叉树的结点个数：\n);printf(二叉树的结点个数为：%d\n,Count_Tree(T));}elseprintf(二叉树为空!\n);break;case3:if(T){printf(非递归求二叉树的结点个数：\n);printf(二叉树的结点个数为：%d\n,NCount_Tree(T));}elseprintf(二叉树为空!\n);break;case4:if(T){printf(递归求二叉树的高度：\n);printf(二叉树的高度为：%d\n,Height(T));}elseprintf(二叉树为空!\n);break;case5:if(T){printf(递归求二叉树的叶子结点个数：\n);Countleaf(T,&count);printf(二叉树的叶子结点个数为：%d\n,count);}elseprintf(二叉树为空!\n);break;case6:if(T){printf(非递归求二叉树的叶子结点个数：\n);NCountleaf(T,&count);printf(二叉树的叶子结点个数为：%d\n,count);}elseprintf(二叉树为空!\n);break;case7:if(T){printf(递归交换二叉树左右子树：\n);Swapbitree(T);Preorder(T);printf(\n);}elseprintf(二叉树为空!\n);break;case8:if(T){printf(递归复制二叉树左右子树：\n);Copybitree(T,T1);Preorder(T1);printf(\n);}elseprintf(二叉树为空!\n);break;case9:if(T){printf(二叉树的遍历序列为：);Preorder(T);printf(\n);}elseprintf(二叉树为空!\n);break;default:sign=0;printf(程序运行结束，按任意键退出!\n);}}}