241 lines
7.6 KiB
C++
241 lines
7.6 KiB
C++
#ifndef BINARYSEARCHTREE_H
|
||
#define BINARYSEARCHTREE_H
|
||
|
||
#include "BinaryTree.h"
|
||
|
||
namespace Kylin {
|
||
|
||
/**
|
||
* @brief The BinarySearchTree class. 右子树永远比左子树要小
|
||
* 1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
|
||
* 2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
|
||
* 3.任意节点的左、右子树也分别为二叉查找树。
|
||
* 4.没有键值相等的节点（no duplicate nodes）
|
||
*/
|
||
template <typename T>
|
||
class BinarySearchTree : public BinaryTree<T> {
|
||
public:
|
||
using NodeT = BinaryTreeNode<T>;
|
||
|
||
class ConstIterator : public Object {
|
||
public:
|
||
ConstIterator() = default;
|
||
ConstIterator(NodeT *pos) : pos(pos) {
|
||
}
|
||
ConstIterator &operator++() {
|
||
if (pos == nullptr) return *this;
|
||
if (pos->right) {
|
||
pos = pos->right;
|
||
while (pos->left) pos = pos->left;
|
||
} else {
|
||
while ((pos->parent != nullptr) && (dynamic_cast<NodeT *>(pos->parent)->right == pos))
|
||
pos = dynamic_cast<NodeT *>(pos->parent);
|
||
pos = dynamic_cast<NodeT *>(pos->parent);
|
||
}
|
||
return *this;
|
||
}
|
||
|
||
const T &operator*() {
|
||
return pos->value;
|
||
}
|
||
|
||
bool operator!=(const ConstIterator &iter) {
|
||
return pos != iter.pos;
|
||
}
|
||
|
||
const NodeT *pos = nullptr;
|
||
};
|
||
|
||
ConstIterator begin() const {
|
||
auto node = this->root();
|
||
while (node->left != nullptr) node = node->left;
|
||
return ConstIterator(node);
|
||
}
|
||
|
||
ConstIterator end() const {
|
||
return ConstIterator();
|
||
}
|
||
|
||
BinaryTreeNode<T> *find(const T &value) const override {
|
||
return find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), value);
|
||
}
|
||
|
||
T maximum() {
|
||
auto node = maximumOfNode(dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
|
||
if (node != nullptr)
|
||
return node->value;
|
||
else
|
||
return T();
|
||
}
|
||
|
||
T minimum() {
|
||
auto node = minimumOfNode(dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
|
||
if (node != nullptr)
|
||
return node->value;
|
||
else
|
||
return T();
|
||
}
|
||
|
||
/**
|
||
* @brief Find the maxinum node which these node are smaller than arg node.
|
||
* @param node
|
||
* @return
|
||
*/
|
||
BinaryTreeNode<T> *predecessor(BinaryTreeNode<T> *node) {
|
||
if (node == nullptr) return node;
|
||
if (node->left != nullptr) return maximumOfNode(node->left);
|
||
auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
||
while ((parent != nullptr) && (parent->left == node)) {
|
||
node = parent;
|
||
parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
||
}
|
||
return parent;
|
||
}
|
||
|
||
/**
|
||
* @brief successor Find the mininum node which these node are bigger than arg node.
|
||
* @param node
|
||
* @return
|
||
*/
|
||
BinaryTreeNode<T> *successor(BinaryTreeNode<T> *node) {
|
||
if (node == nullptr) return node;
|
||
if (node->right != nullptr) return minimumOfNode(node->right);
|
||
auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
||
if (node->right == nullptr && parent->left == node) return parent;
|
||
while ((parent != nullptr) && (parent->right == node)) {
|
||
node = parent;
|
||
parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
||
}
|
||
return parent;
|
||
}
|
||
|
||
bool insert(const T &value) {
|
||
auto node = new NodeT(value);
|
||
if (node == nullptr) return false;
|
||
return insert(node);
|
||
}
|
||
|
||
void remove(const T &value) {
|
||
BinaryTreeNode<T> *node = find(value);
|
||
if (node == nullptr) return;
|
||
auto del = remove(node, dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
|
||
if (del != nullptr) delete del;
|
||
}
|
||
|
||
protected:
|
||
/**
|
||
* @brief find
|
||
* @param node the root of sub-tree
|
||
* @param value
|
||
* @return
|
||
*/
|
||
BinaryTreeNode<T> *find(BinaryTreeNode<T> *node, const T &value) const {
|
||
if ((node == nullptr) || (node->value == value)) return node;
|
||
if (value < node->value)
|
||
return find(node->left, value);
|
||
else if (value > node->value)
|
||
return find(node->right, value);
|
||
return nullptr;
|
||
}
|
||
|
||
BinaryTreeNode<T> *find1(BinaryTreeNode<T> *node, const T &value) const {
|
||
while ((node != nullptr) && (node->value != value)) {
|
||
if (value > node->value)
|
||
node = node->right;
|
||
else if (value < node->value)
|
||
node = node->left;
|
||
}
|
||
return node;
|
||
}
|
||
|
||
BinaryTreeNode<T> *maximumOfNode(BinaryTreeNode<T> *node) {
|
||
if (node == nullptr) return node;
|
||
while (node->right != nullptr) node = node->right;
|
||
return node;
|
||
}
|
||
|
||
/**
|
||
* @brief minimumOfNode Find the maxinum node of the sub-tree which root is arg node.
|
||
* @param node
|
||
* @return
|
||
*/
|
||
BinaryTreeNode<T> *minimumOfNode(BinaryTreeNode<T> *node) {
|
||
if (node == nullptr) return node;
|
||
while (node->left != nullptr) node = node->left;
|
||
return node;
|
||
}
|
||
|
||
/**
|
||
* @brief insert Insert node to the sub-tree which root is arg node.
|
||
*/
|
||
bool insert(NodeT *node) {
|
||
if (node == nullptr) return false;
|
||
auto n = reinterpret_cast<NodeT **>(&(this->m_root));
|
||
NodeT *parent = nullptr;
|
||
while (*n != nullptr) {
|
||
parent = *n;
|
||
n = (node->value <= (*n)->value) ? &((*n)->left) : &((*n)->right);
|
||
}
|
||
node->parent = parent;
|
||
*n = node;
|
||
return true;
|
||
}
|
||
|
||
/**
|
||
* @brief remove
|
||
* @param node The tree which we want remove
|
||
* @param tree
|
||
* @return
|
||
*/
|
||
BinaryTreeNode<T> *remove(BinaryTreeNode<T> *node, BinaryTreeNode<T> *tree) {
|
||
auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
||
if ((node->left == nullptr) || (node->right == nullptr)) {
|
||
}
|
||
|
||
if ((node->left == nullptr) && (node->right == nullptr)) { // node没有左右子树
|
||
if (parent->left == node)
|
||
parent->left = nullptr;
|
||
else
|
||
parent->right = nullptr;
|
||
} else if ((node->left != nullptr) && (node->right == nullptr)) {
|
||
if (parent->left == node)
|
||
parent->left = node->left;
|
||
else
|
||
parent->right = node->left;
|
||
} else if ((node->left == nullptr) && (node->right != nullptr)) {
|
||
if (parent->left == node)
|
||
parent->left = node->right;
|
||
else
|
||
parent->right = node->right;
|
||
} else {
|
||
auto n = successor(node);
|
||
n->left = node->left;
|
||
if (parent->left == node)
|
||
parent->left = node->right;
|
||
else
|
||
parent->right = node->right;
|
||
}
|
||
return node;
|
||
/*
|
||
BinaryTreeNode<T> *del = nullptr;
|
||
BinaryTreeNode<T> *n = nullptr;
|
||
if((node->left==nullptr)||(node->right==nullptr)) del = node;
|
||
else del = successor(node);
|
||
|
||
if(del->left!=nullptr) n = del->left;
|
||
else n =del->right;
|
||
|
||
if(n != nullptr) n->parent = del->parent;
|
||
|
||
if(del->parent==nullptr) tree = n;
|
||
else if (del == del->parent->left) del->parent->left=n;
|
||
else del->parent->right=n;
|
||
if(del!=node) tree->value=del->value;
|
||
return del;
|
||
*/
|
||
}
|
||
};
|
||
} // namespace Kylin
|
||
|
||
#endif // BINARYSEARCHTREE_H
|