实验报告
计算机科学与技术学院
实验教学中心
2017年11月17日
实验项目名称：二叉树的建立与遍历
一、实验目的：
(1)熟练掌握二叉树的建立方法；
(2)熟练掌握二叉树的遍历算法；
(3)掌握二叉树的应用算法。
二、实验内容：
(1)编写算法建立一棵二叉树的二叉链表；
(2)输出二叉树的三种遍历序列，包括递归算法、非递归算法；
(3)编写算法统计二叉树结点数、叶子数、深度。
三、实验结果分析
四、实验操作步骤
先按遍历顺序输入生成树，用输入替换空节点，递归生成树。
输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。
并计算出输出树的深度、叶节点数、汇点数
然后根据序列遍历序列输入建立完整的二叉树，采用非递归树。
输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。
并计算出输出树的深度、叶节点数、汇点数
五、源**
#include
#include
#include
#include
using namespace std;
//二叉树定义
typedef char elementtype;
typedef struct bitreenode
bitreenode，* bitree;
//递归的建立一棵二叉树
//以二叉树为输入的序列
void createbitree(bitree &t)
else
}void creatbitree_2(bitree &rt,int n)
bitreenode *node=new bitreenode;
node->data=tmp[0];
node->rchild=null;
node->lchild=null;
for(int j=num-2; j>0; j--)
if(a[j])t=t->rchild;
else t=t->lchild;
if(a[0])t->rchild=node;
else t->lchild=node;
}}int nodenum(bitreenode* root)//二叉树节点数目
//递归地销毁二叉树
void destroybitree(bitree &t)
}//递归预序遍历二叉树
void preordertraverse(const bitree &t)
}//递归中阶遍历二叉树
void inordertraverse(const bitree &t)
}//递归后序遍历二叉树
void postordertraverse(const bitree &t)
}//递归地查找树的深度
int depthofbitree(const bitree &t)
//递归查找二叉树的叶结点数
int leafcountofbitree(const bitree &t)
int main(int argc, char *argv)
数据结构二叉树实践报告（二）
一、需求分析：
编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、连续的操作。输入为a-z或者是a-z之间的字符，用‘@’字符作为结束当前结点的标识符。
二、概要设计：
要在此程序中使用的数据类型
struct bintreenode
；然后定义我们需要的指针类型
typedef struct bintreenode*pbintreenode； /* 定义指向二叉树结点的指针类型*/
typedef pbintreenode*pbintree； /*定义指向树型结点的指针类型*/
程序所需的自定义函数
一。创建二叉树根节点
pbintree create_bintreeroot(void)
2。创建二叉树的节点
pbintreenode create_bintreenode(void)
3．创建一棵二叉树
pbintreenode create_bintree(void)
四。用第一根法遍历二叉树
void preorder(pbintreenode pbnode)
5个。用中根法遍历二叉树
void inorder(pbintreenode pbnode)
6.使用backroot方法遍历二叉树
void postorder(pbintreenode pbnode)
7号。打印出我们创建的二叉树的树结构
void outputtree(pbintreenode pbnode,int totalspace)
8个。打印出二叉树的叶节点
void leaves(pbintreenode pbnode)
9。释放我们申请的所有结点空间
void freeallnodes(pbintreenode pbnode)
10个。判断是否输入合格字符
int isalphabet(char i)
三、详细设计：
1． pbintreenode create_bintreenode(void)
我们定义一个指向二叉树结点类型的指针pbintreenode，然后，申请一个二叉树结点大小的空间，对左右子结点赋为空。
2。创建二叉树根节点
定义一个指向二叉树结点的指针的指针即：bintreenode ** pbtree, 或者是：pbintreenode *pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：
*pbtree=create_bintree();
3． 创建一棵二叉树
首先我们定义一个datatype类型的变量i,用于存放我们输入的字符（即作为缓冲区），并用scanf函数去接收它，由于使用scanf函数时，会出现吸收我们输入的回车字符，并将会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush(stdin)将缓冲区的字符全部冲掉，然后再吸收我们输入的字符，就可以完全避免此类问题的发生。我们定义我们输入的字符是从a-z或者是a-z，用字符@为我们结束当前结点左或者右结点的字符，然后递归调用左右子树，此时我们将一棵二叉树全整的创建出来了。
四。用第一根法遍历二叉树
首先访问根结点，打印出其中的信息，然后递归调用左子树和右子树。
5个。用中根法遍历二叉树
首先递归调用左子树，打印出其中的信息，打印出根结点信息，然后递归调用右子树，打印出其中的信息。
6.使用backroot方法遍历二叉树
首先，递归地调用左子树来打印内容，然后递归地调用右子树来打印内容，然后是根结点的内容。
7号。打印出我们创建的二叉树的树结构
先递归调用右子树，如果结点不为空的话，空格数加5，如果为空的话，就打印出右子树的内容，然后递归调用左子树。
8个。打印出二叉树的叶节点
如果当前结点的左右子树都为空的话，就打印出此结点的信息，如果左子树不为空的话，递归调用左子树，如果右子树不为空的话，递归调用右子树。
9。释放我们申请的所有结点空间
如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如果都不位空的话，分别调用左右子树，如果左右都为空的话，就释放左右结点空间，并将当前结点置为空。
10．主函数的安排：
先创建好我们要的二叉树，之后，我们就可以对此而二树进行多种操作，我们定义了6种集合操作，并对用户输入的信息进行检测，正确的提示出错信息，如果选择的是我们定义的操作之一的话，对应的我们设置出不同的case语句。如果我们选择的是释放所有的结点空间的话，我们需要屏蔽掉所有的菜单信息，提示用户重新创建一棵二叉树，并对它进行重新操作。
如果我们选择退出，但是没有选择释放掉所有的节点空间时，我们需要考虑到此类的情形，应调用void freeallnodes(pbintreenode pbnode)自动的释放掉所有的结点空间，正常的退出。
四、用户使用说明：
当用户尚未创建二叉树时，系统会提示用户输入数据：
please input char to the binatree, @ to exit current node:please input a char:
这时用户用键盘输入，每输入一个字符回车一次,输入为a-z或者是a-z之间的字符，用‘@’字符作为结束当前结点的标识符
当用户创建二叉树时，将显示“控制”菜单：
please choose the mode you want to operate with the binatree:
1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:
此时，用户可以选择操作：1。自动打印出树结构。先遍历根；3。穿过中根；4。稍后遍历根
5个。打印叶结点6。释放所有结点空间0。出口
五、测试结果：
一。测试完整二叉树的情况：
输入（每输入一个字符回车一次）：a b c @ @ d @ @ e f @ @ g @ @
自动打印出树型结构：
display the binatree data directly:ge
fadb
c三种遍历方法和叶结点测试如下：
先根：data in preorder:
a b c d e f g
中根：按顺序排列的数据：
c b d a f e g
后根：data in postorder:
c d b f g e a
打印叶子结点：
leaves:
c d f g
释放所有结点空间：
free all nodes:
all node have been freed successfully.
自动提示创建新的二叉树：
now creating a new binatree...
please input char to the binatree, @ to exit current node:
please input a char:
测试不完整的二叉树的情况
输入（每个字符输入一次）：a b c d
自动打印出树型结构：
abc d
三种遍历方法和叶结点测试如下：
先根：data in preorder:
a b c d
中根：按顺序排列的数据：
d c b a
后根：data in postorder:
d c b a
打印叶子结点：
leaves:d
释放所有结点空间：
free all nodes:
all node have been freed successfully.
自动提示创建新的二叉树：
now creating a new binatree...
please input char to the binatree, @ to exit current node:
please input a char:
如果要结束此操作并退出此程序，可以输入0，程序将自动释放所有结点空间：
please choose the mode you want to operate with the binatree:
1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:0
dealing with the last job, to free all nodes
all node have been freed successfully
六、附录：
#include
#include
#include
#define null 0
#define datatype char
typedef struct bintreenode*pbintreenode；
typedef pbintreenode*pbintree；
struct bintreenode
;pbintreenode create_bintree(void);
pbintree create_bintreeroot(void)
{pbintree pbtree;
pbtree=(pbintree)malloc(sizeof(struct bintreenode));