【C++】二叉搜索树

二叉搜索树

【概念】

二叉搜索树（BST，BinarySearchTree）又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

先定义二叉树的结构

struct BSTreeNode
{K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

利用二叉树结构模拟实现二叉搜索树

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

1. 二叉搜索树的插入

插入时要先判断_root是不是空节点

其次插入一个数(key)时要判断头结点与key的大小，大则往右树走，小则左树。再依次遍历判断。

最后判断要在父节点的哪个位置

	bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}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 {return true;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else {parent->_left = cur;}return true;}

2. 搜索二叉树

本质上就是遍历

	bool 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 true;}}return false;}

3. 中序遍历

中序遍历就是左子树，根，右子树。

采用递归思想。

	void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

当我们在main函数使用中序遍历时，发现传递不了root根节点。这时，我们把_InOrder设置为私有函数。在公有函数中引用私有函数_InOrder

	void InOrder(){_InOrder(_root);cout << endl;}

4. 删除二叉树

删除二叉树中的节点

如果删除叶子节点，直接删除

如果删除只有一个子节点的节点，则需要把他的父节点与他的子节点链接

如果删除有两个节点的节点，则需要找一个节点替代左子树的最大或右子树最小

无子节点或者有一个子节点可以归为一类，我们只需把有一个子节点的节点或者没有节点的节点他们的孩子，交给节点的父节点来看管就行

if (cur->_left == nullptr)
{if (parent == nullptr){_root = cur->_right;}else {if (parent->_left == cur){parent->_left = cur->_right;}else {parent->_right = cur->_right;}}delete cur;return true;
}
else if (cur->_right == nullptr)
{if (parent == nullptr){_root = cur->_left;}else {if (parent->_left == cur){parent->_left = cur->_left;}else {parent->_right = cur->_left;}}delete cur;return true;
}

删除两个子节点的节点

首先要找到右子树最小的节点与要删除的节点进行交换。

这里我们定义一个cur就是要删除的节点，和rightMin右子树最小的节点，和rightMinP右子树最小的节点的父节点。

					Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;

删除二叉树总代码实现

bool Erase(int 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{// 删除//0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else {if (parent->_left == cur){parent->_left = cur->_right;}else {parent->_right = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else {if (parent->_left == cur){parent->_left = cur->_left;}else {parent->_right = cur->_left;}}delete cur;return true;}else {// 2 个孩子// 右子树的最大节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;
}