数据结构----二叉搜索树（C语言）
程序员文章站
2022-06-05 16:52:18
...
关于数据结构二叉树的概念及操作可参看博客：
https://blog.csdn.net/eric_qiushui/article/details/80261271
一、二叉搜索树
二叉搜索树又称为二叉排序树，它或者是一颗空树，或者时具有以下性质的二叉树
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二、二叉搜索树的操作
最难的部分还是要数二叉搜索树的删除操作
- BinarySearchTree.h
// BinarySearchTree.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
typedef int DataType;
typedef struct BSTreeNode
{
struct BSTreeNode *_pLeft;
struct BSTreeNode *_pRight;
DataType _data;
}BSTNode, *PBSTN;
// 初始化二叉搜索树
void InitBSTree(PBSTN* pRoot);
// 插入值为data的元素
void InsertBSTree(PBSTN* pRoot, DataType data);
// 删除值为data的结点
void DeleteBSTree(PBSTN* pRoot, DataType data);
// 在二叉搜索树中查找值为data的结点
PBSTN FindBSTree(PBSTN pRoot, DataType data);
// 中序遍历二叉搜索树
void InOrder(PBSTN pRoot);
// 销毁二叉搜索树
void DestroyBSTree(PBSTN* pRoot);
- BinarySearchTree.c
// BinarySearchTree.c
#include "BinarySearchTree.h"
// 初始化二叉搜索树
void InitBSTree(BSTNode** pRoot)
{
assert(pRoot);
(*pRoot) = NULL;
}
PBSTN BuyNewNode(DataType data)
{
PBSTN _new = (PBSTN)malloc(sizeof(BSTNode));
if (_new == NULL)
{
assert(0);
return NULL;
}
else
{
_new->_data = data;
_new->_pLeft = NULL;
_new->_pRight = NULL;
}
return _new;
}
// 插入值为data的元素
// 在二叉树中插入新元素时，必须先检测该元素是否在树中已经存在
// 如果已经存在，则不进行插入
// 否则将新元素加入到搜索停止的地方
// 具体插入过程：
// 1.如果树为空树，则直接插入
// 2.树不空，按二叉搜索树性质查找插入位置，插入新节点
void InsertBSTree(PBSTN* pRoot, DataType data)
{
PBSTN pCur = NULL;
PBSTN pParent = NULL;
assert(pRoot);
pCur = (*pRoot);
if ((pCur == NULL))
{ // 树为空
(*pRoot) = BuyNewNode(data);
}
else
{ // 树不为空
// 查找插入位置
while (pCur)
{
if (pCur->_data == data)
{ // 树中已经有这个元素
return;
}
else if (data < pCur->_data)
{ // 在左子树中找
pParent = pCur;
pCur = pCur->_pLeft;
}
else
{ // 在右子树中找
pParent = pCur;
pCur = pCur->_pRight;
}
}
// 插入新节点
if (data < pParent->_data)
{
pParent->_pLeft = BuyNewNode(data);
}
else
{
pParent->_pRight = BuyNewNode(data);
}
}
}
// 在二叉搜索树中查找值为data的结点
PBSTN FindBSTree(PBSTN pRoot, DataType data)
{
PBSTN pCur = pRoot;
if (pCur == NULL)
{
return NULL;
}
else
{
if (pCur->_data == data)
{
return pCur;
}
else if (data < pCur->_data)
{
return FindBSTree(pCur->_pLeft, data);
}
else
{
return FindBSTree(pCur->_pRight, data);
}
}
}
// 删除值为data的结点
// 要删除的节点有四种情况
// 1.要删除的节点没有孩子节点
// 直接删除
// 2.要删除的节点只有左孩子节点
// 先链接，再删除
// 3.要删除的节点只有右孩子节点
// 先链接，再删除
// 4.既有左孩子，又有右孩子
// (1)寻找一个替代节点：下面两种方法随便一种都行
// 在当前节点左子树中找替代节点：左子树中最右下端的节点
// 在当前节点右子树中找替代节点：右子树中最左下端的节点
// (2)交换当前节点和替代节点的值
// (3)修改要删除的标记----用替代节点覆盖
// 删除值为data的结点
void DeleteBSTree(PBSTN* pRoot, DataType data)
{
PBSTN pCur = NULL;
PBSTN pParent = NULL;
assert(pRoot);
// 1.先找要删除的节点
pCur = (*pRoot);
while (pCur)
{
if (data == pCur->_data)
{
if (pParent == NULL)
{
// 根节点
if (pCur->_pLeft == NULL)
{ // 根节点左子树为空
if (pCur->_pRight == NULL)
{ // 根节点右子树也为空
// (*pRoot) = NULL; // 把根赋空 这种写法不对
pcur = *pRoot;
}
else
{ // 根节点右子树不为空
(*pRoot) = pCur->_pRight; // 让根节点指向当前节点的右孩子
}
}
else
{ // 根节点左子树不为空
if (pCur->_pRight == NULL)
{ // 根节点右子树为空
(*pRoot) = pCur->_pLeft; // 让根节点指向当前节点的左孩子
}
else
{ // 根节点右子树也不为空 需要找一个替代节点
PBSTN _pReplace = pCur->_pLeft;
pParent = pCur;
while (_pReplace->_pRight) // 在左子树中找最大值----左子树的最右下端
{
pParent = _pReplace;
_pReplace = _pReplace->_pRight;
}
pCur->_data = _pReplace->_data;
if (pCur == pParent)
{
pParent->_pLeft = _pReplace->_pLeft;
}
else
{
pParent->_pRight = _pReplace->_pLeft;
}
pCur = _pReplace; // 将待删除节点更改为替代节点
}
}
else
{ // 要删除节点不是根节点
if (pCur->_pLeft == NULL)
{ // 左子树为空
if (pParent->_pLeft == pCur)
{
pParent->_pLeft = pCur->_pRight;
}
else
{
pParent->_pRight = pCur->_pRight;
}
}
else if (pCur->_pRight == NULL)
{ // 右子树为空
if (pParent->_pLeft == pCur)
{
pParent->_pLeft = pCur->_pLeft;
}
else
{
pParent->_pRight = pCur->_pLeft;
}
}
else
{ // 左、右子树都不为空 需要找替代节点
PBSTN _pReplace = pCur->_pRight;
// 在右子树中找最小值----右子树的最左下端
// 最左下端的节点可以直接删除
while (_pReplace->_pLeft)
{
pParent = _pReplace;
_pReplace = _pReplace->_pLeft;
}
pCur->_data = _pReplace->_data;
pParent->_pLeft = _pReplace->_pRight;
pCur = _pReplace; // 将待删除节点更改为替代节点
}
}
break;
}
if (data < pCur->_data)
{
pParent = pCur;
pCur = pCur->_pLeft;
}
else
{
pParent = pCur;
pCur = pCur->_pRight;
}
}
// 2.删除节点
if (pCur)
{
if (pCur == *pRoot)
{
free(*pRoot);
*pRoot = NULL;
}
else
{
free(pCur);
pCur = NULL;
}
}
else
{
printf("树中没有值为%d的节点\n", data);
}
}
// 中序遍历二叉搜索树
void InOrder(PBSTN pRoot)
{
if (pRoot == NULL)
{
return;
}
InOrder(pRoot->_pLeft);
printf("%d ", pRoot->_data);
InOrder(pRoot->_pRight);
}
// 销毁二叉搜索树
void DestroyBSTree(PBSTN* pRoot)
{
assert(pRoot);
if ((*pRoot) == NULL)
{
return;
}
DestroyBSTree(&(*pRoot)->_pLeft);
DestroyBSTree(&(*pRoot)->_pRight);
free(*pRoot);
(*pRoot) = NULL;
}
- test.c
#include "BinarySearchTree.h"
void TestBinarySearchTree()
{
PBSTN Root = NULL;
int arr[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
int i = 0;
int size = sizeof(arr) / sizeof(arr[0]);
PBSTN ret_Find = NULL;
InitBSTree(&Root);
for (i = 0; i < size; i++)
{
InsertBSTree(&Root, arr[i]);
}
printf("InOrder:");
InOrder(Root);
printf("\n");
InsertBSTree(&Root, 10);
printf("InOrder:");
InOrder(Root);
printf("\n");
ret_Find = FindBSTree(Root, 10);
if (ret_Find == NULL)
{
printf("没找到！！！\n");
}
else
{
printf("找到了:%d\n", ret_Find->_data);
}
DeleteBSTree(&Root, 2);
printf("InOrder:");
InOrder(Root);
printf("\n");
DeleteBSTree(&Root, 1);
printf("InOrder:");
InOrder(Root);
printf("\n");
DeleteBSTree(&Root, 5);
printf("InOrder:");
InOrder(Root);
printf("\n");
DeleteBSTree(&Root, 3);
printf("InOrder:");
InOrder(Root);
printf("\n");
DestroyBSTree(&Root);
}
int main()
{
TestBinarySearchTree();
system("pause");
return 0;
}
测试结果：
如有不正，还请指出，有劳！！！