C语言实现二叉排序树的创建、查找、遍历、打印树表、插入、删除。 程序拥有良好的输入输出界面。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef int KeyType;
typedef int Status;
typedef struct{
KeyType key; /*关键字域*/
}SElemType;
typedef struct BitNode{
SElemType data; /*存储空间基址,建表时按实际长度分配,0号单元留空*/
struct BitNode *lchild,*rchild;
}BitNode,* BiTree;
/*二叉排序树的插入*/
Status InsertBST(BiTree &T,KeyType key){
BiTree s;
if(!T){
s=(BiTree)malloc(sizeof(BitNode));
s->data.key=key;
s->lchild=s->rchild=NULL;
T=s;
}
else if LT(key,T->data.key)
InsertBST(T->lchild,key);
else InsertBST(T->rchild,key);
return TRUE;
}
/*创建二叉排序树*/
void CreateBST(BiTree &T){
KeyType key;
T=NULL;
scanf("%d",&key);
while(key!=0){
InsertBST(T,key);
scanf("%d",&key);
}
}
/*中序遍历*/
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%4d",T->data.key);
InOrderTraverse(T->rchild);
}
}
/*打印二叉树*/
Status PrintTree(BiTree T,int n){
if(T==NULL)return FALSE;
PrintTree(T->rchild,n+1);
for(int i=0;i<n;i++)
printf(" ");
printf("%d\n",T->data.key);
PrintTree(T->lchild,n+1);
return TRUE;
}
/*二叉排序树的查找*/
BiTree SearchBST(BiTree T,KeyType key){
if(!T){printf("Can not find!!\n");return T;}
else if EQ(key,T->data.key){return T;}
else if LT(key,T->data.key) return SearchBST(T->lchild,key);
else return SearchBST(T->rchild,key);
}
/*二叉排序树的删除*/
Status Delete(BiTree &p){
BiTree q,s;
if(!p->rchild){
q=p;
p=p->lchild;
free(q);
}
else if(!p->lchild){
q=p;
p=p->rchild;
free(q);
}
else{
q=p;
s=p->lchild;
while(s->rchild){q=s;s=s->rchild;}
p->data=s->data;
if(q!=p) q->rchild=s->lchild;
else q->lchild=s->lchild;
delete s;
}
return TRUE;
}
Status DeleteBST(BiTree &T,KeyType key){
if(!T)return FALSE;
else{
if (EQ(key,T->data.key))return Delete(T);
else
if(LT(key,T->data.key))return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
}
}
void main() {
BiTree b1,b2;
KeyType key;
int t;
begin:
printf("1:创建二叉排序树\n");
printf("2:打印排序树\n");
printf("3:查找结点\n");
printf("4:中序遍历\n");
printf("5:插入结点\n");
printf("6:删除结点\n");
printf("0:退出\n");
printf("请选择要进行的操作:");
scanf("%d",&t);
switch(t){
case 1:
printf("Input every key(0 to quit):");
CreateBST(b1);
PrintTree(b1,0);//排序树的结果打印出来
goto begin;
case 2:PrintTree(b1,0);goto begin;
case 3:
printf("Input the key to search:");
scanf("%d",&key);
if(key!=0){
b2=SearchBST(b1,key);//把 key 为根的子树打印出来
PrintTree(b2,0);
printf("\nThe root is the key to search!!\n\n");
}
el
学号:E30814013 实验日期:2010-6-12 专业:网络工程 教师签字: 姓名:张芸 成绩 实 验 报 告 实验目的:实现顺序查找,折半查找,二叉排序树,哈希表实验原理:顺序...
课程设计 课程名称 题目名称 学生学院 专业班级 学号 数据结构课程实验 二叉排序树的实现 应用数学学院 学生姓名 指导教师 2013 年 12 月 25 日 一、 实现二叉...
数据结构C语言实现二叉树三种遍历_理学_高等教育_教育专区。用三种遍历算法遍历...实验课题一 实验课题一:将下图中的二叉树用二叉链表表示: A B D F G E H...
河北工业大学-数据结构实验报告-基于二叉排序树的商品信息查询算法的设计与实现_工学_高等教育_教育专区。实验四:基于二叉排序树的商品信息查询算法的设计与实现 一...
二叉排序树节点的插入和删除实验设计报告 二叉排序树节点的插入和删除实验设计报告...case…结构,有选 择性的进行功能的实现。 4 算法描述: 算法描述:二叉排序树...
数据结构C语言实现二叉树... 4页 1下载券喜欢此文档的还喜欢 数据结构实验二叉排序树... 2页 1下载券 二叉排序树的相关操作(C... 12页 1下载券 数据...
北邮数据结构实验—二叉排序树_计算机软件及应用_IT/计算机_专业资料。北京邮电...这种基本数据操作有 了较深刻的认识.同时在二叉排序树的删除操作的代码编写时,...
北京林业大学 12 学年—13 学年第 1 学期数据结构实验报告书专 姓业:自动化 ... 实验内容:用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树...
数据结构实验报告二叉排序树_工学_高等教育_教育专区。西工大数据结构实验...二叉树有了更进一步的熟悉和了解, 可以熟练编写二叉排 序树, 熟悉了二叉排序树...
热门文档