二叉树的定义与基本操作.doc

二叉树的定义及基本操作 一、实验目的、意义 （1）熟悉二叉链表表示的二叉树结构及其递归遍历2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。3）根据具体问题的需要，能够设计出相关算法。 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： （1）定义二叉树的链式存储结构； （2）建立一颗二叉链表表示的二叉树； 对其进行前序，中序，后序输出。 C语言算法、循环算法、二叉树结构及其递归遍历二叉链表前序，中序，后序输出 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 五、总结与体会 （调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。） (调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。) 调试时，由于对所学知识点概念模糊，二叉树结构及其递归遍历 六、程序清单(包含注释) #includeiostream.h #includestdlib.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二叉树初始化成功!; } int BinTreeCreat(BitTree BT)//按先序次序建立一个二叉树 { char ch; cinch; if(ch==#) BT=NULL; else { if(!(BT=(BitTree)malloc(sizeof(BitNode)))) exit(0); BT-data=ch; BinTreeCreat(BT-lchild); BinTreeCreat(BT-rchild); } return 0; // 按先序序列建立一个二叉树已经完成! } void BinTreeEmpty(BitTree BT)//检查二叉树是否为空 { if(BT-data==NULL) cout是空二叉树!; else cout不是空二叉树!; } void BinTraverse1(BitTree BT)//先序序列遍历二叉树 { if(BT!=NULL) { coutBT-data; BinTraverse1(BT-lchild); BinTraverse1(BT-rchild); } } void BinTraverse2(BitTree BT)//中序序列遍历二叉树 { if(BT!=NULL) { BinTraverse2(BT-lchild); coutBT-data; BinTraverse2(BT-rchild); } } void BinTraverse3(BitTree BT)//后序序列遍历二叉树 { if(BT!=NULL) { BinTraverse3(BT-lchild); BinTraverse3(BT-rchild); coutBT-data; } } int BinTreeDepth(BitTree BT)//求二叉树的深度 { int depthval; if(BT) { int depthLeft=BinTreeDepth(BT-lchild); int depthRight=BinTreeDepth(BT-rchild); depthval=1+ (depthLeftdepthRight?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