/*
* 构造一颗二叉查找树,实现树的插入、删除等基本操作
*
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int count; //记录某个元素出现的次数
int data; //数据
struct node * left;
struct node * right;
}Node,*PNode;
int array[100]; //按序保存遍历后的元素
int k=0; //数组array长度
//初始化一颗二叉排序树
PNode init()
{
PNode p=(PNode)malloc(sizeof(Node));
p->count=0;
p->left=p->right=NULL;
return p;
}
//插入结点
void insert(PNode root ,int data)
{
if(root!=NULL&&root->count==0){//初始化后的第一个元素的count为0
root->data=data;
root->count++;
return;
}
if(data<root->data&&root->left==NULL){
PNode p=(PNode)malloc(sizeof(Node));
p->data=data;
p->count=1;
p->left=p->right=NULL;
root->left=p;
return;
}
if(data>root->data&&root->right==NULL){
PNode p=(PNode)malloc(sizeof(Node));
p->data=data;
p->count=1;
p->left=p->right=NULL;
root->right=p;
return;
}
if(data>root->data)
insert(root->right,data);
else if(data<root->data)
insert(root->left,data);
else{
root->count++;
return;
}
}
//删除结点,删除成功返回1,失败返回0
int deleteNode(PNode* root ,int data)
{
PNode p,q;
//寻找要删除的结点
if(*root==NULL)
return 0;
if((*root)->data==data){//找到要删除的结点
//要删除的结点是叶子结点,直接删除
if((*root)->left==NULL && (*root)->right==NULL){
p=*root;
*root=NULL;
free(p);
return 1;
}
//要删除的结点有左子树或者右子树,此时直接用左子树或右子树代替删除的结点
if((*root)->left==NULL || (*root)->right==NULL){
p=*root;
*root=(*root)->left==NULL?(*root)->right:(*root)->left;
p->left=p->right=NULL;
free(p);
return 1;
}
//要删除的结点有左子树和右子树。删除的结点的左子树代替删除的结点,然后
//一直查找删除的结点的左子树的右子树,直到出现为空。把删除结点的右子树插入
if((*root)->left && (*root)->right){
p=*root;
*root=(*root)->left;
q=*root;
while(q->right)
q=q->right;
q->right=p->right;
p->left=p->right=NULL;
free(p);
return 1;
}
}else if((*root)->data>data){
deleteNode(&(*root)->left,data);
}else
deleteNode(&(*root)->right,data);
return 0;
}
//中序遍历
void search_middle(PNode root)
{
int i=0;
if(root==NULL)
return;
search_middle(root->left);
for(;i<root->count;i++)
array[k++]=root->data;
search_middle(root->right);
}
//先序遍历
void search_prior(PNode root)
{
int i=0;
if(root==NULL)
return;
for(;i<root->count;i++)
array[k++]=root->data;
search_prior(root->left);
search_prior(root->right);
}
//后序遍历
void search_last(PNode root)
{
int i=0;
if(root==NULL)
return;
search_prior(root->left);
search_prior(root->right);
for(;i<root->count;i++)
array[k++]=root->data;
}
//求树的高度
int tree_height(PNode root)
{
int h1,h2;
if(root!=NULL&&root->count==0)
return 0;
if(root==NULL)
return 0;
h1=1+tree_height(root->left);
h2=1+tree_height(root->right);
return h1>h2?h1:h2;
}
void main()
{
int a[20];
int *p=a;
PNode pnode=init();
int i,n,deleteElement;
//读入要排序的数字个数和数字
printf("please input n(n<20):\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter an Integer number:\n");
scanf("%d",p++);
}
//把待排序的元素插入二叉查找树中
for(i=0;i<n;i++){
insert(pnode,*(a+i));
}
search_middle(pnode);
printf("\n树的高度%d\n",tree_height(pnode));
//输出排序后的元素序列
for(i=0;i<k;i++)
printf("%-5d",array[i]);
printf("\n");
//删除结点
printf("请输入要删除的结点:\n");
scanf("%d",&deleteElement);
deleteNode(&pnode,deleteElement);
k=0;
search_middle(pnode);
printf("\n删除后:树的高度%d\n",tree_height(pnode));
//输出排序后的元素序列
for(i=0;i<k;i++)
printf("%-5d",array[i]);
printf("\n");
free(pnode);
}
分享到:
相关推荐
二叉查找树的C语言实现,实现功能:插入、删除、查找。
二叉排序树的c语言实现,创建、插入、删除、查找……
C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好
c语言实现的用动态规划实现最优二叉查找树,,,具体参见附件,2.txt中的内容为: 5 0.15 0.10 0.05 0.10 0.20
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
读一个文件,文件中包含2000个以上英文名字 利用二叉数进行查找,在查找过程中避免 冲突的代码
红黑树和二叉搜索树的C语言实现及性能比较,大学算法导论实验
二叉查找树的编程与实现 C语言.pdf 二叉查找树的编程与实现 C语言.pdf 二叉查找树的编程与实现 C语言.pdf 二叉查找树的编程与实现 C语言.pdf 二叉查找树的编程与实现 C语言.pdf 二叉查找树的编程与实现 C语言.pdf ...
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
findwords查找文件是否有某单词,这是一个二叉查找树的练习
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
该源码使用C实现了最二叉查找树的基本操作,比如删除、查找,插入等。
/*用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
二叉排序树用C语言实现,内含本人写的报告文档,仅供参考
C语言实现二叉查找树(二插排序树)的基本操作。
大量使用 递归 以及面向对象形式 支持C语言下复合类型 其中的比较以及遍历 均使用回调方式 留给用户最大空间 另由于C语言不支持泛型 好在还有个void* 无类型指针 合理使用 但比较以及遍历时不知其具体类型 故而采用...
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
主要介绍了一个c语言版的二叉查找树实现,二叉查找树,支持的操作包括:SERACH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE,大家参考使用吧
运用c语言,贪心算法构造最优二叉查找树。
可以利用二叉排序数按姓名排序,排序后可实现查找,删除,插入,等操作