数据结构【二叉搜索树、leetcode刷题】

目录

二叉搜索树性质

Insert非递归版本

递归版本：类private内部定义，因为需要显示传参root

Erase非递归版本

Erase递归版本

Find非递归版本

Find递归版本

 构造/析构/拷贝构造/operator=

二叉搜索树性能

LeetCode刷题

根据二叉树创建字符串

二叉树的层序遍历

二叉树的最近公共祖先

二叉搜索树与双向链表_牛客题霸_牛客网

从前序与中序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树

二叉树前序非递归遍历

二叉树中序非递归遍历

二叉树后序非递归遍历

---

二叉搜索树性质

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

注意事项：

1.搜索树不允许重复冗余数据

2.搜索二叉树中序遍历是有序+去重

3.二叉搜索树不支持修改

4.二叉搜索树也称二叉排序树

二叉搜索树结构

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

二叉搜索树的查找

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

最多查找高度次，到空还没找到，这个值不存在

Insert非递归版本

返回值为bool，防止冗余数据

 树为空，则直接新增节点，赋值给root指针

 树不空，按二叉搜索树性质查找插入位置，插入新节点

bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;//值在树中存在，错误
			}
			
		}
		cur = new Node(key);  //单纯写一句这个错误，cur只是局部变量，并没有挂到树中
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
		
	}

递归版本：类private内部定义，因为需要显示传参root

此处递归插入需要加上&， 如果不加引用此处是局部变量，还需要链接父亲，