一.什么是BST树BST树称作二叉搜索树(Binary Search Tree)或者二叉排序树(Binary Sort Tree),它或者是一颗空树;或者是具有下列性质的二叉树:1、若左子树不为空,则左子树上所有节点的值均小于它的根节点的值2、若右子树不为空,则右子树上所有节点的值均大于它的根节点的值3、左右子树也分别满足二叉搜索树性质特点:每一个节点都满足 左孩子的值(不为空)父节点的值右孩子的值(不为空)BST树的基本框架templatetypename T, typename Compare lessT class BSTtree { public: BSTtree(Compare comp Compare()) :root(nullptr) ,comp(comp) { } ~BSTtree() { if (root nullptr) { return; } queueNode*q; q.push(root); while (!q.empty()) { Node* front q.front(); q.pop(); if (front-left ! nullptr) { q.push(front-left); } if (front-right ! nullptr) { q.push(front-right); } delete front; } } private: struct Node { Node(T data T()) :m_data(data) , left(nullptr) , right(nullptr) { } T m_data; Node* left; Node* right; }; Node* root; Compare comp; };二.BST树常见操作的实现1.插入1非递归实现void n_insert(const T val) { if (root nullptr) { root new Node(val); return; } Node* parent nullptr; Node* cur root; while (cur ! nullptr) { if (comp(val, cur-m_data)) { parent cur; cur cur-left; } else if (comp(cur-m_data, val)) { parent cur; cur cur-right; } else//不插入相同的值 return; } if (comp(val, parent-m_data)) { parent-left new Node(val); } else { parent-right new Node(val); } }2递归实现//递归插入 void insert(const T val) { root insert(root, val); } Node* insert(Node* node, const T val) { if (node nullptr) { return new Node(val); } if (node-m_data val) { return node; } else if (comp(node-m_data, val)) { node-right insert(node-right, val); } else { node-left insert(node-left, val); } return node; }2.删除1非递归实现void n_remove(const T val) { if (root nullptr) { return; } Node* parent nullptr; Node* cur root; while (cur ! nullptr) { if (comp(val, cur-m_data)) { parent cur; cur cur-left; } else if (comp(cur-m_data, val)) { parent cur; cur cur-right; } else { break; } } if (cur nullptr) return; if (cur-left ! nullptr cur-right ! nullptr) { parent cur; Node* pre cur-left; while (pre-right ! nullptr) { parent pre; pre pre-right; } cur-m_data pre-m_data; cur pre; } Node* child cur-left; if (child nullptr) { child cur-right; } if (parent nullptr) { root child; } else { if (parent-left cur) { parent-left child; } else { parent-right child; } } delete cur; }2递归实现void remove(const T val) { root remove(root, val); } Node* remove(Node* node, const T val) { if (node nullptr) return nullptr; if (node-m_data val) { if (node-left ! nullptr node-right ! nullptr) { Node* pre node-left; while (pre-right ! nullptr) { pre pre-right; } node-m_data pre-m_data; node-left remove(node-left, pre-m_data); } else { if (node-left ! nullptr) { Node* left node-left; delete node; return left; } else if (node-right ! nullptr) { Node* right node-right; delete node; return right; } else { delete node; return nullptr; } } } else if (comp(node-m_data, val)) { node-right remove(node-right, val); } else { node-left remove(node-left, val); } return node; }3.查找1非递归实现bool n_find(T val)const { Node* cur root; while (cur ! nullptr) { if (comp(val, cur-m_data)) { cur cur-left; } else if (comp(cur-m_data, val)) { cur cur-right; } else { return true; } } return false; }2递归实现bool find(const T val) { return find(root, val); } bool find(Node* node, const T val) { if (node nullptr) { return false; } if (node-m_data val) { return true; } else if (comp(node-m_data, val)) { return find(node-right, val); } else { return find(node-left, val); } }4.前序遍历1非递归实现void n_preOrder() { if (root nullptr) { return; } stackNode*s; s.push(root); while (!s.empty()) { Node* top s.top(); s.pop(); cout top-m_data ; if (top-right ! nullptr) { s.push(top-right); } if (top-left ! nullptr) { s.push(top-left); } } }2递归实现//递归前序遍历VLR void preOrder() { preOrder(root); } void preOrder(Node* node) { if (node ! nullptr) { cout node-m_data ; preOrder(node-left); preOrder(node-right); } }5.中序遍历1非递归实现void n_inOrder() { if (root nullptr) { return; } stackNode*s; Node* cur root; while (cur ! nullptr) { s.push(cur); cur cur-left; } while (!s.empty()) { Node* top s.top(); s.pop(); cout top-m_data ; cur top-right; while (cur ! nullptr) { s.push(cur); cur cur-left; } } }2递归实现//递归中序遍历LVR(中序遍历是升序) void inOrder() { inOrder(root); } void inOrder(Node* node) { if (node ! nullptr) { inOrder(node-left); cout node-m_data ; inOrder(node-right); } }6.后序遍历1非递归实现void n_postOrder() { if (root nullptr) { return; } stackNode*s1; stackNode*s2; s1.push(root); while (!s1.empty()) { Node* top s1.top(); s1.pop(); s2.push(top); if (top-left ! nullptr) { s1.push(top-left); } if (top-right ! nullptr) { s1.push(top-right); } } while (!s2.empty()) { Node* cur s2.top(); cout cur-m_data ; s2.pop(); } }2递归实现void postOrder() { postOrder(root); } void postOrder(Node* node) { if (node ! nullptr) { postOrder(node-left); postOrder(node-right); cout node-m_data ; } }7.层序遍历1非递归实现void n_levelOrder() { if (root nullptr) { return; } queueNode*q; q.push(root); while (!q.empty()) { Node* front q.front(); cout front-m_data ; q.pop(); if (front-left ! nullptr) { q.push(front-left); } if (front-right ! nullptr) { q.push(front-right); } } }2递归实现//求BST树的层数 int level() { return level(root); } int level(Node* node) { if (node nullptr) { return 0; } int left level(node-left); int right level(node-right); return left right ? left 1 : right 1; } void levelOrder() { int h level(); for (size_t i 0; i h; i) { levelOrder(root, i); } } void levelOrder(Node* node, int i) { if (node nullptr) return; if (i 0) { cout node-m_data ; return; } levelOrder(node-left, i - 1); levelOrder(node-right, i - 1); }三.BST树的经典问题1.区间元素搜索问题搜索处于ij之间的所以树上的节点的数据。1非递归实现//BST树区间元素搜索问题[i,j](非递归实现) void n_findValues(vectorT vec, int i, int j) { if (root nullptr) { return; } stackNode*s; Node* cur root; while (cur ! nullptr) { s.push(cur); cur cur-left; } while (!s.empty()) { Node* top s.top(); s.pop(); if (top-m_data i top-m_data j) { vec.push_back(top-m_data); } cur top-right; while (cur ! nullptr) { s.push(cur); cur cur-left; } } }2递归实现void findValues(vectorT vec, int i, int j) { findValues(vec, i, j, root); } void findValues(vectorT vec, int i, int j, Node* node) { if (node ! nullptr) { if (node-m_data i) { findValues(vec, i, j, node-left); } if (node-m_data 10 node-m_data 50) { vec.push_back(node-m_data); } if (node-m_data j) { findValues(vec, i, j, node-right); } } }2.判断一颗二叉树是否是BST树bool isBSTtree() { Node* node nullptr; return isBSTtree(root, node); } bool isBSTtree(Node* node, Node* node2) { if (node nullptr) { return true; } if (!isBSTtree(node-left, node2)) { return false; } if (node2 ! nullptr) { if (node-m_data node2-m_data) { return false; } } node2 node; isBSTtree(node-right, node2); }3.判断一颗二叉树是否是另一颗二叉树的子树bool isChildtree(BSTtreeT, Compare bst) { if (bst.root nullptr) return true; Node* cur root; while (cur ! nullptr) { if (cur-m_data bst.root-m_data) { break; } else if (comp(cur-m_data, bst.root-m_data)) { cur cur-right; } else { cur cur-left; } } if (cur nullptr) return false; return isChildtree(cur, bst.root); } bool isChildtree(Node* node, Node* child) { if (node nullptr child nullptr) return true; if (node nullptr) return false; if (child nullptr) return true; if (node-m_data ! child-m_data) { return false; } return isChildtree(node-left, child-left) isChildtree(node-right, child-right); }4.求一个二叉树上两个节点的最近公共祖先节点int getLCA(int val1, int val2) { Node* node getLCA(root, val1, val2); if (node nullptr) throw NO LCA; else { return node-m_data; } } Node* getLCA(Node* node, int val1, int val2) { if (node nullptr) return nullptr; if (node-m_data val1 node-m_data val2) { return getLCA(node node-right, val1, val2); } else if (node-m_data val1 node-m_data val2) { return getLCA(node node-left, val1, val2); } else { return node; } }5.二叉树的镜像翻转问题//二叉树镜像翻转问题 void mirror() { mirror(root); } void mirror(Node* node) { if (node nullptr) return; Node* p nullptr; p node-left; node-left node-right; node-right p; mirror(node-left); mirror(node-right); }6.二叉树的镜像对称问题//二叉树镜像对称问题 bool mirror02() { return mirror02(root-left, root-right); } bool mirror02(Node* left, Node* right) { if (left nullptr right nullptr) return true; if (left nullptr || right nullptr) return false; if (left-m_data ! right-m_data) return false; return mirror02(left-left, right-right) mirror02(left-right, right-left); }7.利用先序遍历与中序遍历重建二叉树Node* _rebuild(int pre[], int i, int j, int in[], int m, int n) { if (i j || m n) return nullptr; Node* node new Node(pre[i]); for (size_t k m; k n; k) { if (pre[i] in[k]) { node-left _rebuild(pre, i 1, i (k - m), in, m, k - 1); node-right _rebuild(pre, i (k - m) 1, j, in, k 1, n); return node; } } return node; } //根据前序遍历和中序遍历的数组重建二叉树 void rebuild(int pre[], int i, int j, int in[], int m, int n) { root _rebuild(pre, i, j, in, m, n); }8.判断一颗二叉树是否是平衡树AVL树//判断一颗二叉树是否是平衡树 bool isBalance() { int l 0; bool flag true; isBalance(root, l, flag); return flag; } bool isBalance(Node* node,int l, bool flag) { if (node nullptr) { return l; } int left isBalance(node-left, l 1, flag); if (!flag) return left; int right isBalance(node-right, l 1, flag); if (!flag) return right; if (abs(left - right) 1) { flag false; } return max(left, right); }9.求二叉树中序遍历倒数第k个节点//求中序遍历倒数第k个节点 int getVal(int k) { int num 0; Node* node getVal(root, k,num); if (node nullptr) { string err no NO.; err k; throw err; } else { return node-m_data; } } Node* getVal(Node* node, int k,int num) { if (node nullptr) { return nullptr; } Node* left getVal(node-right, k,num); if (left ! nullptr) return left; num; if (num k) { return node; } return getVal(node-left, k,num); }