C++进阶：搜索树

1. 二叉搜索树
- 1.1 二叉搜索树的结构
- 1.2 二叉搜索树的接口及其优点与不足
- 1.3 二叉搜索树自实现
- - 1.3.1 二叉树结点结构
  - 1.3.2 查找
  - 1.3.3 插入
  - 1.3.4 删除
  - 1.3.5 中序遍历
2. 二叉树进阶相关练习
- 2.1 根据二叉树创建字符串
- 2.2 二叉树的层序遍历I
- 2.3 二叉树层序遍历II
- 2.4 二叉树最近公共祖先结点
- 2.5 二叉树搜索与双向链表
- 2.6 从前序与中序遍历序列构造二叉树
- 2.7 从中序与后序遍历序列构造二叉树
- 2.8 二叉树前序遍历（非递归）
- 2.9 二叉树中序遍历（非递归）
- !!!3.10 二叉树后序遍历（非递归）

1. 二叉搜索树

1.1 二叉搜索树的结构

搜索二叉树中的所有结点都满足
<1> 若左子树不为空，则其所有结点的键值都小于父结点
<2> 若右子树不为空，则其所有结点的键值都大于父节点
<3> 左右子树都为二叉搜索树

在这里插入图片描述

1.2 二叉搜索树的接口及其优点与不足

搜索二叉树的功能接口
<1> 数据插入（Insert）
<2> 数据删除（Erase）
<3> 数据查寻（Find）
<4> 中序遍历（InOrder）

二叉搜索树的优点：
<1> 正如其名，此种数据存储结构，尤其擅长数据搜索，其进行数据搜索的效率极高。
<2> 在其结构为近似完全二叉树或满二叉树的情况时，其的搜索效率可以达到O( $l o g N$ )
<3> 当以中序遍历的方式遍历整棵搜索树时，得到的数据即为升序序列

在这里插入图片描述

二叉搜索树的不足：
<1> 根据二叉搜索树的插入逻辑，当数据以完全升序或降序插入时，会使得二叉树退化为单枝结构，此种结构下其搜索效率也退化为O(N)

在这里插入图片描述

1.3 二叉搜索树自实现

1.3.1 二叉树结点结构

搜索树结点：由左右孩子结点指针与key组成
搜索树：由根节点与类方法构成

template<class T>
struct BinarySearchNode
{
	typedef BinarySearchNode<T> BSNode;

	BSNode* _left;
	BSNode* _right;
	T _key;

	BinarySearchNode(T key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class T>
class BinarySearchTree
{
public:
	typedef BinarySearchNode<T> BSNode;
	
	//查找
	bool Find(T key);

	//插入
	bool Insert(T key);

	//删除
	bool Erase(T key);

	//中序遍历
	void InOrder();

private:
	BSNode* _root = nullptr;
};

1.3.2 查找

查找实现：在一颗搜索树中搜寻一个数据是否存在
查找逻辑：
<1> 若查找值小于当前结点的key值，向左搜寻，向左孩子查找
<2> 若查找值大于当前结点的key值，向右搜寻，向右孩子查找
<3> 查找遍历至空结点，则证明搜索树中不存在此值

//非递归
bool Find(T key)
{
	BSNode* cur = _root;

	while (cur)
	{
		if (key < cur->_key)
		{
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else
		{
			return true;
		}
	}

	return false;
}

//递归
bool _FindR(BSNode* cur, T key)
{
	if (cur == nullptr)
	{
		return false;
	}

	if (key < cur->_key)
	{
		return _FindR(cur->_left, key);
	}
	else if (key > cur->_key)
	{
		return _FindR(cur->_right, key);
	}
	else
	{
		return true;
	}

	//补全返回路径
	assert(true);
	return -1;
}

bool FindR(T key)
{
	return _FindR(_root, key);
}

1.3.3 插入

搜寻插入位置：
<1> key小向左
<2> key大向右
<3> 直至遍历到空
<1> 若遇key相同的结点，停止插入，返回false
<2> 遍历至空，创建结点，链接结点

//非递归
bool Insert(T key)
{
	//特殊处理根结点插入
	if (_root == nullptr)
	{
		_root = new BSNode(key);
		return true;
	}

	BSNode* cur = _root;
	BSNode* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}

	//确定插入位置
	if (key < parent->_key)
	{
		parent->_left = new BSNode(key);
	}
	else
	{
		parent->_right = new BSNode(key);
	}

	return true;
}

//递归
bool _InsertR(BSNode*& cur, T key)
{
	//存在单子树的情况，导致段错误
	//传引用
	if (cur == nullptr)
	{
		cur = new BSNode(key);

		return true;
	}

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

	assert(true);
	return false;
}

bool InsertR(T key)
{
	if (_root == nullptr)
	{
		_root = new BSNode(key);
		
		return true;
	}

	return _InsertR(_root, key);
}

1.3.4 删除

删除结点后，不能破坏搜索树的结构
删除不同类型结点的场景，删除逻辑：
<1> 叶子结点，直接删除，父节点链接指针置空
<2> 单子树结点，托孤，即，将自己的子树链接给父结点
<3> 双子树结点，寻找key值最接近的结点（左子树的最右结点，右子树的最左结点），值替换被删除的结点，而后删除被替换的结点

叶子结点
单子树结点
双子树结点

//非递归
bool Erase(T key)
{
	BSNode* cur = _root;
	BSNode* parent = nullptr;
	while (cur)
	{
		//查找到删除结点的位置
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//找到了
		{
			//叶子结点与单子树结点的删除
			//可以合并共用一套逻辑
			if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树
			{
				//根结点特殊处理
				if (cur == _root)
				{
					if (cur->_left)
					{
						_root = cur->_left;
					}
					else
					{
						_root = cur->_right;
					}

					delete cur;
				}
				else//普通结点
				{
					//托孤
					if (cur->_left)//左单子树
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
						delete cur;
					}
					else//右单子树/叶子节点
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
						delete cur;
					}
				}

				return true;
			}
			else//双子树
			{
				//寻找右子树的最左结点
				BSNode* RightParent = cur;
				BSNode* RightMin = cur->_right;

				while (RightMin->_left)
				{
					RightParent = RightMin;
					RightMin = RightMin->_left;
				}

				//值替换
				cur->_key = RightMin->_key;

				//删除被替换结点
				//删除结点的左孩子一定为空，所以按照右子树结点处理
				//托孤
				if (RightMin == RightParent->_left)
				{
					RightParent->_left = RightMin->_right;
				}
				else
				{
					RightParent->_right = RightMin->_right;
				}

				//删除
				delete RightMin;

				return true;
			}
		}
	}

	//未找到
	return false;
}

//递归
bool _EraseR(BSNode*& cur, T key)
{
	if (cur == nullptr)
	{
		return false;
	}

	//寻找删除结点
	if (key < cur->_key)
	{
		return _EraseR(cur->_left, key);
	}
	else if (key > cur->_key)
	{
		return _EraseR(cur->_right, key);
	}
	else//找到了
	{
		//使用传引用后，对操作的优化
		if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树结点
		{
			BSNode* del = cur;
			if (cur->_left)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
			delete del;

			return true;
		}
		else//双子树
		{
			//寻找右子树的最左结点
			BSNode* RightMin = cur->_right;
			while (RightMin->_left)
			{
				RightMin = RightMin->_left;
			}

			//值替换
			cur->_key = RightMin->_key;

			//值替换后，删除结点传值改变
			//转化为单子树删除，调用单子树删除处理
			_EraseR(cur->_right, cur->_key);
		}
	}

	assert(true);
	return false;
}

1.3.5 中序遍历

void _InOrder(BSNode* cur)
{
	if (cur == nullptr)
	{
		return;
	}

	//左根右
	_InOrder(cur->_left);
	cout << cur->_key << " ";
	_InOrder(cur->_right);
}

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

2. 二叉树进阶相关练习

2.1 根据二叉树创建字符串

题目信息：

题目连接：
根据二叉树创建字符串

class Solution 
{
public:
    void _tree2str(string& str, TreeNode* cur)
    {
        if(cur == nullptr)
        {
            return;
        }
        //字符串转字符串stoi（整形），stod（浮点型）
        str += to_string(cur->val);

        //除左空右不空的情况外，其余省略
        if(cur->left || cur->right)
        {
            str += "(";
            _tree2str(str, cur->left);
            str += ")";
        }

        if(cur->right)
        {
            str += "(";
            _tree2str(str, cur->right);
            str += ")";
        }
    }

    string tree2str(TreeNode* root) 
    {
        string ret;
        //递归
        _tree2str(ret, root);

        return ret;
    }
};

2.2 二叉树的层序遍历I

题目信息：

题目连接：
二叉树的层序遍历I
思路：levelsize计数

class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        //levelsize计数
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        int levelsize = 1;
        q.push(root);
        //可能为空树
        if(root == nullptr)
        {
            return ret;
        }

        while (!q.empty())
        {
            vector<int> count;
            while (levelsize--)
            {
                //记录
                TreeNode* top = q.front();
                q.pop();
                count.push_back(top->val);
                //插入新结点
                if (top->left)
                    q.push(top->left);
                if (top->right)
                    q.push(top->right);
            }
            levelsize = q.size();
            ret.push_back(count);
        }

        return ret;
    }
};

2.3 二叉树层序遍历II

题目信息：

题目连接：
二叉树层序遍历II
思路：反转自上至下的层序遍历

class Solution 
{
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        //全部压栈，无法判断层
        //得出自上至下的序列，然后逆置
        vector<vector<int>> ret;
        if(root == nullptr)
        {
            return ret;
        }
        queue<TreeNode*> q;
        int levelsize = 1;
        q.push(root);
        while(!q.empty())
        {
            vector<int> count;
            while(levelsize--)
            {
                TreeNode* cur = q.front();
                q.pop();
                count.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            levelsize = q.size();
            ret.push_back(count);
        }

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

2.4 二叉树最近公共祖先结点

题目信息：

二叉树最近公共祖先结点
思路：
<1> 方法1：p与q一定分别在祖先结点的左侧与右侧，祖先结点可能是自己
<2> 方法2：栈记录遍历路径，路径上的所有祖先结点

//方法1：
class Solution 
{
public:
    bool SearchNode(TreeNode* cur, TreeNode* search)
    {
        if(cur == nullptr)
        {
            return false;
        }

        if(cur == search)
        {
            return true;
        }

        return SearchNode(cur->left, search) || SearchNode(cur->right, search);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        bool qInleft = false;
        bool qInright = false;
        bool pInleft = false;
        bool pInright = false;
        TreeNode* cur = root;
        while(cur)
        {
            //可能最近祖先结点是自己
            if(cur == p)
            {
                pInleft = pInright = true;
            }
            else if(SearchNode(cur->left, p))
            {
                pInleft = true;
                pInright = false;
            }
            else
            {
                pInright = true;
                pInleft = false;
            }

            if(cur == q)
            {
                qInleft = qInright = true;
            }
            else if(SearchNode(cur->left, q))
            {
                qInleft = true;
                qInright = false;
            }
            else
            {
                qInright = true;
                qInleft = false;
            }

            if((pInleft && qInright) || (pInright && qInleft))
                break;
            else if(pInleft && qInleft)
                cur = cur->left;
            else
                cur = cur->right;
        }

        return cur;
    }
};

//方法2：
class Solution 
{
public:
    bool PreOrder(TreeNode* cur, TreeNode* search, stack<TreeNode*>& count)
    {
        if(cur == nullptr)
        {
            return false;
        }

        count.push(cur);

        if(cur == search)
        {
            return true;
        }

        if(!PreOrder(cur->left, search, count) && !PreOrder(cur->right, search, count))
        {
            count.pop();
        }
        else
        {
            return true;
        }

        assert(true);
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //栈记录遍历路径,所有祖先结点
        //到达指定结点的路径只有一条
        //深度优先遍历
        stack<TreeNode*> p_st;
        stack<TreeNode*> q_st;
        PreOrder(root, p, p_st);
        PreOrder(root, q, q_st);

        //路径上的相交结点
        while(p_st.size() != q_st.size())
        {
            if(p_st.size() > q_st.size())
                p_st.pop();
            else
                q_st.pop();
        }

        while(p_st.top() != q_st.top())
        {
            p_st.pop();
            q_st.pop();
        }

        return p_st.top();

    }
};

2.5 二叉树搜索与双向链表

题目信息：

题目链接：
二叉搜索树与双向链表
思路：记录前置结点，中序遍历，注意调整指针链接的时机

class Solution 
{
public:
	void InOrder(TreeNode* cur, TreeNode*& pre)
	{
		if(cur == nullptr)
		{
			return;
		}

		InOrder(cur->left, pre);
		cur->left = pre;
		if(pre)
			pre->right = cur;
		
		pre = cur;
		InOrder(cur->right, pre);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		if(pRootOfTree == nullptr)
		{
			return nullptr;
		}

		TreeNode* pre = nullptr;
		InOrder(pRootOfTree, pre);
		while(pRootOfTree->left)
		{
			pRootOfTree = pRootOfTree->left;
		}

		return pRootOfTree;
    }
};

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

题目信息：

题目链接：
从前序与中序遍历序列构造二叉树
思路：根据根分割出左右子树，区域分割，引用

class Solution 
{
public:
    TreeNode* buildNode(vector<int>& preorder, vector<int>& inorder, int& i, int left, int right)
    {
        if(left > right)
        {
            return nullptr;
        }

        //在中序中找到需构建结点
        int j = 0;
        while(inorder[j] != preorder[i])
        {
            j++;
        }

        //根左右
        //构建
        TreeNode* newnode = new TreeNode(preorder[i++]);
        //分割域，判断，构建左孩子
        newnode->left = buildNode(preorder, inorder, i, left, j - 1);
        //分割域，判断，构建右孩子
        newnode->right = buildNode(preorder, inorder, i, j + 1, right);
        
        return newnode;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int i = 0;
        return buildNode(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

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

题目信息：

题目链接：
从中序与后序遍历序列构造二叉树
思路：区域分割判断，引用，逆向遍历，根右左

class Solution 
{
public:
    TreeNode* buildNode(vector<int>& inorder, vector<int>& postorder, int& i, int left, int right)
    {
        if(left > right)
        {
            return nullptr;
        }

        int j = 0;
        while(inorder[j] != postorder[i])
        {
            j++;
        }

        TreeNode* newnode = new TreeNode(postorder[i--]);
        newnode->right = buildNode(inorder, postorder, i, j + 1, right);
        newnode->left = buildNode(inorder, postorder, i, left, j - 1);

        return newnode;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        //逆向遍历，根右左
        int i = postorder.size() - 1;
        return buildNode(inorder, postorder, i, 0, postorder.size() - 1);
    }
};

2.8 二叉树前序遍历（非递归）

题目信息：

题目链接：
二叉树前序遍历
思路：根左右，插入右子树时就将根删除，栈记录

class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        //非递归，前序遍历，根左右
        vector<int> ret;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                ret.push_back(cur->val);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }

        return ret;
    }
};

2.9 二叉树中序遍历（非递归）

题目信息：

题目链接：
二叉树中序遍历
思路：插入时机，删除时插入，左右根

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        //中序，左右根
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        //插入时机，删除时插入
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);

            cur = top->right;
        }

        return ret;
    }
};

!!!3.10 二叉树后序遍历（非递归）

题目信息：

题目链接：
二叉树后续遍历
思路：二次遍历时删除，删除时插入，何时删除

class Solution 
{
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        //左右根
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(cur || !st.empty())
        {
            //左
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            
            //根
            TreeNode* top = st.top();
            //cur = st.top();
            if(top->right == nullptr || pre == top->right)
            //if(cur->right == nullptr || pre == cur->right)
            {
                st.pop();
                pre = top;
                //pre = cur;
                ret.push_back(top->val);
                //ret.push_back(cur->val);
            }
            else
            {
                //右，死循环
                cur = top->right;
                //cur调整错误
                //cur = cur->right;
            }
        }

        return ret;
    }
};