BST（二叉搜索树）

BST（Binary Search Tree）目的是为了提高查找的性能，其查找在平均和最坏的情况下都是logn级别，接近二分查找。

其特点是：每个节点的值大于其任意左侧子节点的值，小于其任意右节点的值。

介绍三个最基本的操作：

预备操作：

typedef struct node{int value;char key;int Index;struct node *left;struct node *right;
}BSTNode,*PBSTNode;

1、查找

//找到指定的键值
PBSTNode  Get(PBSTNode root,char Key)
{if(!root)return NULL;if(Key == root->key)return root;else if(Key < root->key)return Get(root->left,Key);elsereturn Get(root->right,Key);
}

2、插入节点操作。

//插入操作
//------1.BSTree为空-------------------------
//------2.BSTree已经有该键，那么只需要更新
//------3.正常操作---------------------------
void BSTInsert(PBSTNode *root,char Key,int Value)
{//树开始是空值if(!(*root)){(*root) = (PBSTNode)malloc(sizeof(BSTNode));(*root)->Index = 0;(*root)->key = Key;(*root)->value = Value;(*root)->left = (*root)->right = NULL;return;}PBSTNode Temp = (PBSTNode)malloc(sizeof(BSTNode));PBSTNode des = Get((*root),Key);//已经存在更新键值if(des != NULL){des->value = Value;return;}//正常的情况下：PBSTNode Go = (*root);while(Go){if(Go->key > Key){if(!Go->left){Temp->key = Key;Temp->value = Value;Temp->left = Temp->right = NULL;Go->left = Temp;//序号没有实现更新。return;}elseGo = Go->left;}//end of > situationelse{if(!Go->right){Temp->key = Key;Temp->value = Value;Temp->left = Temp->right = NULL;Go->right = Temp;return;}elseGo = Go->right;}}
}

我们可以利用插入节点这个函数来进行BST树的创建：

//利用插入函数来创建BSTree
PBSTNode CreateBSTree(char *data,int n)
{PBSTNode Root = NULL;if(n == 0)Root =  NULL;else{for(int i = 0;i < n;i++)BSTInsert(&Root,data[i],i);}return Root;
}

3、删除

//删除操作:
//-------1、未查找到----------------------------------------------------------------------
//-------2、删除的节点只有一个子节点，直接将其删除，并让其父节点指向其唯一的那个子节点即可
//-------3、删除的节点是叶子节点，直接删除就行
//-------4、删除的结点有两个子节点，则有两种方案可供选择：
//-------------------------------------------------------1)选取其右孩子的最小结点来顶替其位置
//-------------------------------------------------------2)选取其左孩子的最大节点来顶替其位置
//返回值-1表示删除非法。1代表成功。
int Delete(PBSTNode * Root,char key)
{//删除头结点if((*Root)->key == key){if(!(*Root)->left && (*Root)->right){(*Root) = (*Root)->right;free((*Root));return 1;}else if((*Root)->left && !(*Root)->right){(*Root) = (*Root)->left;free((*Root));return 1;}PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));Min = (*Root)->right;PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));ParentMin = (*Root);while(Min->left){ParentMin = Min;Min = Min->left;}ParentMin->left = Min->right;Min->left = (*Root)->left;Min->right = (*Root)->right;(*Root) = Min;return 1;}//因为需要找到删除节点的父节点，所以不能调用Get函数PBSTNode Parent = (*Root);PBSTNode Go = (*Root);while(Go){if(Go->key == key)break;else if(Go->key > key){Parent = Go;Go = Go->left;}else{Parent = Go;Go = Go->right;}}//Situation 1if(!Go)return -1;//Situation 2if(!Go->left && Go->right){if(Parent->left == Go)Parent->left = Go->right;elseParent->right = Go->right;free(Go);return 1;}else if(Go->left && !Go->right){if(Parent->left == Go)Parent->left = Go->left;elseParent->right = Go->left;free(Go);return 1;}//Situation 3else if(!Go->left && !Go->right){if(Parent->left == Go)Parent->left = NULL;elseParent->right = NULL;free(Go);return 1;}//Situation 4//Choose Solution 1: Min right sonelse{PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));Min = Go->right;PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));ParentMin = Go;while(Min->left){ParentMin = Min;Min = Min->left;}if(Parent->left == Go){Parent->left = Min;ParentMin->left = Min->right;Min->left = Go->left;Min->right = Go->right;}else{Parent->right = Min;ParentMin->left = Min->right;Min->left = Go->left;Min->right = Go->right;}}//end of elsereturn 1;
}

删除由于情况比较多所以复杂一点。

4、返回范围内的所有数据

//范围查找，找出某个范围内的全部数据,返回一个动态链表
void  GetDatasFromField(PBSTNode Root,char LowKey,char MaxKey,PBSTNode *Result,int *count)
{if(!Root)return;if(Root->key > LowKey && Root->key < MaxKey){Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));Result[(*count)]->key = Root->key;Result[(*count)]->value = Root->value;  (*count)++;//这情况表示左右都有可能有符合范围的数据GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);}else if(Root->key < LowKey){if(Root->key == LowKey){Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));Result[(*count)]->key = Root->key;Result[(*count)]->value = Root->value;(*count)++;}//表明数据在右边GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);}else{if(Root->key == MaxKey){Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));Result[(*count)]->key = Root->key;Result[(*count)]->value = Root->value;(*count)++;}//表明数据在左边GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);}
}