2024年二叉树实验报告

二叉树试验汇报問題描述（1）問題描述：①用先序递归過程建立二叉树(存储构造：二叉链表)。输入数据按先序遍历所得序列输入，當某結點左子树或右子树為空時，输入‘*’号，如输入abc**d**e**得到的二叉树為：aaebebddcc②编写递归算法，计算二叉树中叶子結點的数目。③按凹入表方式输出该二叉树。分析：①此題规定用二叉链表作為存储构造，首先要定义二叉链表：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;structBiTNode*lchild,*rchild中lchild，rchild分别表达该結點的左右孩子。②输入時，按先序遍历所得序列输入，當某結點左子树或右子树為空時，输入‘*’号。③输出以凹入表的形式输出。算法思想按照规定，這道題采用二叉链表来存储矩阵的有关信息。存储构造定义為：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;題中共有四個函数，包括主函数main()，创立二叉树函数Statuspreorder(BiTree&T)，计算叶子結點函数StatuscalLeaf(BiTree&T)，输出函数Statusoutput(BiTree&T,int)。其中，主函数首先调用preorder()创立二叉树，然後调用函数calLeaf()。最终调用函数output()，输出二叉树。算法描述：main(){BiTreeT;intdepth=0;//打印提醒語//输入先序序列preorder(T);//调用函数，先序创立二叉树calLeaf(T);//调用函数calLeaf()计算叶子結點数并打印output(T,depth);//调用函数凹入输出system("pause");return0;}//创立Statuspreorder(BiTree&T){charch;scanf("%c",&ch);//讀入数据if(ch=='*')T=NULL;//讀到*号，表明该結點無孩子else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))//動态申請exit(OVERFLOW);T->data=ch;//将数据计入結點的数据域//递归调用}}//CreatBiTree//计算叶子結點数StatuscalLeaf(BiTree&T){if(空树,無叶子)returnERROR;elseif(只有左孩子或右孩子)return1;/else递归调用}Statusoutput(BiTree&T,intdepth){inti;if(目前結點不為空){depth++;//深度加1//打印元素前空格//打印数据if(左孩子)if(!output(T->lchild,depth))returnERROR;//递归if(右孩子)if(!output(T->rchild,depth))returnERROR;//递归returnOK;}elsereturnERROR;}源程序已提交测试成果顾客使用阐明：①运行环境：visualC++6.0Dev-c++②程序启動：Ctrl+F10③操作环节：按照提醒输入④输入：abc**d**e**图1打印提醒語，运行正常。按规定输入先序遍历序列，按该序列得到的二叉树為图1所示二叉树，叶子結點数為3，a在第一层，b，e在第二层，c，d在第三层。运行正常。心得体會（1）StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空树,無叶子else{if(!(calLeaf(T->lchild)))num++;elseif(!(calLeaf(T->lchild)))num++;//递归调用}returnnum;}這种算法的思想是递归调用函数，當调用到没有孩子的叶子結點時，num数加1。這样依次计算，最终找到所有的叶子結點。不過，這种算法在调用時，不能记录右子树上的叶子結點，导致出現下面的錯误：因此改成了目前的算法：StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空树,無叶子elseif(!T->lchild&&!T->rchild)return1;//只有左孩子或右孩子elsereturn(calLeaf(T->lchild)+calLeaf(T->rchild));//递归调用}當T為空時，是空树，叶子結點数為0；當左孩子或右孩子有一种不存在時，叶子結點数為1；當左右孩子都存在時，递归调用，懂得找到所有的叶子結點，返回左右子树上叶子結點数之和即為所求。心得体會：這道題用二叉链表存储二叉树，二叉链表由数据元素，左孩子指针和右孩子指针构成。用二叉链表存储二叉树比较简朴，不過局限性是不能存储该节點的双亲，這种状况下，用线序序列建立二叉树比较以便。虽然是用二叉链表這种较為简朴的方式存储二叉树，但對于初次接触树的概念的我還是一种很好的锻炼机會，增强了對于二叉树孩子与双亲的关系的理解，有助于更好的理解二叉树的构造。输入数据後，循环调用创立函数，依次讀入数据并保留。创立二叉树，计算叶子結點数和打印凹入表都要用到递归函数。可以說，對树和操作都重要是對递归函数的调用，复习了對二叉链表的应用。對于递归算法，目前的理解一直比较模糊，通過這道題在一定程度上增長了對递归函数的理解。选做（1）用先序和中序遍历建立二叉树。顾客分别输入一种二叉树的先序遍历序列和中序遍历序列，通過两個遍历序列建立二叉树。（2）处理措施：二叉树存储方式不变，但在程序中增長两個字符数组pre[]和in[]分别用于寄存两個遍历序列。用递归的算法处理問題。不难发現，pre[]中的第一种元素即為根节點對应的元素。而在in[]数组中，若第i個元素等于pre[0]，那么從第一种到第i-1個元素即為根节點的左子树。按照這個措施，用递归的算法即可构建一棵完整的二叉树。算法描述：StatuscreatTree(BiTree&T,charpre[],charin[],intp,intq){inti=0;//i表达根节點在中序中的位置動态申請T->data=pre[p];//根节點i=q;while(in[i]!=pre[p])i++;if(构建左子树){//确定左子树的先序序列指针creatTre