binary search tree，中文翻譯為二叉搜索樹、二叉查找樹或者二叉排序樹。簡稱為BST
一：二叉搜索樹的定義
他的定義與樹的定義是類似的，也是一個遞歸的定義：
1、要麼是一棵空樹
2、如果不為空，那麼其左子樹節點的值都小於根節點的值；右子樹節點的值都大於根節點的值
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;
}
運行結果截圖:
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
