7.8、二叉排序树(BST)
二叉排序树又称二叉查找树
- 左子树上所有结点的值都小于根结点的值
- 右子树上所有结点的值都大于根结点的值
- 左子树和右子树又是一颗二叉排序树
左子树的结点值 < 根结点值 < 右子树的结点值
插入的数据的递归实现
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0
//定义一颗二叉排序树
typedef struct BSTNode{
ElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
//插入一个结点的递归实现
boolean BST_Insert(BSTree *T,ElemType k){
if(*T == NULL){
(*T) = (BSTree)malloc(sizeof(BSTNode));
if((*T) == NULL) return false;
(*T)->data = k;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
}else if( (*T)->data == k) {//树中有该值,不能插入相同的值
return false;
}else if((*T)->data < k){
BST_Insert(&(*T)->rchild,k);
}else{
BST_Insert(&(*T)->lchild,k);
}
return true;
}
//访问结点
void Vist(BSTNode *node){
printf("%d , ",node->data);
}
//中序遍历
void InOrder(BSTree T){
if(T != NULL){
InOrder(T->lchild);
Vist(T);
InOrder(T->rchild);
}
}
int main(){
BSTree T = NULL;
BST_Insert(&T,19);
BST_Insert(&T,13);
BST_Insert(&T,50);
BST_Insert(&T,11);
BST_Insert(&T,12);
BST_Insert(&T,26);
BST_Insert(&T,21);
BST_Insert(&T,30);
BST_Insert(&T,66);
BST_Insert(&T,60);
BST_Insert(&T,70);
//中序遍历
printf("中序遍历二叉排序树:");
InOrder(T);
return 0;
}
//结果:
中序遍历二叉排序树:11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 70 ,
非递归实现
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0
//定义一颗二叉排序树
typedef struct BSTNode{
ElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
//插入一个结点的非递归实现
boolean BST_Insert1(BSTree *T,ElemType k){
BSTNode *p = *T;
BSTNode *pre;
if(p == NULL){
*T = (BSTNode*)malloc(sizeof(BSTNode));
if(*T == NULL) return false;
(*T)->data = k;
(*T)->lchild = (*T)->rchild = NULL;
return true;
}
while(p != NULL){
if(p->data == k) return false;
if(p->data < k){
pre = p;
p = p->rchild;
}else{
pre = p;
p = p->lchild;
}
}
BSTNode *q = (BSTNode*)malloc(sizeof(BSTNode));
if(q == NULL) return false;
q->data = k;
q->lchild = q->rchild = NULL;
if(pre->data < k){
pre->rchild = q;
}else{
pre->lchild = q;
}
return true;
}
//访问结点
void Vist(BSTNode *node){
printf("%d , ",node->data);
}
//中序遍历
void InOrder(BSTree T){
if(T != NULL){
InOrder(T->lchild);
Vist(T);
InOrder(T->rchild);
}
}
int main(){
BSTree T = NULL;
BST_Insert1(&T,19);
BST_Insert1(&T,13);
BST_Insert1(&T,50);
BST_Insert1(&T,11);
BST_Insert1(&T,12);
BST_Insert1(&T,26);
BST_Insert1(&T,21);
BST_Insert1(&T,30);
BST_Insert1(&T,66);
BST_Insert1(&T,60);
BST_Insert1(&T,70);
//中序遍历
printf("中序遍历二叉排序树:");
InOrder(T);
return 0;
}
//结果:
中序遍历二叉排序树:11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 70 ,
删除操作
BSTNode *pre = NULL;//需要删除结点的前驱结点
boolean flag = 0;//0表示左子树进入 1表示右子树进入
BSTNode * BSTInOrder(BSTree T){//寻找最子树的中序遍历第一个结点
if(T->lchild == NULL){
return T;
}
return BSTInOrder(T->lchild);
}
//删除结点
boolean BST_DeleteNode(BSTree *T,ElemType e){
if((*T) == NULL) return false;
if((*T)->data == e){
if((*T)->lchild == NULL && (*T)->rchild == NULL){//1.它是叶子结点
(*T) = NULL;
}else if((*T)->lchild == NULL){//2.删除结点的左子树为空
if(flag){
pre->rchild = (*T)->rchild;
}else{
pre->lchild = (*T)->rchild;
}
}else if((*T)->rchild == NULL){//3.删除结点的右子树为空
if(flag){
pre->rchild = (*T)->lchild;
}else{
pre->lchild = (*T)->lchild;
}
}else{//4.如果即有左子树又有右子树
BSTNode *p = BSTInOrder((*T)->rchild);//寻找右子树的最小结点
(*T)->data = p->data;//修改删除结点值
BST_DeleteNode(&(*T)->rchild,p->data);//删除右子树的最小结点
}
return true;
}
pre = *T;
if((*T)->data < e){
flag = 1;
BST_DeleteNode(&(*T)->rchild,e);
}else if((*T)->data > e){
flag = 0;
BST_DeleteNode(&(*T)->lchild,e);
}
}
int main(){
BSTree T = NULL;
BST_Insert1(&T,19);
BST_Insert1(&T,13);
BST_Insert1(&T,50);
BST_Insert1(&T,11);
BST_Insert1(&T,12);
BST_Insert1(&T,26);
BST_Insert1(&T,21);
BST_Insert1(&T,30);
BST_Insert1(&T,66);
BST_Insert1(&T,60);
BST_Insert1(&T,70);
BST_Insert1(&T,68);
//中序遍历
printf("中序遍历二叉排序树:");
InOrder(T);
BST_DeleteNode(&T,50);
//中序遍历
printf("\n删除后中序遍历二叉排序树:");
InOrder(T);
return 0;
}
//结果:
中序遍历二叉排序树:11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 68 , 70 ,
删除后中序遍历二叉排序树:11 , 12 , 13 , 19 , 21 , 26 , 30 , 60 , 66 , 68 , 70 ,
ASL(Average Search Length)
原文地址:http://www.cnblogs.com/shuisanya/p/16849428.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性