二叉排序树创建，删除，查找操作

binary search tree，中文翻译为二叉搜索树、二叉查找树或者二叉排序树，简称为BST。

二叉搜索树的定义他的定义与树的定义是类似的，也是一个递归的定义：

1、要么是一棵空树

2、如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值

3、其左右子树也是二叉搜索树

BST在数据结构中占有很重要的地位，一些高级树结构都是其的变种，例如AVL树、红黑树等，因此理解BST对于后续树结构的学习有很好的作用。同时利用BST可以进行排序，称为二叉排序，也是很重要的一种思想。相关代码如下:

/** 二叉排序树(BST)创建,删除,查找操作 **/

#include

#include

#define LENGTH 15

typedefintElemType;//数据类型

typedefstructBiTNode{

ElemTypedata;

structBiTNode*lchild;

structBiTNode*rchild;

}BiTNode,*BiTree;

/**

* 向下遍历查找给定结点的相邻节点,以便插入指定节点

*/

voidsearchBiTreeNode(BiTree&root,BiTree&node){

if(root==NULL){

return;

}

if(root->data>node->data){

searchBiTreeNode(root->lchild,node);//递归遍历搜索

if(root->lchild==NULL){

root->lchild=node;

}

}elseif(root->datadata){

searchBiTreeNode(root->rchild,node);

if(root->rchild==NULL){

root->rchild=node;

}

}

}

/**

* 插入指定节点node

*/

voidinsertNode(BiTree&biTree,BiTree&node){

if(biTree==NULL){

biTree=node;

}else{

searchBiTreeNode(biTree,node);

}

}

/**

* 删除指定元素x

*/

voiddeleteNode(BiTree&root,ElemTypex){

if(root==NULL){

return;

}

if(root->data>x){

deleteNode(root->lchild,x);

}elseif(root->data

deleteNode(root->rchild,x);

}else{//查找到了删除节点

if(root->lchild==NULL){//左子树为空

BiTreetempNode=root;

root=root->rchild;

free(tempNode);

}elseif(root->rchild==NULL){//右子树为空

BiTreetempNode=root;

root=root->lchild;

free(tempNode);

}else{//左右子树都不为空

//一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)

BiTreetempNode=root->lchild;

if(tempNode->rchild!=NULL){

tempNode=tempNode->rchild;

}

root->data=tempNode->data;

deleteNode(root->lchild,tempNode->data);

}

}

}

/**

* 查找指定元素x所在的节点

*/

BiTreeBST_Search(BiTree&root,ElemTypex){

if(root==NULL){

returnNULL;

}elseif(root->data>x){

returnBST_Search(root->lchild,x);

}elseif(root->data

returnBST_Search(root->rchild,x);

}else{

returnroot;

}

}

/**

* 二叉排序树创建

*/

voidcreateBiOrderTree(BiTree&biTree,ElemTypearr[]){

for(inti=;i

BiTrees=(BiTree)malloc(sizeof(BiTNode));

s->data=arr[i];

s->lchild=NULL;

s->rchild=NULL;

insertNode(biTree,s);

}

}

/**

* 中序打印二叉树

*/

voidmidSearchBiTreePrint(BiTree&biTree){

if(biTree==NULL){

return;

}

midSearchBiTreePrint(biTree->lchild);

printf("%d ",biTree->data);

midSearchBiTreePrint(biTree->rchild);

}

/**

* 测试程序入口

*/

intmain(){

ElemTypearr[LENGTH]={62,88,58,47,35,73,51,99,37,93,23,27,45,21,12};

BiTreebiTree=NULL;

/** 创建二叉排序树,并测试数据 **/

createBiOrderTree(biTree,arr);

midSearchBiTreePrint(biTree);

printf("\n");

/** 从二叉排序树中删除指定元素,并测试数据 **/

deleteNode(biTree,35);

midSearchBiTreePrint(biTree);

printf("\n");

/** 二叉排序树查找指定元素操作,并测试数据 **/

BiTreesearchNode=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;

}