创建，删除和查找二进制排序树（BST）的操作

二进制搜索树，二进制翻译树，二进制搜索树或二进制排序树的中文翻译. 简称为BST

一个: 二进制搜索树的定义

他的定义类似于树的定义，也是递归定义:

1. 一棵空树

2. 如果不为空二叉排序树删除，则左子树节点的值小于根节点的值；否则为0. 右子树节点的值大于根节点的值

3. 左右子树也是二叉搜索树

算法简介中的定义:

下图显示了BST的两个示例:

其中二叉排序树删除，（b）中的树非常不平衡（所谓不平衡是值附近的子树之间的高度差相对较大）

BST在数据结构中占据非常重要的位置. 一些高级树结构是它的变体，例如AVL树，红黑树等. 因此，了解BST对树结构的后续学习有很好的效果. 同时，BST可以用于排序，称为二进制排序，这也是一个重要的想法.

相关代码如下:

/** 二叉排序树(BST)创建,删除,查找操作 **/
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 15
typedef int ElemType; //数据类型 

typedef struct BiTNode{
    ElemType  data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree; 
 
/**
 * 向下遍历查找给定结点的相邻节点,以便插入指定节点
 */
void searchBiTreeNode(BiTree &root,BiTree &node){
    if(root == NULL){
        return;
    }
    if(root->data > node->data){
        searchBiTreeNode(root->lchild,node); //递归遍历搜索
        if(root->lchild == NULL){
           root->lchild = node;
        }
    }else if(root->data < node->data){
        searchBiTreeNode(root->rchild,node);
        if(root->rchild == NULL){
           root->rchild = node;
        }
    }
}
/**
 * 插入指定节点node
 */
void insertNode(BiTree &biTree,BiTree &node){
    if(biTree==NULL){
        biTree = node;
    }else{
        searchBiTreeNode(biTree,node);
    }
}
/**
 * 删除指定元素x
 */
void deleteNode(BiTree &root,ElemType x){
    if(root == NULL){
        return;
    }
    if(root->data>x){
        deleteNode(root->lchild,x);
    }else if(root->data<x){
        deleteNode(root->rchild,x);
    }else{ //查找到了删除节点
        if(root->lchild == NULL){ //左子树为空
           BiTree tempNode = root;
           root = root->rchild;
           free(tempNode);
        }else if(root->rchild == NULL){ //右子树为空
           BiTree tempNode = root;
           root = root->lchild;
           free(tempNode);
        }else{  //左右子树都不为空
            //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)
            BiTree tempNode = root->lchild;
            if(tempNode->rchild!=NULL){
                tempNode = tempNode->rchild;
            }
            root->data = tempNode->data;
            deleteNode(root->lchild,tempNode->data);
        }
    }
}
/**
 * 查找指定元素x所在的节点
 */
BiTree BST_Search(BiTree &root,ElemType x){
    if(root == NULL){
        return NULL;
    }else if(root->data>x){
        return BST_Search(root->lchild,x);
    }else if(root->data<x){
        return BST_Search(root->rchild,x);
    }else{
        return root;
    }
}
/**
 * 二叉排序树创建
 */
void createBiOrderTree(BiTree &biTree,ElemType arr[]){
    for(int i=0;i<LENGTH;i++){
        BiTree s = (BiTree)malloc(sizeof(BiTNode));    
        s->data = arr[i];
        s->lchild = NULL;
        s->rchild = NULL;
        insertNode(biTree,s);
    }
}
/**
 * 中序打印二叉树
 */ 
void midSearchBiTreePrint(BiTree &biTree){
    if(biTree == NULL){
        return;
    }
    midSearchBiTreePrint(biTree->lchild);
    printf("%d ",biTree->data);
    midSearchBiTreePrint(biTree->rchild);
}
/**
 * 测试程序入口
 */
int main(){
    ElemType arr[LENGTH] = {62,88,58,47,35,73,51,99,37,93,23,27,45,21,12};
    BiTree biTree = NULL;
    /** 创建二叉排序树,并测试数据 **/
    createBiOrderTree(biTree,arr);
    midSearchBiTreePrint(biTree);
    printf("\n");
    /** 从二叉排序树中删除指定元素,并测试数据 **/
    deleteNode(biTree,35);
    midSearchBiTreePrint(biTree);
    printf("\n");
    /** 二叉排序树查找指定元素操作,并测试数据 **/
    BiTree searchNode = BST_Search(biTree,27);
    if(searchNode == NULL){
        fprintf(stdout,"没有查找到节点\n");
    }else{
        if(searchNode->lchild==NULL && searchNode->rchild==NULL){ //叶子节点
            printf("所查找的节点x=%d是叶子节点\n",searchNode->data);
        }else{ 
            if(searchNode->lchild != NULL){
                printf("x=%d所在节点的左孩子: %d\n",searchNode->data,searchNode->lchild->data);
            }
            if(searchNode->rchild != NULL){
                printf("x=%d所在节点的右孩子: %d\n",searchNode->data,searchNode->rchild->data);
            }
        }
    }
    return 0;
}

运行结果的屏幕截图:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-185231-1.html