二叉树的基本操作及应用

实验报告实验报告（三）实验题目二叉树的基本操作及应用实验时间6月10日实验地点B07-B214实验成绩实验性质□应用性□设计性□综合性教师评阅：评阅教师签名：一、实验目的1熟悉二叉树的存储构造和对二叉树的基本操作。2掌握对二叉树前序、中序、后序遍历操作的具体实现。3学习运用递归办法编写对二叉树这种递归数据构造进行解决的算法。4会应用二叉树的基本操作解决简朴的实际问题二、实验内容和规定(阐明算法的时间复杂度)1基于二叉链表的存储格式，输入二叉树的先序序列，用*代表空节点，如ABD**CE**F**建立二叉树，然后中序遍历二叉树，输出节点的值。2针对建好的二叉树，编写递归程序，求树中叶子节点个数。3针对建好的二叉树，编写递归程序，求二叉树的高度。4针对建好的二叉树，试编写二叉树的前序非递归遍历算法。三、重要设计思想与算法（此处不够可加页，或在背面书写）该实验重要涉及一下几个函数，算法核心分别在各函数中。建立树的构造。typedef structBiTNode{ charelement; Treelchild,rchild;};//B数的基本结点输入ABD**CE**F***TreeCreateBTree(void)//能够返回一种Tree指针{ TreepTree; charval; scanf("%c",&val); printf("%c",val); if(val=='*'||val=='^p')returnNULL;//根据输入字符先序建树 else//*代表空 { pTree=(Tree)malloc(sizeof(structBiTNode)); if(pTree==NULL) { printf("内存分派失败！"); exit(-1);//避免程序不懂得空间不够用了 } pTree->element=val; pTree->lchild=CreateBTree(); pTree->rchild=CreateBTree();//递归，NLR地创立结点 } returnpTree;};数叶结点个数intCountLeaf(TreeT){ if(T==NULL)return0; if(!T->lchild&&!T->rchild) { return1;//两个儿子都空则阐明是叶子，返回1 } else { returnCountLeaf(T->lchild)+CountLeaf(T->rchild);//数左右子树总共的叶结点 } };3.数树的深度intCountLevel(TreeT){ if(!T)return0; else { intLeft=CountLevel(T->lchild);intRight=CountLevel(T->rchild); return1+(Left>Right?Left:Right);//三目运算取最大 }};//最后数得树的最深层数，也是递归typedefstruct{ Treeelements[MAXSIZE];//注意这里放的是指针 inttop;}Stack;//这是一种用于装Tree指针的栈4.这是用非递归实现先序遍历的voidPreOrder(TreeT){StackS; Treep; InitStack(&S);//造一种栈待会儿用 p=T;//用p指针来不停解决结点操作while(p||!IsEmpty(S)) {while(p) { printf("%c",p->element);//只要不空则把p指的数据输出 Push(&S,p);p=p->lchild;//继续往左边找 }//一旦停下来阐明找到了空结点，则开始往上一层的右边找一下 if(!IsEmpty(S)) {//栈非空 p=Pop(&S);//退栈，找到刚刚说的上一层 p=p->rchild;//找右边了 } }//只要while还循环阐明没有遍历完，现在再一次从刚刚的右边执行先序遍历};四、实验成果（设计文档、文稿寄存途径，能够截图描述实验成果）#include<stdio.h>#include"3.h"intmain(void)//改主程序对应上图成果{ TreepTree; inti,j; pTree=CreateBTree();//创立二叉树pTree i=CountLeaf(pTree); printf("Thereare%dleaves!",i);//递归程序数叶节点 j=CountLevel(pTree); printf("Thereare%dlevels!",j);//递归程序数层数 PreOrder(pTree);//按照前序遍历输出该书的元素 return0;}五、实验分析总结本次实验采用二叉树存储了一系列的字符串，通过函数TreeCreateBTree(void)得到一种根据输入创立的二叉树构造，时间复杂度是O（n）；通过函数intCountLeaf(TreeT)递归返回叶子个数，时间复杂度O(n)；通过intCountLevel(TreeT)返回最深途径得到树的深度，时间复杂度O（n）；；最后用voidPreOrder(TreeT)实现非递归写法的二叉树先序遍历，时间复杂度为O(n).总而言之，由于都是要遍历B数的每个节点，因此程序执行的时间长度和输入的字符串长度n是线性增加的。他们的时间复杂度都是O(n).这次实验，我更深刻的理解了B数的基本性质如递归性，运用递归，我们能够很方便的写出多个对树的操作；熟悉了创立树，遍历树的基本办法；体会了算法的代码实现