正文
使用C++实现二叉搜索树的数据结构
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
需要注意的地方：
①二叉搜索树删除一个指定结点R，若R为叶子结点，则将R的父结点中指向R的指针改为指向nullptr；若R的左右子结点一个为空，一个非空，则将R的父结点中指向R的指针改为指向R的非空子结点；若R有两个非空子结点，则找出R的右子树中的最小值结点，将其删除并将R的值置为该最小值结点的值。
②对二叉搜索树进行中序遍历，将得到按升序排序的输出结果。
③使用了多态，二叉搜索树结点类BSTNode继承自抽象类BinNode（二叉树结点类）。
④二叉搜索树不是自平衡的，二叉搜索树的平衡性取决于结点的插入顺序，在极端情况二叉搜索树会退化成链表，查找元素的时间复杂度会退化为O(N)。
代码如下，写在头文件中：
#ifndef BST_H
#define BST_H #include <iostream>
#include <queue> /************************************************************************/
/* 抽象二叉树结点类 */
/************************************************************************/
template <typename Val>
class BinNode
{
public:
virtual ~BinNode() {}
virtual bool IsLeaf() const = ;
virtual Val GetValue() const = ;
virtual void SetValue(const Val &val_) = ;
virtual BinNode* GetLeftChild() const = ;
virtual void SetLeftChild(BinNode *lc) = ;
virtual BinNode* GetRightChild() const = ;
virtual void SetRightChild(BinNode *rc) = ;
virtual void InOrderTraverse() const = ;
}; /************************************************************************/
/* 二叉搜索树结点类 */
/************************************************************************/
template <typename Key, typename Val>
class BSTNode : public BinNode<Val>
{
public:
BSTNode()
: key(), val(), left_(nullptr), right_(nullptr) {}
BSTNode(const Key &key_, const Val &val_, BSTNode *lc = nullptr, BSTNode *rc = nullptr)
: key(key_), val(val_), left_(lc), right_(rc) {}
~BSTNode() {}
bool IsLeaf() const { return (left_ == nullptr) && (right_ == nullptr); } //判断是否为叶结点
Key GetKey() const { return key; }
void SetKey(const Key &key_) { key = key_; } //删除结点时用到,其他情况下不可对key值做修改
Val GetValue() const { return val; }
void SetValue(const Val &val_) { val = val_; }
BSTNode* GetLeftChild() const { return left_; }
void SetLeftChild(BinNode<Val> *lc) { left_ = dynamic_cast<BSTNode*>(lc); }
BSTNode* GetRightChild() const { return right_; }
void SetRightChild(BinNode<Val> *rc) { right_ = dynamic_cast<BSTNode*>(rc); }
void InOrderTraverse() const; //中序遍历
private:
Key key;
Val val;
BSTNode *left_;
BSTNode *right_;
}; template <typename Key, typename Val>
void BSTNode<Key, Val>::InOrderTraverse() const
{
if (left_ != nullptr)
{
left_->InOrderTraverse();
}
std::cout << "Key: " << key << ", Value: " << val << "\n";
if (right_ != nullptr)
{
right_->InOrderTraverse();
}
} /************************************************************************/
/* 二叉搜索树类 */
/************************************************************************/
template <typename Key, typename Val>
class BSTree
{
public:
BSTree()
: root(nullptr), node_num() {}
~BSTree() { Deconstructor(root); }
BSTree(const BSTree &bst) = delete; //禁止编译器生成拷贝构造函数
BSTree& operator=(const BSTree &bst) = delete; //禁止编译器重载拷贝赋值运算符
void InOrderTraverse() const; //中序遍历
void Insert(const Key &key, const Val &val); //插入新结点
Val Delete(const Key &key); //删除指定结点,返回结点的值
Val Find(const Key &key) const; //获取指定key值结点对应的val值
void SetEmpty(); //清空树中所有结点
void BFS() const; //广度优先搜索遍历
unsigned int Size() const { return node_num; }
private:
BSTNode<Key, Val> *root;
unsigned int node_num;
/************************************************************************/
/* 私有函数 */
/************************************************************************/
BSTNode<Key, Val>* Inserter(BSTNode<Key, Val> *root, const Key &key, const Val &val); //插入结点的辅助函数
void Deconstructor(BSTNode<Key, Val> *root); //析构函数的辅助函数,delete所有结点
BSTNode<Key, Val>* GetMinValueNode(BSTNode<Key, Val> *root) const; //找到Key值最小的结点
BSTNode<Key, Val>* DeleteMinValueNode(BSTNode<Key, Val> *root); //删除Key值最小的结点
BSTNode<Key, Val>* Deleter(BSTNode<Key, Val> *root, const Key &key); //删除结点的辅助函数
Val Finder(BSTNode<Key, Val> *root, const Key &key) const; //找出指定Key值的结点,并返回val的值
}; template <typename Key, typename Val>
void BSTree<Key, Val>::InOrderTraverse() const
{
if (root == nullptr)
{
return;
}
std::cout << "Inorder Traverse:\n";
root->InOrderTraverse();
} template <typename Key, typename Val>
void BSTree<Key, Val>::Insert(const Key &key, const Val &val)
{
root = Inserter(root, key, val);
++node_num;
} template <typename Key, typename Val>
BSTNode<Key, Val>* BSTree<Key, Val>::Inserter(BSTNode<Key, Val> *root, const Key &key, const Val &val)
{
if (root == nullptr)
{
return new BSTNode<Key, Val>(key, val, nullptr, nullptr);
}
if (key < root->GetKey())
{
root->SetLeftChild(Inserter(root->GetLeftChild(), key, val));
}
else
{
root->SetRightChild(Inserter(root->GetRightChild(), key, val));
}
return root;
} template <typename Key, typename Val>
void BSTree<Key, Val>::Deconstructor(BSTNode<Key, Val> *root)
{
if (root == nullptr)
{
return;
}
Deconstructor(root->GetLeftChild());
Deconstructor(root->GetRightChild());
delete root;
} template <typename Key, typename Val>
BSTNode<Key, Val>* BSTree<Key, Val>::GetMinValueNode(BSTNode<Key, Val> *root) const
{
if (root->GetLeftChild() == nullptr)
{
return root;
}
else
{
return GetMinValueNode(root->GetLeftChild());
}
} template <typename Key, typename Val>
BSTNode<Key, Val>* BSTree<Key, Val>::DeleteMinValueNode(BSTNode<Key, Val> *root)
{
if (root->GetLeftChild() == nullptr)
{
return root->GetRightChild();
}
else
{
root->SetLeftChild(DeleteMinValueNode(root->GetLeftChild()));
return root;
}
} template <typename Key, typename Val>
Val BSTree<Key, Val>::Delete(const Key &key)
{
Val temp_val = Finder(root, key);
if (temp_val != Val())
{
root = Deleter(root, key);
--node_num;
}
return temp_val;
} template <typename Key, typename Val>
BSTNode<Key, Val>* BSTree<Key, Val>::Deleter(BSTNode<Key, Val> *root, const Key &key)
{
if (root == nullptr)
return nullptr;
if (key < root->GetKey())
{
root->SetLeftChild(Deleter(root->GetLeftChild(), key));
}
else if (key > root->GetKey())
{
root->SetRightChild(Deleter(root->GetRightChild(), key));
}
else
{
if (root->GetLeftChild() == nullptr)
{
BSTNode<Key, Val> *temp_node = root;
root = root->GetRightChild();
delete temp_node;
}
else if (root->GetRightChild() == nullptr)
{
BSTNode<Key, Val> *temp_node = root;
root = root->GetLeftChild();
delete temp_node;
}
else
{
BSTNode<Key, Val> *temp_node = GetMinValueNode(root->GetRightChild());
root->SetValue(temp_node->GetValue());
root->SetKey(temp_node->GetKey());
root->SetRightChild(DeleteMinValueNode(root->GetRightChild()));
delete temp_node;
}
}
return root;
} template <typename Key, typename Val>
Val BSTree<Key, Val>::Find(const Key &key) const
{
return Finder(root, key);
} template <typename Key, typename Val>
Val BSTree<Key, Val>::Finder(BSTNode<Key, Val> *root, const Key &key) const
{
if (root == nullptr)
{
return Val(); //对应的结点不存在,返回Val类型的默认值
}
if (key < root->GetKey())
{
return Finder(root->GetLeftChild(), key);
}
else if (key > root->GetKey())
{
return Finder(root->GetRightChild(), key);
}
else
{
return root->GetValue();
}
} template <typename Key, typename Val>
void BSTree<Key, Val>::SetEmpty()
{
Deconstructor(root);
root = nullptr;
node_num = ;
} template <typename Key, typename Val>
void BSTree<Key, Val>::BFS() const
{
std::queue<BSTNode<Key, Val>*> node_queue;
node_queue.push(root);
BSTNode<Key, Val> *temp_node = nullptr;
std::cout << "Breadth First Search Traverse:\n";
while (!node_queue.empty())
{
temp_node = node_queue.front();
node_queue.pop();
std::cout << "Key: " << temp_node->GetKey() << ", Value: " << temp_node->GetValue() << "\n";
if (temp_node->GetLeftChild() != nullptr)
{
node_queue.push(temp_node->GetLeftChild());
}
if (temp_node->GetRightChild() != nullptr)
{
node_queue.push(temp_node->GetRightChild());
}
}
} #endif
