【c++】搜索二叉树的模拟实现

搜索二叉树的模拟实现

k模型完整代码

#pragma once
namespace hqj1
{template<class K>struct SBTreeNode{public://这里直接用匿名对象作为缺省参数SBTreeNode(const K& key = K()):_key(key), _cleft(nullptr), _cright(nullptr){}public:K _key;SBTreeNode* _cleft;SBTreeNode* _cright;};template<class K>class SBTree{typedef SBTreeNode<K> Node;public:SBTree():_root(nullptr){}bool Insert(const K& key){if (_root == nullptr)_root = new Node(key);else{Node* cur = _root;Node* parent = nullptr;//找到要插入的位置while (cur){parent = cur;if (cur->_key < key)cur = cur->_cright;else if (cur->_key > key)cur = cur->_cleft;elsereturn false;}//连接cur = new Node(key);if (parent->_key < key)parent->_cright = cur;elseparent->_cleft = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}bool Erase(const K& key){if (_root == nullptr)return false;else{//找出要删除元素的位置,复用查找函数也行Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}//对根进行特判if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}//对不同情况进行处理//第一种是要删除的元素不在树内if (cur == nullptr)return false;else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright){//要删除的元素是叶子节点，直接删if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){//有右子树但没有左子树if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){//有左子树但没有右子树if (cur == parent->_cleft){parent->_cleft = cur->_cleft;}else{parent->_cright = cur->_cleft;}delete cur;}else{//既有左子树又有右子树//找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点Node* curRL = cur->_cright;Node* parentRL = cur;while (curRL->_cleft){parentRL = curRL;curRL = curRL->_cleft;}//交换要删除的值和要删除节点的右树最左节点的值swap(cur->_key, curRL->_key);//判断要删除的节点在其父节点的位置//操控父节点指针//有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行if (curRL == parentRL->_cleft)parentRL->_cleft = curRL->_cright;elseparentRL->_cright = curRL->_cright;delete curRL;curRL = nullptr;}return true;}}void InOrder(){_InOrder(_root);}private:void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_cleft);cout << root->_key << ' ';_InOrder(root->_cright);}Node* _root;};
}

k模型节点的定义

• 这是一个模板类，模板类型为K，代表着关键词

• 成员为：关键词、左子树指针、右子树指针

• 构造函数的参数为K类型的对象，缺省参数为匿名对象（K（）），使我们代码的通用性增强

template<class K>struct SBTreeNode{public://这里直接用匿名对象作为缺省参数SBTreeNode(const K& key = K()):_key(key), _cleft(nullptr), _cright(nullptr){}public:K _key;SBTreeNode* _cleft;SBTreeNode* _cright;};

k模型二叉搜索树类的实现

• 首先将节点类类型重定义为Node方便我们后续的使用

• 成员函数为插入、删除、查找、中序遍历

• 私有成员为节点指针_root

template<class K>class SBTree{typedef SBTreeNode<K> Node;public:SBTree():_root(nullptr){}bool Insert(const K& key){if (_root == nullptr)_root = new Node(key);else{Node* cur = _root;Node* parent = nullptr;//找到要插入的位置while (cur){parent = cur;if (cur->_key < key)cur = cur->_cright;else if (cur->_key > key)cur = cur->_cleft;elsereturn false;}//连接cur = new Node(key);if (parent->_key < key)parent->_cright = cur;elseparent->_cleft = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}bool Erase(const K& key){if (_root == nullptr)return false;else{//找出要删除元素的位置,复用查找函数也行Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}//对根进行特判if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}//对不同情况进行处理//第一种是要删除的元素不在树内if (cur == nullptr)return false;else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright){//要删除的元素是叶子节点，直接删if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){//有右子树但没有左子树if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){//有左子树但没有右子树if (cur == parent->_cleft){parent->_cleft = cur->_cleft;}else{parent->_cright = cur->_cleft;}delete cur;}else{//既有左子树又有右子树//找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点Node* curRL = cur->_cright;Node* parentRL = cur;while (curRL->_cleft){parentRL = curRL;curRL = curRL->_cleft;}//交换要删除的值和要删除节点的右树最左节点的值swap(cur->_key, curRL->_key);//判断要删除的节点在其父节点的位置//操控父节点指针//有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行if (curRL == parentRL->_cleft)parentRL->_cleft = curRL->_cright;elseparentRL->_cright = curRL->_cright;delete curRL;curRL = nullptr;}return true;}}void InOrder(){_InOrder(_root);}private:void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_cleft);cout << root->_key << ' ';_InOrder(root->_cright);}Node* _root;};

构造函数

• 将_root指针初始化为空指针即可

SBTree():_root(nullptr){}

Insert函数

• Insert函数的参数为要插入的关键字

• 首先进行判空，如果_root为空，说明此时还没有节点，我们直接给_root赋值就行

• 如果不为空，那么就需要先找到要插入的位置，我们定义cur和parent两个节点指针，cur负责寻找要插入的位置，parent负责记录cur的父亲节点，由于搜索二叉树的特性，当key值大于cur所指向节点的_key值说明要插入的位置再cur节点的右子树中，反之则在cur的左子树中，通过循环来达到目的，更新cur的同时要更新parent

• 如果遇到cur的_key和key相等的情况说明插入失败，其余情况皆为插入成功

bool Insert(const K& key){if (_root == nullptr)_root = new Node(key);else{Node* cur = _root;Node* parent = nullptr;//找到要插入的位置while (cur){if (cur->_key == key)return false;parent = cur;if (cur->_key < key)cur = cur->_cright;else if (cur->_key > key)cur = cur->_cleft;}//连接cur = new Node(key);if (parent->_key < key)parent->_cright = cur;elseparent->_cleft = cur;}return true;}

Find函数

• Find的参数为要查找的关键字

• 我们定义cur指针来找到目标节点位置，当key > cur->_key时cur要往其右子树寻找，反之则去其左子树寻找，当相等时或者cur指向空（意味着没找到）结束循环，返回cur

  Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}

Erase函数

• 该函数的参数为要删除的关键字

• 当要操作的树为空树时，直接返回失败

• 不是空树则首先找出要删除节点的位置，同样是定义cur和parent节点指针，cur负责找出要删除节点的位置，parent负责记录cur节点的父节点。利用循环结构实现，循环的结束条件为cur为空指针或者找到对应位置，若为空则说明要删除节点不在树内，直接返回失败

• 找到之后首先判断是否要操作_root指针，当parent为空时说明要操作根节点，对于根节点的不同类型进行对应的操作1. 如果整棵树只有一个节点，直接删除根节点，并将根节点置为空。2. 如果根节点没有左子树，则用右子树的根节点作为新的整棵树的根节点。3. 如果根节点没有右子树，则用左子树的根节点作为新的整棵树的根节点。4. 如果根节点既有左子树又有右子树，则当作普通节点处理（见下一点的第4小点）

• 处理完根节点问题后就改判断要删除的节点是哪种类型：1. 删除节点是叶子结点，那么我们直接删除该节点并更新其父亲节点的指针（判断要删除节点是其父情节点的左子树还是右子树，操作对应的指针）2. 有右子树但没有左子树，让其父亲的对应指针指向其右子树，并删除当前节点。3. 有左子树但没有右子树，让其父亲的对应指针指向其左子树，并删除该节点4. 既有左子树又有右子树，定义curRL负责寻找其右子树的最左节点（也就是右子树的最小节点）或者定义curLR左子树的最右节点（也就是左子树的最大节点），定义parentRL记录其父亲节点，与当前节点（cur）的值进行交换，交换完后令parentRL的对应指针指向curRL的右子树，并删除curRL所指向的节点。

• 所有过程走完后返回状态（成功或者失败）

bool Erase(const K& key){if (_root == nullptr)return false;else{//找出要删除元素的位置,复用查找函数也行Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}//对根进行特判if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}//对不同情况进行处理//第一种是要删除的元素不在树内if (cur == nullptr)return false;else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright){//要删除的元素是叶子节点，直接删if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){//有右子树但没有左子树if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){//有左子树但没有右子树if (cur == parent->_cleft){parent->_cleft = cur->_cleft;}else{parent->_cright = cur->_cleft;}delete cur;}else{//既有左子树又有右子树//找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点Node* curRL = cur->_cright;Node* parentRL = cur;while (curRL->_cleft){parentRL = curRL;curRL = curRL->_cleft;}//交换要删除的值和要删除节点的右树最左节点的值swap(cur->_key, curRL->_key);//判断要删除的节点在其父节点的位置//操控父节点指针//有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行if (curRL == parentRL->_cleft)parentRL->_cleft = curRL->_cright;elseparentRL->_cright = curRL->_cright;delete curRL;curRL = nullptr;}return true;}}

kv模型完整代码

#pragma once
namespace hqj2
{template<class K, class V>struct SBTreeNode{public:SBTreeNode(const K& key = K(), const V& value = V()):_cleft(nullptr), _cright(nullptr), _key(key), _value(value){}public:SBTreeNode* _cleft;SBTreeNode* _cright;K _key;V _value;};template<class K, class V>class SBTree{typedef SBTreeNode<K, V> Node;public:SBTree():_root(nullptr){}public:bool Insert(const K& key, const V& value){if (_root == nullptr)_root = new Node(key, value);else{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)return false;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}cur = new Node(key, value);if (cur == parent->_cleft)parent->_cleft = cur;elseparent->_cright = cur;}return true;}void InOrder(){_Inorder(_root);}Node*& Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}if (cur->_cleft == nullptr && cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cleft;elseparent->_cright = cur->_cleft;}else{Node* parntRL = nullptr;Node* curRL = cur->_cright;while (curRL->_cleft != nullptr){parntRL = curRL;curRL = curRL->_cleft;}swap(curRL->_key, cur->_key);if (curRL == parntRL->_cleft)parntRL->_cleft = curRL->_cright;elseparntRL->_cright = curRL->_cright;delete curRL;}return true;}private:void _Inorder(const Node* root){if (root == nullptr)return;_Inorder(root->_cleft);cout << root->_key << ' ' << root->_value << ' ' << endl;_Inorder(root->_cright);}Node* _root;};
}

kv模型搜索二叉树的定义

• 是模板类，模板参数是K和V

• 成员函数和k模型一模一样

template<class K, class V>class SBTree{typedef SBTreeNode<K, V> Node;public:SBTree():_root(nullptr){}public:bool Insert(const K& key, const V& value){if (_root == nullptr)_root = new Node(key, value);else{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)return false;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}cur = new Node(key, value);if (cur == parent->_cleft)parent->_cleft = cur;elseparent->_cright = cur;}return true;}void InOrder(){_Inorder(_root);}Node*& Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}if (cur->_cleft == nullptr && cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cleft;elseparent->_cright = cur->_cleft;}else{Node* parntRL = nullptr;Node* curRL = cur->_cright;while (curRL->_cleft != nullptr){parntRL = curRL;curRL = curRL->_cleft;}swap(curRL->_key, cur->_key);if (curRL == parntRL->_cleft)parntRL->_cleft = curRL->_cright;elseparntRL->_cright = curRL->_cright;delete curRL;}return true;}private:void _Inorder(const Node* root){if (root == nullptr)return;_Inorder(root->_cleft);cout << root->_key << ' ' << root->_value << ' ' << endl;_Inorder(root->_cright);}Node* _root;};

kv模型节点的定义

• 节点是模板类，模板参数为K和V

• 成员为左子树指针、右子树指针、关键字、所对应的值

• 依然以匿名对象作为缺省参数，使得我们程序更加通用

template<class K, class V>struct SBTreeNode{public:SBTreeNode(const K& key = K(), const V& value = V()):_cleft(nullptr), _cright(nullptr), _key(key), _value(value){}public:SBTreeNode* _cleft;SBTreeNode* _cright;K _key;V _value;};

Insert函数

• 该函数参数为关键字、值

• 首先判断该树有无节点，无节点则直接给_root赋值，有节点则先找要插入的位置，插入的同时改变其父亲节点所对应的指针

• 返回值为插入状态

bool Insert(const K& key, const V& value){if (_root == nullptr)_root = new Node(key, value);else{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)return false;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}cur = new Node(key, value);if (cur == parent->_cleft)parent->_cleft = cur;elseparent->_cright = cur;}return true;}

Find函数

• 和k模型的一模一样，不做赘述

Node*& Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;elsebreak;}return cur;}

Erase函数

• 和k模型的一模一样，不做赘述

 bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key)break;parent = cur;if (key > cur->_key)cur = cur->_cright;else if (key < cur->_key)cur = cur->_cleft;}if (parent == nullptr){if (cur->_cleft == nullptr && cur->_cright == nullptr){delete _root;_root = nullptr;}else if (cur->_cleft == nullptr)_root = _root->_cright;else_root = _root->_cleft;return true;}if (cur->_cleft == nullptr && cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = nullptr;elseparent->_cright = nullptr;delete cur;}else if (cur->_cleft == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cright;elseparent->_cright = cur->_cright;delete cur;}else if (cur->_cright == nullptr){if (cur == parent->_cleft)parent->_cleft = cur->_cleft;elseparent->_cright = cur->_cleft;}else{Node* parntRL = nullptr;Node* curRL = cur->_cright;while (curRL->_cleft != nullptr){parntRL = curRL;curRL = curRL->_cleft;}swap(curRL->_key, cur->_key);if (curRL == parntRL->_cleft)parntRL->_cleft = curRL->_cright;elseparntRL->_cright = curRL->_cright;delete curRL;}return true;}