实验三 二叉树的建立和应用
1、实验目的
（1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；
（2）重点掌握二叉树的生成、遍历及求叶子结点算法；
（3）掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。
2、实验内容
1）按照已知二叉树，从键盘读入节点字符，建立二叉树（例如，ABD#G###CE##FH###）2）分别采用先序、中序、后序及层次遍历该二叉树，分别输出遍历结果。
3）应用：求出该数的叶子结点数。
3、实验步骤
（1）仔细分析实验内容，给出其算法和流程图；
（2）用C语言实现该算法；
（3）给出测试数据，并分析其结果；
（4）在实验报告册上写出实验过程。
4、测试数据 A
1）所创建的树如右图所示：
2）遍历结果： B C 先序序列： ABDGCEFH
中序序列： DGBAECHF
后序序列： GDBEHFCA D E F 层次遍历：ABCDEFGH
3）叶子结点数：3
5、树的结点结构定义如下： G H typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
6、实验报告要求
实验三 二叉树的建立和应用
姓名： 班级： 学号： 日期： 实验目的：
实验内容：
基本思想、原理和算法描述：
源程序：
运行结果分析：
实验总结：
第二篇：GJQ实验3 排序二叉树的建立和查找
《软件技术基础》实验指导书
实验三 排序二叉树的建立和查找
一、实验题目：排序二叉树的建立和查找
二、实验目的：掌握非线性数据结构的描述方法
三、实验内容：
（1）附录中是用链式结构实现二叉树的建立、查询和打印的源程序。请将他们输入计算机，编译、连接并运行。
（2）读懂上述程序，并编写删除一个结点的子函数。
四、实验报告要求：
《软件技术基础》实验报告
实验名称：排序二叉树的建立和查找
班级： 学号： 姓名：
实验目的：掌握非线性数据结构的描述方法
实验内容：
（1）附录中是用链式结构实现二叉树的建立、查询和打印的源程序。请将他们输入计算机，编译、连接并运行。
（2）读懂上述程序，并编写删除一个结点的子函数。
实验原理：写出删除排序二叉树中一个结点的算法（形式语言）。
实验步骤：写出调试、查找程序中问题的思路和步骤。
实验结果：写出删除排序二叉树中一个结点的子程序。
附录：二叉树的建立、查询、打印和遍历的源程序：
#include<iostream.h>
#include<stdio.h>
//******************************************
//define the structure of an element of a tree
//******************************************
struct tree {
char info;
struct tree *left,*right;
};
//******************************************
//explanation the functions
//******************************************
struct tree *create_btree(struct tree *root,struct tree *r,char info);
struct tree *search_btree(struct tree *root,char key);
void print_btree(struct tree *r,int l);
void PreOrder(struct tree *T); //先序递归遍历二叉树
void InOrder(struct tree *T); //中序递归遍历二叉树
void PostOrder(struct tree *T);
//******************************************
// the main function
//******************************************
void main()
{ char s[100], c ;
struct tree *root=0, *p;
printf("Input a letter for Creating the Binary_Tree ( Directly press <Enter> to stop ):\n");
do {
printf("Input a letter: ");
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btree(root,root,*s);
} while (*s) ;
while ( c!='!')
{
print_btree(root,0);
printf("Enter a character to find( '!' to stop ):");
scanf("%s",&c);
printf("\n");
p=search_btree(root,c);
printf("\n");
}
printf("\n先序遍历结果：");
PreOrder(root); //先序递归遍历二叉树
printf("\n中序遍历结果：");
InOrder(root);
printf("\n后序遍历结果："); //中序递归遍历二叉树
PostOrder(root);
printf("\n");
} /* Btree.C 结束 */
struct tree *create_btree(struct tree *root,struct tree *r,char info)
{ if (r ==0 )
{ r=new (struct tree);
if ( r == 0)
{ printf("Out of memory\n"); return 0 ; }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
}
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
//******************************************
//tree *search_btree(struct tree *root,char key)
//******************************************
struct tree *search_btree(struct tree *p,char key)
{ struct tree *root;
root=p;
if (!root)
{ printf("Empty btree\n"); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf("Search Failure\n");
return 0;
}
} /* while(root->info!=key) */
if (root !=0)
printf("Successful search\n key=%c\n",root->info);
return root ;
} /* *search_btree(root,key) */
//************************************
// print_btree
//************************************
void print_btree(struct tree *r,int l)
{ int i;
if (r == 0) return ;
print_btree(r->left,l+1);
for(i=0;i<l;i++) printf(" ");
printf("%c\n",r->info);
print_btree(r->right,l+1);
}
void PreOrder(struct tree *T)
{
if(T)
{
printf("%c",T->info); //访问结点
PreOrder(T->left); //遍历左子树
PreOrder(T->right); //遍历右子树
}
}
void InOrder(struct tree *T)
{if(T)
{
InOrder(T->left); //遍历左子树
printf("%c",T->info); //访问结点
InOrder(T->right); //遍历右子树
}
}
void PostOrder(struct tree *T)
{
if(T)
{
PostOrder(T->left); //遍历左子树
PostOrder(T->right); //访问结点
printf("%c",T->info); //遍历右子树
}
}