// 二叉搜索树:
// A.每个结点都有一个关键码,每个关键码互不相同;
// B.左子树(若存在)上所有结点的关键码都小于根结点的关键码;
// C.右子树(若存在)上所有结点的关键码都大于根结点的关键码;
// D.左子树和右子树也是二叉搜索树
//
// 建立:采取插入建立
// 遍历:采取中序遍历
//
// 测试数据:53 78 65 17 87 09 81 15 -1(结束标志)
#include <iostream>
#include <stack>
template <class T>
struct BSTNode // 二叉搜索树结点的结构定义
{
T data;
BSTNode *lChild, *rChild; // 左右孩子指针
};
template <class T>
class BinarySearchTree
{
public:
BinarySearchTree(BSTNode<T> *p = NULL) {root = p;} // 构造函数
void createBST(); // 建立二叉搜索树
bool Insert(T x); // 递归插入
bool Insert1(T x); // 非递归插入
bool Pop(T x); // 删除:查找到x,删除x
void inOrder(); // 中序遍历
bool seachBST(T x); // 查找函数:递归查找
bool seachBST1(T x); // 查找函数:非递归查找
T getMin(); // 获取最小值
T getMax(); // 获取最大值
private:
bool seachBST(T x, BSTNode<T> *p); // 递归搜索
bool Insert(T x, BSTNode<T> *&p); // 递归插入
bool deleteNode(T x, BSTNode<T> *&p); // 删除结点
BSTNode<T> *root;
};
// 建立二叉搜索树
template <class T>
void BinarySearchTree<T>::createBST()
{
int x;
std::cout << "请输入数据建立二叉搜索树:\n";
std::cin >> x;
while(x != -1)
{
Insert(x);
std::cin >> x;
}
}
// 递归插入
template <class T>
bool BinarySearchTree<T>::Insert(T x)
{
return Insert(x, root);
}
// 递归插入:注意要使用引用符号&,否则每次插入被忽略,root永远为NULL
template <class T>
bool BinarySearchTree<T>::Insert(T x, BSTNode<T> *&p)
{
BSTNode<T> *newNode;
if(p == NULL) {
newNode = new BSTNode<T>(); // 新结点
if(newNode == NULL)
{
std::cerr << "申请空间失败!\n";
exit(1);
}
newNode->data = x;
newNode->lChild = newNode->rChild = NULL;
p = newNode;
return true; // 插入成功
}
if(x < p->data)
return Insert(x, p->lChild); // 在左子树中插入
else if(x > p->data)
return Insert(x, p->rChild); // 在右子树中插入
else
return false; // 重复值,插入不成功
}
// 非递归插入
template <class T>
bool BinarySearchTree<T>::Insert1(T x)
{
BSTNode<T> *current, *prev, *newNode;
current = root;
prev = NULL; // 跟踪指针
while(current != NULL)
{
if(x == current->data)
return false; // 重复值,插入不成功
else if(x < current->data)
{
prev = current;
current = current->lChild; // 在左子树中找
}
else
{
prev = current;
current = current->rChild; // 在右子树中找
}
}
// 插入
newNode = new BSTNode<T>(); // 新结点
newNode->data = x;
newNode->lChild = newNode->rChild = NULL;
if(prev == NULL) // 插入到根结点
root = newNode;
else if(x < prev->data)
prev->lChild = newNode; // 作为左子树
else
prev->rChild = newNode; // 作为右子树
return true; // 插入成功
}
// 删除:查找到x,删除x
template <class T>
bool BinarySearchTree<T>::Pop(T x)
{
return deleteNode(x, root);
}
// 删除结点
template <class T>
bool BinarySearchTree<T>::deleteNode(T x, BSTNode<T> *&p) {
if(p == NULL)
return false;
if(x > p->data) {
return deleteNode(x, p->rChild);
} else if(x < p->data) {
return deleteNode(x, p->lChild);
} else { // 查找到了删除结点
if(p->lChild == NULL) { // 左子树为空
BSTNode<T> *current = p;
p = p->rChild;
delete current;
} else if(p->rChild == NULL) { // 右子树为空
BSTNode<T> *current = p;
p = p->lChild;
delete current;
} else { // 左、右子树都不为空
// 找前驱:即左子树中的最大数据
// 或者找后驱:即右子树中的最小数据
BSTNode<T> *current = p->lChild;
while(current->rChild != NULL) // 找左子树中最大的元素
current = current->rChild;
p->data = current->data; // 用直接前驱的值填到要删除的结点
// deleteNode(current->data, p->lChild); // p->lChild相当于新的一棵树的根结点,查找current->data并删除
deleteNode(current->data, current); // 这个是直接跳到该删除的点,对找到的前驱进行同样的删除
}
return true;
}
}
// 查找函数:递归查找
template <class T>
bool BinarySearchTree<T>::seachBST(T x)
{
return seachBST(x, root);
}
// 查找函数:递归查找
template <class T>
bool BinarySearchTree<T>::seachBST(T x, BSTNode<T> *p)
{
if(p != NULL)
{
if(x == p->data)
return true;
else if(x < p->data)
return seachBST(x, p->lChild); // 在左子树继续查找
else
return seachBST(x, p->rChild); // 在右子树继续查找
}
return NULL; // 没找到
}
// 查找函数:非递归查找
template <class T>
bool BinarySearchTree<T>::seachBST1(T x)
{
BSTNode<T> *current = root;
while(current != NULL)
{
if(x == current->data)
return current;
else if(x < current->data)
current = current->lChild; // 在左子树中找
else
current = current->rChild; // 在右子树中找
}
return NULL;
}
// 中序遍历
template <class T>
void BinarySearchTree<T>::inOrder()
{
std::stack<BSTNode<T> *> s;
BSTNode<T> *current; // 当前结点
BSTNode<T> *sTop; // 找顶结点
if(root == NULL)
std::cout << "空二叉搜索树\n";
else
{
current = root;
while(current != NULL || !s.empty())
{
while(current != NULL) // 往左孩子结点往下走
{
s.push(current);
current = current->lChild;
}
if(!s.empty())
{
sTop = s.top(); // 取栈顶结点
s.pop();
std::cout << sTop->data << " ";
current = sTop->rChild; // 遍历右孩子树
}
}
}
std::cout << "\n";
}
// 获取最小值
template <class T>
T BinarySearchTree<T>::getMin()
{
BSTNode<T> *current;
if(root == NULL)
{
std::cout << "空二叉搜索树!\n";
return -1;
}
current = root;
while(current->lChild != NULL)
current = current->lChild;
return current->data;
}
// 获取最大值
template <class T>
T BinarySearchTree<T>::getMax()
{
BSTNode<T> *current;
if(root == NULL)
{
std::cout << "空二叉搜索树!\n";
return -1;
}
current = root;
while(current->rChild != NULL)
current = current->rChild;
return current->data;
}
int main(int argc, const char * argv[]) {
int choose, finished, x;
int min, max; // 最小值、最大值
BinarySearchTree<int> BST; // 声明二叉搜索树对象
finished = 0;
while(!finished)
{
std::cout << "\n***********菜单***************\n";
std::cout << "1:创建二叉搜索树\n";
std::cout << "2:递归插入\n";
std::cout << "3:非递归插入\n";
std::cout << "4:中序遍历\n";
std::cout << "5:递归查找\n";
std::cout << "6:非递归查找\n";
std::cout << "7:获取最小值\n";
std::cout << "8:获取最大值\n";
std::cout << "9:删除某值\n";
std::cout << "10:退出\n";
std::cout << "请输入选择[1-10]:";
std::cin >> choose;
switch(choose)
{
case 1:
BST.createBST(); // 创建二叉搜索树
break;
case 2:
std::cout << "请输入插入的值:";
std::cin >> x;
if(BST.Insert(x)) // 插入成功
std::cout << "插入成功!\n";
else
std::cout << "插入失败!\n";
break;
case 3:
std::cout << "请输入插入的值:";
std::cin >> x;
if(BST.Insert1(x)) // 插入成功
std::cout << "插入成功!\n";
else
std::cout << "插入失败!\n";
break;
case 4:
std::cout << "中序遍历二叉搜索树:\n";
BST.inOrder(); // 中序遍历
break;
case 5:
std::cout << "请输入要查找的值:";
std::cin >> x;
if(BST.seachBST(x)) // 递归查找
std::cout << "查找成功!\n";
else
std::cout << "查找失败!\n";
break;
case 6:
std::cout << "请输入要查找的值:";
std::cin >> x;
if(BST.seachBST1(x)) // 非递归查找
std::cout << "查找成功!\n";
else
std::cout << "查找失败!\n";
break;
case 7:
min = BST.getMin(); // 获取最小值
if(min != -1)
std::cout << "最小值:" << min << "\n";
break;
case 8:
max = BST.getMax(); // 获取最大值
if(max != -1)
std::cout << "最大值:" << max << "\n";
break;
case 9:
std::cout << "请输入要删除的值:";
std::cin >> x;
if(BST.Pop(x))
std::cout << "删除成功!\n";
else
std::cout << "删除失败!\n";
break;
case 10:
finished = 1;
break;
default:
std::cout << "输入错误,请重新输入!\n";
}
}
return 0;
}