二叉搜索树的介绍、模拟实现二叉搜索树、leetcode---根据二叉树创建字符串、leetcode---二叉树的最近公共祖先等的介绍

---

前言

二叉搜索树的介绍、模拟实现二叉搜索树、leetcode—根据二叉树创建字符串、leetcode—二叉树的最近公共祖先等的介绍

---

一、二叉搜索树的介绍

• 如上图所示，搜索二叉树就是比当前节点大的存放在右子树，比当前节点小的存放在左子树中。

二、模拟实现二叉搜索树

#pragma oncetemplate<class K>
struct BSTreeNode
{BSTreeNode(const K& key): _left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};template <class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& tree){_root = copy(tree._root);}BSTree<K>& operator=(BSTree<K> tree){swap(_root, tree._root);return *this;}~BSTree(){Destroy(_root);}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 false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}}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 = _root->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}else if(cur->_right == nullptr) // 找到的节点右树为空{if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else // 左右节点都不为空{// 找左子树的最大节点（最右）Node* parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(leftMax->_key, cur->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;}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;}void InOrder(){_InOrder(_root);cout << endl;}// 递归插入bool InsertR(const K& key){return _InsertR(_root, key);}// 递归删除bool EraseR(const K& key){return _EraseR(_root, key);}Node* findR(const K& key){return _findR(_root, key);}private:// 递归查找Node* _findR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key < key){_findR(root->_right, key);}else if (root->_key > key){_findR(root->_left, key);}else{return root;}}// copy	Node* copy(Node* root){if (root == nullptr){return nullptr;}Node* copyroot = new Node(root->_key);copyroot->_left = copy(root->_left);copyroot->_right = copy(root->_right);return copyroot;}// 递归析构void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}// 递归版本删除bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){_EraseR(root->_right, key);}else if (root->_key > key){_EraseR(root->_left, key);}else{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(leftMax->_key, root->_key);return _EraseR(root->_left, key);}delete del;return true;}}// 递归版本插入数据bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){_InsertR(root->_right, key);}else if(root->_key > key){_InsertR(root->_left, key);}else{return false;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root;
};

测试：

#include <iostream>
using namespace std;#include "BinarySearchTree.h"void test1()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(8);t.InOrder();t.Erase(4);t.InOrder();t.Erase(6);t.InOrder();t.Erase(7);t.InOrder();
}void test2()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t.InsertR(e);}t.InOrder();t.EraseR(8);t.InOrder();t.EraseR(4);t.InOrder();t.EraseR(6);t.InOrder();t.EraseR(7);t.InOrder();
}void test3()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t.InsertR(e);}t.InOrder();BSTree<int> t1(t);t1.InOrder();BSTree<int> t2;t2 = t1;t2.InOrder();}void test4()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t.InsertR(e);}t.InOrder();cout << t.find(10) << endl;cout << t.findR(100) << endl;}
int main()
{test1();test2();test3();test4();return 0;
}

三、leetcode—根据二叉树创建字符串

leetcode—根据二叉树创建字符串

class Solution {
public:string tree2str(TreeNode* root) {if(root == nullptr){return "";}string str;str += to_string(root->val);if(root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}if(root->right){str += '(';str += tree2str(root->right);str += ')';}return str;}
};

四、leetcode—二叉树的最近公共祖先

leetcode—二叉树的最近公共祖先

class Solution {
public:bool Find(TreeNode* root, TreeNode* x){if(root == nullptr){return false;}return root == x || Find(root->left,x) || Find(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr){return nullptr;}if(root == p || root == q){return root;}bool pInLeft, pInRight, qInLeft, qInRight;pInLeft = Find(root->left, p);pInRight = !pInLeft;qInLeft = Find(root->left, q);qInRight = !qInLeft;if(pInLeft && qInLeft){return lowestCommonAncestor(root->left, p, q); }else if(pInRight && qInRight){return lowestCommonAncestor(root->right, p, q); }else{return root;} }
};

---

总结

二叉搜索树的介绍、模拟实现二叉搜索树、leetcode—根据二叉树创建字符串、leetcode—二叉树的最近公共祖先等的介绍