正文

c++ 搜索二叉树 插入，删除，遍历操作

IP云
IP云V管理员/0 阅读
07/23
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构，包括多种操作，本篇只介绍插入，排序（遍历），和删除操作，重点是删除操作比较复杂，用到的例子也是本人亲自画的

用到的测试图数据例子

第一、构建节点

template <typename T> class BST;
template <typename T> class BSTNode {
public:
friend class BST<T>;
BSTNode() {
lChild = rChild = parent = NULL;
data = NULL;
}
BSTNode(T d) {
lChild = rChild = parent = NULL;
data = d;
}
private:
BSTNode<T> *lChild, *rChild, *parent;
T data;
};

第二、二叉树头文件定义

template<typename T> class BST {
public:
BST() { } //插入操作
void insert(BSTNode<T>*node); //二叉查找树的中序遍历，就相当于排序了
void inSort(BSTNode<T>*node); //按节点删除
void deleteNode(BSTNode<T>* node); //按数值删除
void deleteNode(const T& t); BSTNode<T>* search(T key);
BSTNode<T>* root=NULL; private:
int count;
};

第三、搜索二叉树的插入

1）如果二叉树查找树为空节点，则插入节点就为根节点

2）如果二叉查找树为非空节点，就需要先找到待插入节点，查找原则就是从根节点开始，如果大于根就右边走，小于根就左边走，直到找到合适节点，

下面代码中的最终找到的temp 就是待插入节点.

template<typename T>
void BST<T>::insert(BSTNode<T>* node)
{
BSTNode<T>* curr, *temp = NULL;
curr = root;
while (NULL!= curr) //遍历二叉树，找到应该插入的父节点
{
temp = curr;
if (node->data>curr->data)
{
curr = curr->rChild;
}
else {
curr = curr->lChild;
}
}
node->parent = temp;//temp 代码当前最后遍历的node，设置node->parent为该节点
if (temp==NULL)
{
root = node;
count++;
}
else {
if (node->data<temp->data)
{
temp->lChild = node;
count++;
}
else {
temp->rChild = node;
count++;
}
}
}

第四、搜索二叉树的删除

删除包含多种情况，

1. 如果节点没有子女，修改其父节点指针为NULL，删除即可

2. 如果该节点有左孩子情况，修改其父亲节点的指针和其左孩子的parent指针即可

3. 如果该节点有右孩子情况，修改其父亲节点的指针和其右孩子的parent指针即可

4.如果同时有左右孩子的情况，情况比较复杂，一般有2种方法处理

1） 用节点右边孩子的最小值替换该节点，其他节点位置保持不变（本篇用这种方法）

2）用节点左边孩子的最大值替换该节点，其他节点位置保持不变

后面测试例子是删除18 node，通过程序找到右边最小值20，用20 替换18，其他节点位置保持不动。

template<typename T>
inline void BST<T>::deleteNode(BSTNode<T>* node)
{
BSTNode<T>*p = node->parent;//获取node的父节点，这里很重要
if (node->lChild==NULL && node->rChild==NULL) //叶子节点直接删除
{
if (node==node->parent->lChild)
{
node->parent->lChild = NULL;
}
else {
node->parent->rChild = NULL;
}
delete node;
count--;
}
else if (node->rChild != NULL && node->lChild == NULL) {//存在右孩子
if (p==NULL)//说明节点为根节点
{
root = node->rChild;
count--;
}
else {
node->rChild->parent = p;
if (p->lChild==node) //判断是父节点的左孩子还是右孩子
{
p->lChild = node->rChild;
}
else {
p->rChild = node->rChild;
}
delete node;
count--;
}
}
else if (node->lChild!=NULL && node->rChild==NULL)//存在左孩子
{
if (p==NULL)
{
root = root->lChild;
count--;
}
else {
node->lChild->parent = p;
if (p->lChild==node)
{
p->lChild = node->lChild;
}
else {
p->rChild = node->lChild;
}
delete node;
count--;
}
}
else {
BSTNode<T>*left, *curp=NULL;
left = node->rChild; //本方案是找右侧最小值，替换node节点，其他节点保持不动即可
while (left!=NULL)
{
curp = left;
left = left->lChild;
} if (curp->rChild!=NULL)
{
if (curp->lChild==curp)
{
curp->parent->lChild = curp->rChild;
}
else {
curp->parent->rChild = curp->rChild;
}
}
else {
if (curp->parent->lChild==curp)
{
curp->parent->lChild = NULL;
}
else {
curp->parent->rChild = NULL;
}
//curp->parent->lChild = NULL;
}
//替curp 替换 node
curp->parent = p;
curp->lChild = node->lChild;
curp->rChild = node->rChild; if (p->lChild==node)//判断node 是p 的左孩子还是右孩
{
p->lChild = curp;
}
else {
p->rChild = curp;
}
delete node;
count--;
}
}

第五、二叉树的搜索查找

由于搜索二叉树本身是已经排序好的，查找过程相对简单，从根节点，逐个排查，大于根向右，小于根向左，直到叶子节点.

template<typename T>
inline BSTNode<T>* BST<T>::search(T k)
{
BSTNode<T>*node = root;
while (node!=NULL)
{
if (k<node->data)
{
node = node->lChild;
}
else if (k> node->data)
{
node = node->rChild;
}
else {
break;
}
}
return node;
}

第六、二叉搜索树的排序

根据二叉所有树的特性，这里所谓排序，其实就是二叉树的中序遍历，其他的几种遍历不在这里赘述，知识调整下结构即可

template<typename T>
void BST<T>::inSort(BSTNode<T>* node)
{
if (node!=NULL)
{
inSort(node->lChild);
std::cout << node->data<<",";
inSort(node->rChild);
}
}

第七、测试程序

#include "pch.h"
#include <iostream>
#include "BSTree.h"
using namespace std; int main()
{
// 树结构示意
// 30
// / \
// 15 25
// / \
//9 18
// / \
// 16 25
// / \
// 20 26
BST<int> sbt;
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>());
sbt.insert(new BSTNode<int>()); cout << "搜索树排序后:";
sbt.inSort(sbt.root); sbt.deleteNode(); cout << endl << "删除18 后排序:"; sbt.inSort(sbt.root);
}

测试结果

所有完整程序代码

#pragma once
template <typename T> class BST;
template <typename T> class BSTNode {
public:
friend class BST<T>;
BSTNode() {
lChild = rChild = parent = NULL;
data = NULL;
}
BSTNode(T d) {
lChild = rChild = parent = NULL;
data = d;
}
private:
BSTNode<T> *lChild, *rChild, *parent;
T data;
}; template<typename T> class BST {
public:
BST() { } //插入操作
void insert(BSTNode<T>*node); //二叉查找树的中序遍历，就相当于排序了
void inSort(BSTNode<T>*node); //按节点删除
void deleteNode(BSTNode<T>* node); //按数值删除
void deleteNode(const T& t); BSTNode<T>* search(T key);
BSTNode<T>* root=NULL; private:
int count;
}; template<typename T>
void BST<T>::insert(BSTNode<T>* node)
{
BSTNode<T>* curr, *temp = NULL;
curr = root;
while (NULL!= curr) //遍历二叉树，找到应该插入的父节点
{
temp = curr;
if (node->data>curr->data)
{
curr = curr->rChild;
}
else {
curr = curr->lChild;
}
}
node->parent = temp;//temp 代码当前最后遍历的node，设置node->parent为该节点
if (temp==NULL)
{
root = node;
count++;
}
else {
if (node->data<temp->data)
{
temp->lChild = node;
count++;
}
else {
temp->rChild = node;
count++;
}
}
} template<typename T>
void BST<T>::inSort(BSTNode<T>* node)
{
if (node!=NULL)
{
inSort(node->lChild);
std::cout << node->data<<",";
inSort(node->rChild);
}
} template<typename T>
inline void BST<T>::deleteNode(BSTNode<T>* node)
{
BSTNode<T>*p = node->parent;//获取node的父节点，这里很重要
if (node->lChild==NULL && node->rChild==NULL) //叶子节点直接删除
{
if (node==node->parent->lChild)
{
node->parent->lChild = NULL;
}
else {
node->parent->rChild = NULL;
}
delete node;
count--;
}
else if (node->rChild != NULL && node->lChild == NULL) {//存在右孩子
if (p==NULL)//说明节点为根节点
{
root = node->rChild;
count--;
}
else {
node->rChild->parent = p;
if (p->lChild==node) //判断是父节点的左孩子还是右孩子
{
p->lChild = node->rChild;
}
else {
p->rChild = node->rChild;
}
delete node;
count--;
}
}
else if (node->lChild!=NULL && node->rChild==NULL)//存在左孩子
{
if (p==NULL)
{
root = root->lChild;
count--;
}
else {
node->lChild->parent = p;
if (p->lChild==node)
{
p->lChild = node->lChild;
}
else {
p->rChild = node->lChild;
}
delete node;
count--;
}
}
else {
BSTNode<T>*left, *curp=NULL;
left = node->rChild; //本方案是找右侧最小值，替换node节点，其他节点保持不动即可
while (left!=NULL)
{
curp = left;
left = left->lChild;
} if (curp->rChild!=NULL)
{
if (curp->lChild==curp)
{
curp->parent->lChild = curp->rChild;
}
else {
curp->parent->rChild = curp->rChild;
}
}
else {
if (curp->parent->lChild==curp)
{
curp->parent->lChild = NULL;
}
else {
curp->parent->rChild = NULL;
}
//curp->parent->lChild = NULL;
}
//替curp 替换 node
curp->parent = p;
curp->lChild = node->lChild;
curp->rChild = node->rChild; if (p->lChild==node)//判断node 是p 的左孩子还是右孩
{
p->lChild = curp;
}
else {
p->rChild = curp;
}
delete node;
count--;
}
} template<typename T>
inline void BST<T>::deleteNode(const T & k)
{
BSTNode<T>*node = search(k);
if (node!=NULL)
{
deleteNode(node);
}
} template<typename T>
inline BSTNode<T>* BST<T>::search(T k)
{
BSTNode<T>*node = root;
while (node!=NULL)
{
if (k<node->data)
{
node = node->lChild;
}
else if (k> node->data)
{
node = node->rChild;
}
else {
break;
}
}
return node;
}

BSTree.h