数据结构与算法实验报告(2)

数据结构实验报告

题目： 树 班级：网络工程1401班 学号： 1408020106 指导教师： 高峰 日期： 2016/7/6

实验二：树

一：实验要求

掌握二叉树，二叉树排序数的概念和存储方法。

掌握二叉树的遍历算法。

熟练掌握编写实现树的各种运算的算法。

二．实验内容

统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。

三：实验过程及步骤

#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; }

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) return 0; else

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

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

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

return(i+1); else

return (j+1); } }

void BinTreeClear(BitTree &BT){ if(BT){

if(BT->lchild)

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

BinTreeClear(BT->rchild); free(BT); BT=NULL; } } main(){

int i=1,j,l; BitTree BT; while(i!=0){

printf(\欢迎使用-------------------\\n\ printf(\请选择要进行的操作\\n\

printf(\初始化一棵树 2.建立一棵树 3.判断树是否为空\\n\ printf(\按前序遍历树 5.按中序遍历树 6.按后序遍历树\\n\ printf(\求树的深度 8.求树的结点数 9.把树清空\\n\ printf(\退出操作界面\\n\

printf(\谢谢使用-------------------\\n\ scanf(\ switch(j){

case 1:BT=BitTreeInit();printf(\树已经初始化！\\n\ case 2:BitTreeCreat(BT);break; case 3:BitTreeEmpty(BT);break; case 4:PreOrderTraverse(BT);break; case 5:InOrderTraverse(BT);break; case 6:PostOrderTraverse(BT);break;

case 7:l=BinTreeDepth(BT);printf(\树的深度为：%d\\n\ case 8:l=count(BT);printf(\树的结点数为：%d\\n\ case 9:BinTreeClear(BT);printf(\树已经清空！\\n\ case 0:exit(0); } } }

步骤：

1.选择进行的操作

2.初始化、建立、判断树是否空、先/中/后序遍历、求深度/结点，清空树 3.显示结果

四：实验结果及分析

分析：

本程序不仅可以统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。

同时让他有以下功能：1.初始化一棵树。2.建立一棵树。3.判断树是否为空。4.分别按先/中/后序遍历树。5.求树的深度。6.求树的结点数。7.清空树。