搜索二叉树

搜索二叉树本质:左节点比我小 右节点比我大

节点类

BSTreeNode:给自身节点封装一个类 用这个类来添加节点的操作
我们写的是一个key.value型的搜索二叉树

template<class K,class V>
struct BSTreeNode
{typedef BSTreeNode<K,V> Node;Node* _left;//左孩子Node* _right;//右孩子K _key;//建V _value;//值
};

BSTreeNode(节点类的构造)

BSTreeNode(const K& key, const V& value): _left(nullptr), _right(nullptr), _key(key), _value(value){}

BSTree(功能实现类)

因为我们实现的是key，value型的所以模版是K,V
类中变量

template<class K,class V>
class BSTree
{typedef BSTreeNode<K,V> Node;
private:Node* _root;
};

Insert(插入)

首先:要判断是否为空树 如果是空树直接new一个新节点当根节点
还有就是建立一个cur让其等于根节点
用一个parent记录cur的父节点
用他们中的key值比较谁大谁小
小的往左走，大的往右走
走到合适位置，new一个新节点插入到树中

bool Insert(const K& key,const V& value)
{if (_root == nullptr)//树为空的情况{_root = new Node(key,value);return true;}Node* parent = nullptr;//因为cur是局部变量函数走完会销毁，所以增加一个指针 链接curNode* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key,value);if (parent->_key < key)//大就链右边 小链左边{parent->_right = cur;}else{parent->_left = cur;}return true;
}

Erase(删除)

看代码中的注释

bool Erase(const K& key)
{Node* parent = nullptr;//记录父节点Node* cur = _root;//从根开始找while (cur){//大了往右 小了往左if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//找到节点{if (cur->_left == nullptr)//左树为空{if (cur == _root)//头节点没有左子树{_root = cur->_right;}else//不为根节点{if (cur == parent->_right)//自身为父节点的右节点{//让自己的右节点成为父节点的右节点parent->_right = cur->_right;}else//左节点{//让我的右节点成为父节点的左节点parent->_left = cur->_right;}}delete cur;//删掉自己这个节点return true;}else if (cur->_right == nullptr)//右树为空{if (cur == _root)//头节点没有右子树{_root = cur->_left;}else{//让自己的左节点代替自己if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;//删除节点return true;}else{//左右都不为空//找到右数中最小的代替自己Node* rightMin = cur->_right;//不能为空 如果为空的话 //要删的是头节点 会让空的_left指向他 会崩溃Node* father = cur;//定义这个为rightMin的父节点while (rightMin->_left)//找右树中的最小{father = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//交换值//如果 相等 那么才让他的父节点左指向他自身节点的右if (rightMin == father->_left){father->_left = rightMin->_right;}else//不想等就是说明的头节点 那么就要让头节点的右指向他的右{father->_right = rightMin->_right;}delete rightMin;return true;}}}return false;
}

Find(查找这个节点)

大了往右 小了往左 找到返回节点 没找到返回空

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;
}