c++数据结构--BST树

一.什么是BST树

BST树称作二叉搜索树(Binary Search Tree)或者二叉排序树(Binary Sort Tree),它或者是一颗空树;或者是具有下列性质的二叉树:
1、若左子树不为空,则左子树上所有节点的值均小于它的根节点的值
2、若右子树不为空,则右子树上所有节点的值均大于它的根节点的值
3、左右子树也分别满足二叉搜索树性质

特点:每一个节点都满足 左孩子的值(不为空)<父节点的值<右孩子的值(不为空)

BST树的基本框架

template<typename T, typename Compare = less<T>> class BSTtree { public: BSTtree(Compare comp= Compare()) :root(nullptr) ,comp(comp) { } ~BSTtree() { if (root == nullptr) { return; } queue<Node*>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; } stack<Node*>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; } stack<Node*>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; } stack<Node*>s1; stack<Node*>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; } queue<Node*>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.区间元素搜索问题

搜索处于i，j之间的所以树上的节点的数据。

（1）非递归实现

//BST树区间元素搜索问题[i,j](非递归实现) void n_findValues(vector<T>& vec, int i, int j) { if (root == nullptr) { return; } stack<Node*>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(vector<T>& vec, int i, int j) { findValues(vec, i, j, root); } void findValues(vector<T>& 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(BSTtree<T, 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); }