二叉树进阶 之 【模拟实现二叉搜索树】(递归、非递归实现查找、插入、删除功能)

目录

1.非递归版本

1.1查找

1.2插入

1.3删除

2.递归版本

2.1查找

2.2插入

2.3删除

1.非递归版本

1.1查找

从根节点开始，根据键值的比较进行查找

所给键值比节点键值大，到节点的右子树去寻找；

所给键值比节点键值小，到节点的左子树去寻找；

所给键值与节点键值相等，就找到了(二叉搜索树默认不存在两个及以上键值相同的节点)

找不到，就会来到空树

Node* find(const K& key){
	//树为空
    if (!_root)
		return nullptr;
    //树不为空
	Node* cur = _root;
	while (cur){
		if (key > cur->_key){
			cur = cur->_right;
		}
		else if (key < cur->_key){
			cur = cur->_left;
		}
		else{
			return cur;
		}
	}
    //找不到
	return nullptr;
}

从根节点开始循环查找，节点为空就是循环结束条件

1.2插入

从根节点开始，根据键值的比较寻找合适的插入位置

所给键值比节点键值大，到节点的右子树去寻找；

所给键值比节点键值小，到节点的左子树去寻找；

一定能找到， 且插入位置是空树

bool Insert(const K& key){
	//树为空
	if (!_root){
		_root = new Node(key);
		return true;
	}
	//树不为空，根据key的大小找到相应位置
	//插入位置为空，提前保存其父亲节点
	Node* parent = _root;
	Node* cur = _root;
	while(cur){
		if (key > cur->_key){
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key){
			parent = cur;
			cur = cur->_left;
		}
		else//相等的值不能插入{
			return false;
		}
	}
	//找到恰当位置了，插入位置一定为空
	Node* newnode = new Node(key, value);
	if (key > parent->_key)
		parent->_right = newnode;
	else
		parent->_left = newnode;

	return true;
}

树不为空时，位置的查找与前面讲的节点的查找差不多，只是，找到插入位置后，我们不仅需要创建一个新节点来存储键值，更重要的是还要将所创建的节点连接到树上去，所以

需要提前保存当前节点的父亲节点，(父亲节点初始值可与当前节点一致)

//这种插入方式就有风险
if (parent->_left == cur)
	parent->_left = newnode;
else 
	parent->_right = newnode;

正如注释所言，这种插入方式有风险，因为如果父亲节点没有孩子节点，所插入节点的插入位置就会受这种方式影响，

如：parent 键值 为 10 ，cur(新创建的节点) 键值 为 14，就会误将其插入到左子树去

所以找到恰当位置之后，我们还需根据键值的比较来链接新的节点

1.3删除

从根节点开始，根据键值的比较寻找要删除的树节点

所给键值比节点键值大，到节点的右子树去寻找；

所给键值比节点键值小，到节点的左子树去寻找；

找不到就来到空树

	//非递归删除
	bool Erase(const K& key){
		//树为空
		if (!_root)
			return false;
		//树不为空
		//删除某节点时，需要更新其父亲节点的指针指向
		Node* parent1 = _root;
		Node* cur = _root;
		while (cur){
			if (key > cur->_key){
				parent1 = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key){
				parent1 = cur;
				cur = cur->_left;
			}
			else//找到了{
				//...
			}
		}
		//没找到
		return false;
	}

树不为空时，以循环的方式查找要删除的节点，节点为空就是循环结束条件

当然，找到节点之后我们还不能直接删除该节点，还需更新其父亲节点的链接关系

所以需要提前保存其父亲节点的初始值(父亲节点初始值可与当前节点一致)

删除需要分情况进行讨论

//保存删除节点
Node* del = cur;
//先更新节点链接关系
//左为空
if (!cur->_left){
	if (parent1 == cur){
		_root = cur->_right;
	}

	//此更新关系建立在parent1和 cur 不同的情况下
	if (parent1->_left == cur){
		parent1->_left = cur->_right;
	}
	else{
		parent1->_right = cur->_right;
	}
}//右为空
else if (!cur->_right){
	//...
}//都不为空，替换法
else
{    
	//找右子树的最小节点
	Node* parent2 = cur;
	Node* rightMin = cur->_right;
	while (rightMin->_left){
		parent2 = rightMin;
		rightMin = rightMin->_left;
	}
	//交换关键值
    swap(rightMin->_key, cur->_key);
	//此时删除目标变为右子树的最小节点
	del = rightMin;
	//更新其关系,左为空
	if (parent2->_left == rightMin)
			parent2->_left = rightMin->_right;
	else
		    parent2->_right = rightMin->_right;
}

delete del;
return true;

(1)将更新父亲节点的链接关系作为主要内容，提前保存删除节点 cur ，后续一步删除

(2)左为空与右为空代码逻辑类似，这里只讲左为空(都为空已被涵盖)

正如删除键值为 6 的树节点一样，只需让父亲节点指向右子树，但是，

需要判断键值为 6 的树节点属于父亲节点的左子树还是右子树

判断完成之后，将父亲节点的左或右孩子指针指向树节点的右子树即可，

if (parent1->_left == cur){
		parent1->_left = cur->_right;
	}
	else{
		parent1->_right = cur->_right;
	}

但最坑的是 ，如果根节点就是要删除的节点这套逻辑行不通！办法是：

将根节点调整为根节点的右子树的根节点

if (parent1 == cur){
		_root = cur->_right;
	}

(3)删除节点左右子树都存在，使用替换法删除

只能选用删除节点的左子树的最大键值或右子树的最小键值与删除节点的键值进行替换操作

因为这样才能满足二叉搜索树的定义

替换之后，需要删除的节点就变为了左子树或右子树中键值与删除节点替换前的键值一致的节点，所以，在查找左子树的最大键值或右子树的最小键值仍需保存当前节点的父亲节点以便后续链接关系的更新，当然，此时的链接关系得到简化(要么左为空，要么右为空)

2.递归版本

2.1查找

根据键值大小，前序遍历进行递归查找，最小子问题是空树

当前节点不是要查找的节点就先去左子树查找，再到右子树查找

Node* findR(const K& key){
	return _findR(_root, key);
}

Node* _findR(Node* root, const K& key){
	if (!root)
		return nullptr;

	if (key > root->_key){
		return _findR(root->_right, key);
	}
	else if (key < root->_key){
		return _findR(root->_left, key);
	}
	else{
		return root;
	}
}

为了外界能够简单的传参(只传入键值)，递归嵌套调用子函数

2.2插入

仍是前序遍历根据键值的比较找到插入的恰当位置

恰当位置就是树为空的位置

bool InsertR(const K& key){
	return _InsertR(_root, key, value);
}

bool _InsertR(Node*& root, const K& key){
	if (!root){
		root = new Node(key);
		return true;
	}

	if (key > root->_key){
		return _InsertR(root->_right, key);
	}
	else if (key < root->_key){
    	return _InsertR(root->_left, key);
	}
	else{
		return false;
	}
}

为了外界能够简单的传参(只传入键值)，递归嵌套调用子函数

查找逻辑以及默认二叉搜索树的节点键值都不同非递归版本都有提及，这里着重讲解

父亲节点连接关系的更新

节点指针的引用可谓是神之一笔

树为空，root 是 _root 的别名，root 指向 新创建的节点，_root 也指向 新创建的节点。

树不为空，且找到恰当位置后， 当前栈帧中的 root 是 前一个栈帧中 root->left 或 root->right

的别名，引用就形成了天然的连接关系，此时只需要将 当前栈帧中的 root 指向 新创建的节点即可将新创建的节点链接到树中

2.3删除

仍是前序遍历根据键值的比较找到要删除的节点

bool EraseR(const K& key){
	return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key){
	//找不到的情况就是节点值为空
	if (!root)
		return false;

	if (key > root->_key){
		return _EraseR(root->_right, key);
	}
	else if (key < root->_key){
		return _EraseR(root->_left, key);
	}
	else//找到了{
		Node* del = root;
        //更新链接关系
        if (!root->_left){
			//root是父亲节点某一指针的别名
			//直接修改root即可
			root = root->_right;
        }
        else if (!root->_right){
			root = root->_left;
        }
        else{
		    //找到左子树的最大节点
			Node* leftMax = root->_left;
			while (leftMax->_right){
					leftMax = leftMax->_right;
			}
			//交换值
			swap(leftMax->_key, root->_key);
			//此时删除目标变为leftMax		
			return _EraseR(root->_left, key);
        }
        delete del;
        return true;
	}
}

为了外界能够简单的传参(只传入键值)，递归嵌套调用子函数

查找逻辑以及默认二叉搜索树的节点键值都不同非递归版本都有提及，这里着重讲解

父亲节点连接关系的更新，节点的删除可一笔带过

节点指针的引用仍是神之一笔

无需提前保存父亲节点

(1)没有孩子节点或者只有一个孩子节点

找到删除节点后， 当前栈帧中的 root 是 前一个栈帧中 root->left 或 root->right

的别名，引用就形成了天然的连接关系，此时只需要将 当前栈帧中的 root 指向 它的左子树或右子树即可将它的左子树或者右子树链接到树中

(2)当删除节点有两个孩子节点时，仍是选择  替换法进行删除

这里的精妙之处在于递归调用函数进行删除操作

替换的是左子树的最大键值，那就只能去左子树中删除

替换的是右子树的最小键值，那就只能去右子树中删除

而不能从当前这棵中去删除，因为会找不到！！