实验四 二叉树的操作.doc

实验四 二叉树的操作2007-11-12一、 实验目的 理解并熟悉掌握创建二叉树和实现二叉树的三种遍历二、 实验内容 创建二叉树和实现二叉树的三种遍历a. 根据提示输入字符型数据创建二叉树，输入值为所有字符型数据b. 输出为遍历后的每个结点的值的顺序c. 创建二叉树并能实现二叉树的先序、中序、后序遍历d. 如果输入数据为：a b c输出结果为：a b c b a c b c a 程序流程：main()clrscr()createtree()preorder()inorder()postorder三、 源程序#include stdlib.h/*引入头文件*/struct tnode/*定义二叉树存储结构*/char data; struct tnode*lchild; struct tnode*rchild;struct tnode tree;/*定义二叉树指针*/void createtree(struct tnode*t)/*创建函数*/struct tnode*p=t;/*把二叉树指针给p*/ char check; if(p-lchild=NULL|p-rchild=NULL) /*判断左右子树是否为空*/ printf(please enter the data:); /*输入根结点数据*/ scanf(%c,&(p-data); getchar(); if(p-lchild=NULL) printf(%c leftchild is null.Add? y/nn,p-data); /*左子树空，询问是否创建*/ scanf(%c,&check); getchar(); if(check=y) struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode); /*开辟空间*/ q-lchild=NULL; q-rchild=NULL; p-lchild=q; createtree(q); if(p-rchild=NULL) printf(%c rightchild is NULL.Add? y/nn,p-data); /*右子树空，询问是否创建*/ scanf(%c,&check); getchar(); if(check=y) struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode); /*开辟空间*/ q-lchild=NULL; q-rchild=NULL; p-rchild=q; /*连到二叉树上*/ createtree(q); void preorder(struct tnode*t)/*先序遍历函数*/void inorder(struct tnode*t) /*中序遍历函数*/void postorder(struct tnode*t) /*后序遍历函数*/void main() clrscr();/*清屏函数*/ tree.lchild=NULL;/*左子树*/ tree.rchild=NULL;/*右子树*/ createtree(&tree); /*创建二叉树*/ preorder(&tree);/*先序遍历*/ printf(n); inorder(&tree);/*中序遍历*/ printf(n); postorder(&tree);/*后序遍历*/四、 使用说明 程序运行：1、 先输入根结点数据，例如：a2、 输入y或n判断是否创建左子树。输入y然后输入左子树数据3、 输入y或n判断是否创建右子树。输入y然后输入右子树数据4、 按回车可查看遍历结果并退出程序。五、 测试结果 运行程序，屏幕提示：please enter the data:a /*首先输入根结点，为a*/a leftchild is null.add?y/n /*询问是否输入a结点的左结点*/y /*输入*/please enter the data:b /*输入结点a的左结点，为b*/b leftchild is null.add?y/n /*询问是否输入b结点的左结点*/n /*不输入*/b rightchild is null.add?y/n /*询问是否输入b结点的右结点*/n /*不输入*/a rightchild is null.add?y/n /*询问是否输入a结点的右结点*/y /*输入*/please enter the data:c /*输入结点a的右结点，为c*/c leftchild is null.add?y/n /*询问是否输入c结点的左结点*/n /*不输入*/c rightchild is null.add?y/n /*询问是否输入c结点的右结点*/n /*不输入*/程序退出，显示结果应为： a b c /*先序*/ b a c /*中序*/ b c a /*后序*/ 要求：1 写出下面三个过程或函数的代码。void preorder(struct tnode*t)/*先序