C++ 二叉查找树 —— 插入、遍历、查找、删除、销毁
二叉查找树的特性：
二叉查找树（Binary Search Tree）（又：二叉搜索树，二叉排序树）
具有以下特性：
（1）若“左子树”不为空，则“左子树”上所有节点的值均小于“根节点”的值；
（2）若“右子树”不为空，则“右子树”上所有节点的值均大于“根节点”的值；
（3）左、右子树也分别为二叉排序树。
01 声明：
#include <iostream>
using namespace std;
/************************/
/* 12_01.h 文件
/************************/
class BSTNode
{
public:
int key; //关键字
BSTNode *left; //左子节点
BSTNode *right; //右子节点
BSTNode *parent; //父节点
BSTNode(int k = 0, BSTNode *l = NULL, BSTNode *r = NULL, BSTNode *p = NULL) : key(k), left(l), right(r), parent(p) {}; //初始化列表
};
class BSTree
{
public:
BSTree(); //构造函数
~BSTree(); //析构函数
void insert(int key); //将key节点插入到二叉树中
void PreOrder(); //前序二叉树遍历
void InOrder(); //中序二叉树遍历
void PostOrder(); //后序二叉树遍历
BSTNode *search(int key); //递归实现，在二叉树中查找key节点
BSTNode *IteratorSearch(int key); //迭代实现，在二叉树中查找key节点
BSTNode *successor(BSTNode *x); //找节点(x)的后继节点。即，查找"二叉树中数据值大于该节点"的"最小节点"
BSTNode *predecessor(BSTNode *x); //找节点(x)的前驱节点。即，查找"二叉树中数据值小于该节点"的"最大节点"
void remove(int key); //删除key节点
void destroy(); //销毁二叉树
private:
BSTNode *root; //根节点
void PreOrder(BSTNode *tree); //前序二叉树遍历
void InOrder(BSTNode *tree); //中序二叉树遍历
void PostOrder(BSTNode *tree); //后序二叉树遍历
BSTNode *search(BSTNode *x, int key); //递归实现，在”二叉树x“中查找key节点
BSTNode *IteratorSearch(BSTNode *x, int key); //迭代实现，在“二叉树x”中查找key节点
BSTNode *minimum(BSTNode *tree); //查找最小节点：返回tree为根节点的二叉树的最小节点
BSTNode *maximum(BSTNode *tree); //查找最大节点：返回tree为根节点的二叉树的最大节点
void insert(BSTNode *&tree, BSTNode *z); // 将节点(z)插入到二叉树(tree)中
BSTNode *remove(BSTNode *tree, BSTNode *z); // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
void destroy(BSTNode *&tree); //销毁二叉树
};
02 功能：
#include "12_01.h"
BSTree::BSTree() :root(NULL) {}; //构造函数
BSTree::~BSTree() //析构函数
{
destroy();
}
void BSTree::insert(int key) //将key节点插入到二叉树中
{
BSTNode *z = new BSTNode(key, NULL, NULL, NULL); //根据插入的key生成新的二叉树节点(z)
if (z == NULL)
{
return; //如果z里面的值为空，则停止函数的执行
}
insert(root, z); //把新生的节点(z)传入树根
}
void BSTree::PreOrder(BSTNode *tree) //前序二叉树遍历
{
if (tree != NULL)
{
cout << tree->key << " ";
PreOrder(tree->left);
PreOrder(tree->right);
}
}
void BSTree::PreOrder()
{
PreOrder(root); //传入根节点
}
void BSTree::InOrder(BSTNode *tree) //中序二叉树遍历
{
if (tree != NULL)
{
InOrder(tree->left);
cout << tree->key << " ";
InOrder(tree->right);
}
}
void BSTree::InOrder()
{
InOrder(root); //传入根节点
}
void BSTree::PostOrder(BSTNode *tree) //后序二叉树遍历
{
if (tree != NULL)
{
PostOrder(tree->left);
PostOrder(tree->right);
cout << tree->key << " ";
}
}
void BSTree::PostOrder()
{
PostOrder(root); //传入根节点
}
BSTNode *BSTree::search(BSTNode *x, int key) //递归实现，在”二叉树x“中查找key节点
{
if (x == NULL || key == x->key)
{
return x;
}
if (key < x->key)
{
return search(x->left, key);
}
else
{
return search(x->right, key);
}
}
BSTNode *BSTree::search(int key)
{
return search(root, key); //传入根节点和待查找的关键字key
}
BSTNode *BSTree::IteratorSearch(BSTNode *x, int key) //迭代实现，在“二叉树x”中查找key节点
{
while (x != NULL && key != x->key)
{
if (key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
}
return x;
}
BSTNode *BSTree::IteratorSearch(int key)
{
return IteratorSearch(root, key); //传入根节点和待查找的关键字key
}
BSTNode *BSTree::minimum(BSTNode *tree) //查找最小节点：返回tree为根节点的二叉树的最小节点。
{
if (tree == NULL)
{
return NULL;
}
while (tree->left != NULL)
{
tree = tree->left;
}
return tree;
}
BSTNode *BSTree::maximum(BSTNode *tree) //查找最大节点：返回tree为根节点的二叉树的最大节点。
{
while (tree->right != NULL)
{
tree = tree->right;
}
return tree;
}
BSTNode *BSTree::successor(BSTNode *x) //找节点(x)的后继节点，也就是该节点的右子树中的最小节点
{
BSTNode *y = NULL;
if (x->right != NULL)
{
return minimum(x->right);
}
// 如果x没有右子节点。则x有以下两种可能：
// （1） x是"一个左子节点"，则"x的后继节点"为 "它的父节点"。
// （2） x是"一个右子节点"，则查找"x的最低的父节点，并且该父节点要具有左子节点"，找到的这个"最低的父节点"就是"x的后继节点"。
y = x->parent;
while (y != NULL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
BSTNode *BSTree::predecessor(BSTNode *x) //找节点(x)的前驱节点是该节点的左子树中的最大节点。
{
BSTNode *y = NULL;
if (x->left != NULL)
{
return maximum(x->left);
}
// 如果x没有左子节点。则x有以下两种可能：
//（1）x是"一个右子节点"，则"x的前驱节点"为 "它的父节点"。
//（2）x是"一个左子节点"，则查找"x的最低的父节点，并且该父节点要具有右子节点"，找到的这个"最低的父节点"就是"x的前驱节点"。
y = x->parent;
while (y != NULL && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
void BSTree::insert(BSTNode *&tree, BSTNode *z) // 将节点(z)插入到二叉树(tree)中
{
BSTNode *y = NULL;
BSTNode *x = tree;
while (x != NULL) // 查找z的插入位置
{
y = x;
if (z->key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
}
z->parent = y;
if (y == NULL)
{
tree = z;
}
else
if (z->key < y->key)
{
y->left = z;
}
else
{
y->right = z;
}
}
BSTNode *BSTree::remove(BSTNode *tree, BSTNode *z) // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
{
BSTNode *x = NULL;
BSTNode *y = NULL;
if (z->left == NULL || z->right == NULL)
{
y = z;
}
else
{
y = successor(z);
}
if (y->left != NULL)
{
x = y->left;
}
else
{
x = y->right;
}
if (x != NULL)
{
x->parent = y->parent;
}
if (y->parent == NULL)
{
tree = x;
}
else
if (y == y->parent->left)
{
y->parent->left = x;
}
else
{
y->parent->right = x;
}
if (y != z)
{
z->key = y->key;
}
return y;
}
void BSTree::remove(int key) // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
{
BSTNode *z, *node;
z = IteratorSearch(root, key); //根据给定的key，查找树中是否存在key节点
if (z != NULL)
{
node = remove(root, z); //传入树根以及待删除的节点(z)
if (node != NULL)
{
delete node;
}
}
}
void BSTree::destroy(BSTNode *&tree) //销毁二叉树
{
if (tree == NULL)
{
return; //停止函数的执行
}
if (tree->left != NULL)
{
return destroy(tree->left);
}
if (tree->right != NULL)
{
return destroy(tree->right);
}
delete tree;
tree = NULL;
}
void BSTree::destroy() //销毁二叉树
{
destroy(root);
}
03 执行：
#include <iostream>
#include <stdlib.h>
#include "12_01.h"
using namespace std;
/***********************************************************/
/* 二叉查找树 —— 插入、遍历、查找、删除、销毁
/**********************************************************/
int main(void)
{
/************************/
/* 插入
/************************/
BSTree *tree = new BSTree();
int array[6] = {11, 33, 18, 24, 44, 66};
cout << "二叉树数值：" << endl;
for (int i = 0; i < 6; i++)
{
cout << array[i] << " ";
tree->insert(array[i]); //调用插入函数，生成二叉查找树
}
cout << endl << endl;
/************************/
/* 遍历
/************************/
cout << "前序遍历：";
tree->PreOrder();
cout << endl;
cout << "中序遍历：";
tree->InOrder();
cout << endl;
cout << "后序遍历：";
tree->PostOrder();
cout << endl << endl;
/************************/
/* 查找
/************************/
int keyword; //查找节点的关键字
cout << "请输入要查找的节点：";
cin >> keyword;
cout << endl;
BSTNode *node = tree->IteratorSearch(keyword); //获取数值的地址
if (node) //判断有没有地址
{
cout << "关键字为“" << keyword << "”的节点，存在。" << endl ;
}
else
{
cout << "关键字为“" << keyword << "”的节点，不存在。" << endl;
}
cout << endl << endl;
/************************/
/* 删除
/************************/
int DelNode; //要删除的节点
cout << "请输入要删除的节点：";
cin >> DelNode;
tree->remove(DelNode);
cout << endl;
cout << "删除操作后，(前序)遍历：";
tree->PreOrder();
cout << endl;
cout << "删除操作后，(中序)遍历：";
tree->InOrder();
cout << endl;
cout << "删除操作后，(后序)遍历：";
tree->PostOrder();
cout << endl << endl;
/************************/
/* 销毁
/************************/
tree->destroy();
system("pause");
return 0;
}