实验六、树和二叉树的操作

一、实验目的

1．进一步掌握树的结构及非线性特点，递归特点和动态性。

2．进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法。

二、实验内容

二叉树的实现和运算

三、实验要求

1．用C++/C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．分析算法，并简要给出算法设计小结和心得。

四、程序实现

#include＜iostream.h＞

#include＜stdlib.h＞

typedef char DataType;

typedef struct BitNode

{

DataType data;

struct BitNode *lchild,*rchild;

}*BitTree;

void BinTreeInit(BitTree &BT)//初始化二叉树，即把树根指针置空

{

BT=(BitTree)malloc(sizeof(BitNode));

BT-＞data=NULL;

cout＜＜"二叉树初始化成功!"＜＜endl;

}

int BinTreeCreat(BitTree &BT)//按先序次序建立一个二叉树

{

char ch;

cin＞＞ch;

if(ch=='#') BT=NULL;

else

{

if(!(BT=(BitTree)malloc(sizeof(BitNode))))

exit(0);

BT-＞data=ch;

BinTreeCreat(BT-＞lchild);

BinTreeCreat(BT-＞rchild);

}

return 0;

//cout＜＜"按先序序列建立一个二叉树已经完成!"＜＜endl;

}

void BinTreeEmpty(BitTree &BT)//检查二叉树是否为空

{

if(BT-＞data==NULL)

cout＜＜"是空二叉树!"＜＜endl;

else

cout＜＜"不是空二叉树!"＜＜endl;

}

void BinTraverse(BitTree &BT)//先序序列遍历二叉树

{

if(BT!=NULL)

{

cout＜＜BT-＞data;

BinTraverse(BT-＞lchild);

BinTraverse(BT-＞rchild);

}

}

int BinTreeDepth(BitTree BT)//求二叉树的深度

{

int depthval;

if(BT)

{

int depthLeft=BinTreeDepth(BT-＞lchild);

int depthRight=BinTreeDepth(BT-＞rchild);

depthval=1+

(depthLeft＞depthRight?depthLeft:depthRight);

}

else depthval=0;

return depthval;

}

int BinTreeCount(BitTree BT)//求二叉树中所有结点数

{

int node;

if(BT)

{

int lchild=BinTreeCount(BT-＞lchild);

int rchild=BinTreeCount(BT-＞rchild);

node=lchild+rchild+1;

}

else

node=0;

return node;

}

void main()

{

int i;

BitTree BT;

cout＜＜"1、初始化二叉树:"＜＜"\n2、按先序序列建立二叉树"＜＜"\n3、判断二叉树是否为空:";

cout＜＜"\n4、先序序列遍历二叉树"＜＜"\n5、求二叉树的深度"＜＜"\n6、求二叉树节点的个数"＜＜endl;

for(;;)

{

cout＜＜"输出你所需的操作:";

cin＞＞i;

if(i==1)

BinTreeInit(BT);

else if(i==2)

{

cout＜＜"输入你要建立的二叉树:"＜＜endl;

BinTreeCreat(BT);

}

else if(i==3)

BinTreeEmpty(BT);

else if(i==4)

BinTraverse(BT);

else if(i==5)

cout＜＜"二叉树的深度:"＜＜BinTreeDepth(BT)＜＜endl;

else if(i==6)

cout＜＜"二叉树的节点数"＜＜BinTreeCount(BT)＜＜endl;

else

return ;

}

}

五、写出输入数据及运行结果

六、心得体会

树是常用的数据结构。通过实验加深了我对树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。

通过实验，有如下几点收获和体会：

1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。

2、编程需要有耐心，尤其实在单步调试的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的错误，也要勇于推翻自己之前的思路，要坚信“没有最好，只有更好”。编程，最好是一鼓作气，得天天“摸摸”它，时时想着它，要是过一阵再去碰它那就得先去读懂自己的程序了，一切的一切几乎都得从头开始。编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。

3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要。

4、由于编程的积累，我发现调试程序的速度明显加快了，这是个很好的进步，不过，我编程的速度仍然有待提高。

5、摸索着用C++/C做完实验，增强了自己的自学能力，这应该是最有用的吧，语言会过时，学习的能力却不会过时。

每次实验都会有多多少少的收获，这些收获将成为以后学习中一笔不可或缺的财富。

 

第二篇：二叉树的基本操作及哈夫曼编码译码系统的实现

实 验 报 告

二叉树的基本操作及哈夫曼编码译码系统的实现

（20## / 20## 学年 第 二 学期）

实 验 报 告

实 验 报 告