【数据结构】二叉排序树(BST)_综合

二叉排序树(Binary Sort Tree)又称二叉查找树、二叉搜索树。它或者是一颗空树，或者具有下列性质的二叉树：

●若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
●若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
●它的左、右子树也分别为二叉排序树；
如图所示：

BST树结构：

结点结构：

typedef struct BstNode
{
   BstNode *leftchild;
   BstNode *rightchild;
   keyType key;
   BstNode *parent;
}BstNode;

带头结点的BST树结构：

typedef struct
{
   BstNode *head;
   int cursize;
}Bstree;

完整代码如下：

基本结构：

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef int keyType;
typedef struct BstNode
{BstNode *leftchild;BstNode *rightchild;keyType key;BstNode *parent;
}BstNode;//结点结构typedef struct 
{BstNode *head;int cursize;
}Bstree;//带头结点的BST树

购买结点并且初始化：

BstNode *BuyNode(BstNode *ptr = NULL)//购买一个结点
{BstNode *p = (BstNode*)malloc(sizeof(BstNode));if(p == NULL){exit(1);}memset(p,0,sizeof(BstNode));p->parent = ptr;return p;
}
void InitBstree(Bstree &myt)//初始化BST树
{myt.head = BuyNode();myt.cursize = 0;
}

查找：

BstNode *Findvalue(Bstree &myt,keyType kx)//查找结点的非递归方式
{BstNode *pa = myt.head->parent;while(pa != NULL && pa->key != kx){pa = pa->key > kx ? pa->leftchild : pa->rightchild;}if(pa == NULL){return false;}return pa;
}BstNode *Searchvalue(BstNode *pst,keyType kx)//递归方式查找结点
{if(pst->key == kx || pst == NULL){return pst;}if(pst->key < kx){Searchvalue(pst->rightchild,kx);}else{Searchvalue(pst->leftchild,kx);}
}BstNode *Search(Bstree &myt,keyType kx)
{return Searchvalue(myt.head->parent,kx);
}

查找子树中的最大值与最小值：

BstNode *First(BstNode *pst)//查找最小结点
{while(pst != NULL && pst->leftchild != NULL){pst = pst->leftchild;}return pst;
}BstNode *Last(BstNode *pst)//查找最大值
{while(pst != NULL && pst->rightchild != NULL){pst = pst->rightchild;}return pst;
}

查找一个结点的直接后继与直接前驱：

BstNode *Next(Bstree &myt,BstNode *pst)//找pst的直接后继
{if(pst == NULL || pst == myt.head)//pst是头结点的情况{return NULL;}if(pst ->rightchild != NULL)//有右分支，则直接后继一定是右分支的最小值{return First(pst->rightchild);}BstNode *pa = pst->parent;while(pa != myt.head && pa->leftchild != pst)//有左孩子的情况，因为左孩子一定要比pst小，要找下一个的最大值，只能向上查找；{pst = pa;pa = pa->parent;}if(pa == myt.head){pa = NULL;}return pa;
}BstNode *Pre(Bstree &myt,BstNode *pst)//找直接前驱
{if(pst == NULL || pst == myt.head)//pst是头结点的情况{return NULL;}if(pst->leftchild != NULL)//找直接前继，是找比当前结点小的值，所有在有左孩子的情况下，只需在当前结点的左分支找最大值；{return Last(pst->leftchild);}BstNode *pa = pst->parent;while(pa != myt.head && pa->rightchild != pst){pst = pa;pa = pa->parent;}if(pa == myt.head)//pst是最小值的情况{pa = NULL;}return pa;
}

排序：

void NiceInOrder(Bstree &myt)//从小到大排序,相当于中序遍历
{BstNode *pa = myt.head->parent;for(pa = First(pa);pa != NULL;pa = Next(myt,pa)){cout << pa->key << " ";}cout << endl;
}void ResNiceOrder(Bstree &myt)//从大到小排序，逆序
{BstNode *pa = myt.head->parent;for(pa = Last(pa);pa != NULL;pa = Pre(myt,pa)){cout << pa->key << " ";}cout << endl;
}

插入与删除结点：

bool InsertBST(Bstree &myt,keyType kx)//插入结点
{BstNode *pa = myt.head;//BST树头结点BstNode *p = myt.head->parent;//BST的root结点while(p != NULL && kx != p->key)//使p指向要插入的位置{pa = p;p = p->key > kx ? p->leftchild : p->rightchild;}if(p != NULL)//找到相同的值，无法进行插入{return false;}p = BuyNode(pa);p->key = kx;if(pa == myt.head)//插入根节点{myt.head->parent = p;myt.head->leftchild = p;myt.head->rightchild = p;}else{if(pa->key > kx)//插到左孩子{pa->leftchild = p;if(myt.head->leftchild->key < kx){myt.head->leftchild = p;//重置头结点中的leftchild的指向，也就是最小值的指向；}}else//插到右孩子的位置{pa->rightchild = p;if(myt.head->rightchild->key > kx){myt.head->rightchild = p;//重置头结点中的rightchild的指向，也就是最大值的指向；}}}myt.cursize += 1;return true;
}bool RemoveBST(Bstree &myt,keyType kx)//删除结点{BstNode *pa = myt.head;BstNode *p = myt.head->parent;while(p != NULL && p->key != kx){pa = p;p = p->key > kx ? p->leftchild : p->rightchild;}if(p == NULL)//未找到结点为kx的情况{return false;}if(p->leftchild != NULL && p->rightchild != NULL)//有双支的情况{BstNode *ptr = Next(myt,p->rightchild);p->key = ptr->key;p = ptr;}BstNode *child = p->leftchild != NULL ? p->leftchild : p->rightchild;//判断是有左枝还是右枝的情况if(child != NULL){child->parent = pa;}//单分枝非叶子结点,连接父结点if(pa == myt.head)//删除根节点的情况{myt.head->parent = child;}else//判断连接到左枝还是右枝{if(p == pa->leftchild){pa->leftchild = child;}else{pa->rightchild = child;}}}

树的最小深度：

int MinDepth(BstNode* pa){if(pa == NULL){return 0;}if(pa->leftchild == NULL)//左子树为NULL的情况{return MinDepth(pa->rightchild) + 1;}if(pa->rightchild == NULL)//右子树为NULL的情况{return MinDepth(pa->leftchild) + 1;}int left = MinDepth(pa->leftchild);//存在左右子树的情况int right = MinDepth(pa->rightchild);return (left > right ) ? (right + 1) : (left + 1);}int run(Bstree &myt)//最小深度，有深度优先的方法{BstNode *pa = myt.head->parent;return MinDepth(pa);}

主函数：

 int main(){int arr[] = {84,5,72,4,8,20,957};int len = sizeof(arr)/sizeof(arr[0]);Bstree myt;InitBstree(myt);for(int i = 0;i < len;i++){InsertBST(myt,arr[i]);}NiceInOrder(myt);ResNiceOrder(myt);int kx;while(cin>>kx,kx != -1){RemoveBST(myt,kx);NiceInOrder(myt);}printf("%d\n",run(myt));}

结果截图：