二叉搜索树封装代码
#pragma once
#include <iostream>
using namespace std;
template<class T>class TreeNode {
public:
TreeNode(T value)
{
this->val = value;
this->right = NULL;
this->left = NULL;
}
TreeNode() { }
T val;
TreeNode *left;
TreeNode *right;
};
template<class T>class BST {
public:
BST();
void Insert(T value); //插入元素接口
void InOrder(); //打印中序序列接口
int GetSize(); //返回当前二叉树总元素个数
int GetMaxValue(); //返回当前二叉树的最大值
int GetMinValue(); //返回当前二叉树的最小值
void Delete(T value); //删除该元素
private:
TreeNode<T> *insert(TreeNode<T> *root, T value ); //内部插入实现
TreeNode<T> *deleteval(TreeNode<T> *node, T val); //删除某个元素
TreeNode<T> *FindMin(TreeNode<T> *node); //找到最小的元素的结点
TreeNode<T> *FindMax(TreeNode<T> *node); //找到最大的元素的结点
T getmaxvalue(TreeNode<T> *node);
T getminvalue(TreeNode<T> *node);
void inorder(TreeNode<T> *node); //内部中序遍历
TreeNode<T> *Tree;
int size;
};
template<class T>
inline BST<T>::BST()
{
this->size = 0;
this->Tree = NULL;
}
//往BST树中插入数据
template<class T>
inline void BST<T>::Insert(T value)
{
this->Tree = insert(Tree, value);
}
template<class T>
inline TreeNode<T> * BST<T>::insert(TreeNode<T> *node, T value)
{
if (node == NULL)
{
size++;
return new TreeNode<T>(value);
}
else {
if (value < node->val)
{
node->left = insert(node->left, value);
return node;
}
else if (value > node->val)
{
node->right = insert(node->right, value);
return node;
}
}
}
//获取当前二叉树的所有非空结点
template<class T>
inline int BST<T>::GetSize()
{
return this->size;
}
template<class T>
inline int BST<T>::GetMaxValue()
{
return this->getmaxvalue(Tree);
}
template<class T>
inline int BST<T>::GetMinValue()
{
return this->getminvalue(Tree);
}
template<class T>
inline void BST<T>::Delete(T value)
{
Tree = this->deleteval(Tree, value);
this->size--;
}
//中序遍历
template<class T>
inline void BST<T>::InOrder()
{
inorder(Tree);
}
template<class T>
inline void BST<T>::inorder(TreeNode<T> *node)
{
if (node != NULL)
{
inorder(node->left);
cout << node->val << " ";
inorder(node->right);
}
}
template<class T>
inline TreeNode<T> * BST<T>::deleteval(TreeNode<T>* node, T val)
{
if (node == NULL)cout << "未找到此元素" << endl;
TreeNode<T> *tmp = new TreeNode<T>;
if (val < node->val)
node->left = deleteval(node->left, val);
else if(val > node->val)
node->right = deleteval(node->right, val);
else {
if (node->left != NULL && node->right != NULL) //存在左右子树
{
tmp = this->FindMin(node->right);
node->val = tmp->val;
node->right = deleteval(node->right, node->val);
}
else { //叶子结点或者只有一个子节点
tmp = node;
if (!node->left)
node = node->right;
else if (!node->right)
node = node->left;
free(tmp);
}
}
return node;
}
template<class T>
inline TreeNode<T>* BST<T>::FindMin(TreeNode<T>* node)
{
if (node->left == NULL)return node;
else return FindMin(node->left);
}
template<class T>
inline TreeNode<T>* BST<T>::FindMax(TreeNode<T>* node)
{
if (node->right == NULL)return node;
else return FindMax(node->right);
}
template<class T>
inline T BST<T>::getmaxvalue(TreeNode<T> *node)
{
//如果当前结点的左子树为空树,则当前结点就是最大值
if (node->right == NULL)
return node->val;
else return getmaxvalue(node->right);
}
template<class T>
inline T BST<T>::getminvalue(TreeNode<T> *node)
{
if (node->left == NULL)
return node->val;
else return getminvalue(node->left);
}
测试代码
#include <istream>
#include "BST.h"
using namespace std;
int main()
{
BST<int> bt;
int arr[] = { 9,5,3,4,1,7,2,8,0 };
int n = sizeof(arr) / sizeof(int);
for (int i = 0; i < n; i++)
bt.Insert(arr[i]);
bt.InOrder();
cout << endl << bt.GetSize() << endl;
cout << "这组元素中的最大值为：" <<bt.GetMaxValue() << endl;
cout << "这组元素中的最小值为：" <<bt.GetMinValue() << endl;
cout << "输入你想删除任意一个元素" << endl;
int x = 0;
cin >> x;
bt.Delete(x);
bt.InOrder();
cout << "此时该集合内的元素个数为:" << bt.GetSize() << endl;
system("pause");
return 0;
}