二叉树基本操作+数据结构+实验报告(2)

第 6 页 共 12 页

Status BinTreeCreat(BitTree &BT) {

scanf(\ if(e=='0) BT=NULL; else

{ BT=(BinNode*)malloc(sizeof(BinNode));

BT->data=e; /*生成根结点*/ BinTreeCreat(BT->lchild); /*构造左子树*/ BinTreeCreat(BT->rchild); /*构造右子树*/ }

return OK; }

3. 检查二叉树是否为空

Status BinTreeEmpty(BitTree BT) { if(BT==NULL) return ERROR; else return OK; }

4. 前序遍历

Status PreBinTraverse(BitTree BT) { if(BT!=NULL)

{printf(\ PreBinTraverse(BT->lchild); PreBinTraverse(BT->rchild);

}

Return OK; }

5. 中序遍历

Status InBinTraverse(BitTree BT) { if(BT!=NULL)

{InBinTraverse(BT->lchild); printf(\ InBinTraverse(BT->rchild); }

Return OK; }

6. 后序遍历

6

第 7 页 共 12 页

Status PastBinTraverse(BitTree BT) { if(BT!=NULL)

{PastBinTraverse(BT->lchild); PastBinTraverse(BT->rchild);

printf(\ }

Return OK; }

7. 求二叉树的深度

Int BinTreeDepth(BitTree BT){ int i=1,j=1; if(BT==NULL) return ERROR; else {

i=BinTreeDepth(BT->lchild); j=BinTreeDepth(BT->rchild); if(i>j)

return(i+1); else

return (j+1); } }

8. 求二叉树中所有结点数

BitTree BinTreeCount(BitTree BT) { if(BT==NULL) return 0; else

return (BinTreeCount(BT->lchild)+BinTreeCount(BT->rchild)+1); }

9. 清除二叉树，使之变为空树 Status BinTreeClear(BitTree &BT){ if(BT){

if(BT->lchild)

BinTreeClear(BT->lchild); if(BT->rchild)

BinTreeClear(BT->rchild); free(BT); BT=NULL;

7

第 8 页 共 12 页

Return OK; } }

五．调试分析

调试第一步：找出一些因为粗心而导致的错误如：少大括号，少逗号，字母打错，没有分清大小写，等等。

调试第二步：在这一步的调试中主要想谈谈函数BinTreeDepth(BitTree BT)，

BinTreeClear(BitTree &BT)这2个函数的调试。

在BinTreeDepth(BitTree BT)函数中因为没有把最后的i和j加1所以最后的结果都少了一层，后来把i和j分别加上了1就可以了。在BinTreeClear(BitTree &BT函数中因为没有BT=NULL;而出现了错误后来改正了以后就好了。

六．结果测试

操作界面为选择1后：

。

。

选择2：

0，0，0，建立一棵树。 选择3：

，分别输入1，2，3，0，0，4，5，0，

选择4：

选择5：

8

第 9 页 共 12 页

选择6：选择7：选择8：选择9：选择0：

七．心的体会

这个实验是所有的实验中难度最大的一个了，因为以前对树这种结构没有什么接触所以感觉比较陌生，在树的建立过程中虽然用的是递归算法但还是出现了错误，就是没有正确的领悟到结束的条件，在一个节点的结束时没有把它的左右孩子都置为空，后来经过仔细的思考才明白，只有把结点的左右孩子都置空才算把这个结点结束。

在遍历时因为用的是递归所以没有出现什么错误，一开始对遍历的递归不是很相信，不太相信那样 就可以把一棵树遍历出来，经过这个实验以后就没有怀疑了。

在后面的求结点和深度和销毁树中都用的是递归算法，所以经过这个实验后对递归这个工具有了很深的理解，从开始的懵懂慢慢变的清晰和理解了。

通过这个实验以后加深了对树这种新的结构的了解和理解。

八．源代码

# include # include # include typedef struct BitNode{ int data;

struct BitNode *lchild,*rchild; }BitNode,*BitTree; BitTree BitTreeInit(){ BitTree BT;

BT=(BitNode*)malloc(sizeof(BitNode)); BT=NULL; return BT;

9

第 10 页 共 12 页

}

BitTree BitTreeCreat(BitTree &BT){ int ch;

printf(\请输入节点的内容,输入0时结束建立！\\n\ scanf(\ if(ch==0) BT=NULL; else{

BT=(BitTree)malloc(sizeof(BitNode)); BT->data=ch;

BitTreeCreat(BT->lchild); BitTreeCreat(BT->rchild); }

return BT; }

void BitTreeEmpty(BitTree BT){ if(BT==NULL)

printf(\树为空！\\n\ else

printf(\树非空！\\n\ }

void PreOrderTraverse(BitTree BT){ if(BT!=NULL){

printf(\树结点的内容为:%d\\n\ PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); } }

void InOrderTraverse(BitTree BT){ if(BT!=NULL){

InOrderTraverse(BT->lchild);

printf(\树结点的内容为:%d\\n\ InOrderTraverse(BT->rchild); } }

void PostOrderTraverse(BitTree BT){ if(BT!=NULL){

PostOrderTraverse(BT->lchild); PostOrderTraverse(BT->lchild);

printf(\树结点的内容为:%d\\n\ } }

int count(BitTree BT){ if(BT==NULL)

10