二叉排序树BST 原则就是小的话接左边,大的话接右边,必须说的是效率太低主要是刚开始理解错了不需要再写什么Creat函数的,直接搜着插着就能进行
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NULL 0
typedef int ElemType;
typedef int Status;
typedef int KepType;
typedef struct BiTNode{
ElemType data;
struct BiTNode * lchild, * rchild;
}BiTNode, * BiTree;
Status SearchBST(BiTree T, int key, BiTree f, BiTree &p){
//此次查找是为Insert做准备
//在根指针T所指的二叉树中递归地查找其关键字等于key的数据元素,若成功,
// 则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访问的
//最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL
if(!T)
{
p=f;
return FALSE;
} //查找不成功
else if (key==T->data)
{
p=T;
return TRUE;
} //查找成功
else if(key < T->data) return SearchBST(T->lchild, key, T, p); //在左子树中继续查找
else if(key > T->data) return SearchBST(T->rchild, key, T, p); //在右子树中继续查找
}
Status InsertBST(BiTree &T, ElemType e){
//当二叉排序树T中不存在关键字等于e的数据元素时,插入e并返回TRUE,否则返回FALSE
BiTree p=NULL;
if(!SearchBST(T, e, NULL, p))
{
BiTree s;
s=(BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
if(!p) T = s; //被插结点*s为新的根结点
else if(e < p->data) p->lchild = s;
else if(e > p->data) p->rchild = s;
return TRUE;
}
else return FALSE;
}
Status DeleteBST(BiTree &p){
//从二叉排序树中删除结点p,并重接它的左或右子树
BiTree q;
if(!p->rchild) //右子树空则只用接左子树
{
q=p;
p=p->lchild;
free(q);
}
else if(!p->lchild) //左子树空则只用接右子树
{
q=p;
p=p->rchild;
free(q);
}
else //左右均不空
{
BiTree s;
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;
}
return OK;
}
Status InOrderTraverse(BiTree T) //中序递归遍历
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
return OK;
}
int main()
{
BiTree T=NULL;
int e;
int num;
printf("输入初始的结点数:\n");
scanf("%d", &num);
while(num--)
{
scanf("%d",&e);
InsertBST(T,e);
}
InOrderTraverse(T);
printf("\n");
printf("输入要插入的数据个数:\n");
scanf("%d", &num);
while(num--)
{
scanf("%d", &e);
InsertBST(T,e);
}
InOrderTraverse(T);
printf("\n");
DeleteBST(T);
InOrderTraverse(T);
printf("\n");
return 0;
}
分享到:
相关推荐
二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造实验报告
其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右子树非空,则右子树上所有结点的值均大于根结点的值;3.左、右子树本身又各...
当二叉排序树BST中不存在结点值等于e时,插入e并返回0,否则返回-1. ③int deleteBST(BTree *T, char key);删除 若二叉排序树T中存在结点值等于key时,则删除该数据元素,并返回0;否则返回-1。 ④BTree searchBST...
输入一组关键字,排列成一棵二叉排序树,最后中序遍历其结果
③平衡的二叉排序树指满足BST性质的平衡二叉树。 ④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下,n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树高度约为lgn,AVL树是最接近最优...
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树...
BST(二叉排序树):二叉检索树类定义、二叉检索树的实现, 二叉检索树结点的删除。
9.2 给定一组关键字K={4,5,2,3,6,1},试按二叉排序树生成规则画出这棵二叉排序树,并说明用这组关键字以不同的次序输入后建立起来的二叉排序树的形态是否相同?当以中序遍历这些二叉排序树时,其遍历结果是否...
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个结点最多有两个子结点,称为左子结点和右子结点。 对于树中的每个结点,其左子树中的所有结点的值都小于该结点的值,而右子树中的...
基于BST(二叉排序树)的城市信息管理系统 .pdf
二叉排序树(BST)又称二叉查找树、二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于根结点的值; 2.若...
(1)编写二叉排序树的基本操作函数。 ①查找结点函数 SearchNode(TREE *tree,int key,TREE **pkpt,TREE **kpt) ②二叉排序树插入函数 InsertNode(TREE **TREE,int key) ③二叉排序树删除函数 DeleteNode...
基于BST(二叉排序树)的城市信息管理.pdf
基于BST(二叉排序树)的城市信息管理.doc
二叉排序树的非递归查找算法二叉排序树的插入算法int BST_Insert(BiTree &T, KeyType k){
这里是自己编的二叉排序树c语言的程序,有助于理解二叉树,采用递归的方法
二叉查找树的查找、插入、删除、建立操作
数据结构课程实验:二叉排序树课程实验示例
二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。 一般地,除了key和位置数据之外,每个结点...