BST树的定义：
二叉搜索树或者是一颗空树，或者是具有下列性质的二叉树：
1.每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码都互不相同。
2.左子树（如果存在）上所有节点的关键码都小于根节点的关键码
3.右子树（如果存在）上所有节点的关键码都大于根节点的关键码。
4.左子树和右子树也是二叉搜索树
如图下面这棵树就是一颗二叉排序树：
通过上述定义我们不难得出下面这个结论：
如果对一颗二叉搜索树进行中序遍历，可以按照从小到大的顺序，将各节点关键码排列起来，所以也称二叉搜索树为二叉排序树。
首先我们给出二叉搜索树的结构：
typedef int ElemType;
typedef struct BstNode
{
BstNode* leftchild;//左孩子
BstNode* parent;//双亲
BstNode* rightchild;//有孩子
ElemType data;//数据域
}BtNode;
typedef struct
{
BstNode* root;//二叉搜索树的根节点
int cursize;//二叉搜索树的节点数目
}BSTree;
首先，当这个二叉搜索树是一颗空树的时候，程序员需要进行节点的申请，也就是说它所占的空间的申请：
struct BstNode* Buynode()
{
struct BstNode* s = (struct BstNode*)malloc(sizeof(struct BstNode));
if (NULL == s) exit(EXIT_FAILURE);
memset(s, 0, sizeof(*s));
return s;
}
以及对空间（内存）的释放：
void Freenode(BstNode* p)
{
free(p);
}
对二叉搜索树进行初始化：
void Init_Tree(BSTree & mytree)
{
mytree.root = nullptr;//注意这里涉及到一个nullptr和NULL 的区别
mytree.cursize = 0;
}
查找某个数据域为x的节点应该插入到哪个位置：
BstNode* FindValue(BSTree& mytree, ElemType x)
{
BstNode* p = mytree.root;
while (p != NULL && p->data != x)
{
p = p->data > x ? p->leftchild : p->rightchild;
}
return p;//返回数据域为x的这个节点
}
给二叉搜索树中插入一个节点：
void Insert_Tree(BSTree& mytree, ElemType val)
{
BstNode* p = mytree.root;
BstNode* pa = NULL;
while (p != NULL && p->data != val)
{
pa = p;
p = val < p->data ? p->leftchild : p->rightchild;
}
if (p != NULL && p->data == val) return;
p = Buynode();
p->data = val;
p->parent = pa;
if (pa == NULL)
{
mytree.root = p;
}
else
{
if (pa->data > p->data)
{
pa->leftchild = p;
}
else
{
pa->rightchild = p;
}
}
mytree.cursize += 1;
}
二叉搜索树的中序遍历：
void InOrder(BstNode* ptr)
{
if (ptr != NULL)
{
InOrder(ptr->leftchild);
cout << ptr->data<<" ";
InOrder(ptr->rightchild);
}
}
找二叉搜索树的最小值（最左边的值）
BtNode* First(BtNode* ptr)
{
while (ptr != NULL && ptr->leftchild != NULL)
{
ptr = ptr->leftchild;
}
return ptr;
}
找二叉搜索树的最大值（最右边的值）
BtNode* Last(BtNode* ptr)
{
while (ptr != NULL && ptr->rightchild != NULL)
{
ptr = ptr->rightchild;
}
return ptr;
}
找二叉搜索树的某个节点的后继节点:
BstNode* Next(BstNode* ptr)
{
if (ptr == NULL) return NULL;
if (ptr->rightchild != NULL)
{
return First(ptr->rightchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != NULL && pa->leftchild != ptr)
{
ptr = pa;
pa = pa->parent;
}
return pa;
}
}
找二叉搜索树的前驱节点:
BstNode* Prov(BstNode* ptr)
{
if (ptr == NULL) return NULL;
if (ptr->leftchild != NULL)
{
return Last(ptr->leftchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != NULL && pa->rightchild != ptr)
{
ptr = pa;
pa = pa->parent;
}
return pa;
}
}
二叉搜索树的非递归遍历:
void NiceInOrder(BSTree &mytree)
{
for (BstNode* p = First(mytree.root); p != NULL; p = Next(p))
{
cout << p->data << " ";
}
cout << endl;
}
二叉搜索树的非递归逆序遍历:
void ReNiceInOrder(BSTree& mytree)
{
for (BstNode* p = Last(mytree.root); p != NULL; p = Prov(p))
{
cout << p->data << " ";
}
cout << endl;
}
按值删除二叉搜索树中的节点;
bool Remove_value(BSTree& mytree,ElemType val)
{
if (mytree.root == NULL) return false;
BstNode* p = FindValue(mytree, val);
if (p == NULL)return false;
if (p->leftchild != NULL && p->rightchild != NULL)
{
BstNode* tmp = Next(p->rightchild);
p->data = tmp->data;
p = tmp;
}
//leaf
BstNode* pa = p->parent;
BstNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;
if (child != NULL)child->parent = pa;
if (pa == NULL)
{
mytree.root = p;
}
else
{
if (pa->leftchild == p)
{
pa->leftchild = child;
}
if (pa->rightchild == p)
{
pa->rightchild = child;
}
}
Freenode(p);
mytree.cursize -= 1;
return true;
}
主函数代码如下所示：
int main()
{
int arr[] = {
53,17,78,9,45,65,87,23,81,94,88 };
int n = sizeof(arr) / sizeof(arr[0]);
BSTree mytree;
Init_Tree(mytree);
for (int i = 0; i < n; i++)
{
Insert_Tree(mytree,arr[i]);
}
InOrder(mytree.root);
cout << endl;
NiceInOrder(mytree);
cout << endl;
ReNiceInOrder(mytree);
cout << endl;
Remove_value(mytree, 88);
InOrder(mytree.root);
cout << endl;
Destroy_Tree(mytree);
return 0;
}
最终运行结果如下所示：
转载：https://blog.csdn.net/csdn_edition/article/details/112604558
查看评论