c++BST树相关知识续及AVL树实现-平芜编程栈

1.BST树相关知识续

二叉树重建问题

//重建的递归接口 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 (int k = m; k <= n ; k++) { if(in[k] == pre[i]) { //找到后连接左右子树根节点 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 nullptr; }

判断是否平衡问题

//判断是否平衡的递归接口 int 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); }

二叉树平衡的条件是：左右子树高度差不超过1.

求中序遍历的倒数第k个节点

// 求中序遍历倒数第k个节点接口->将中序遍历LVR转化成RVL，就可以将原理倒数问题转化成正数 int i = 1; Node* getVal(Node *node,int k) { if(node == nullptr) { return nullptr; } Node *right = getVal(node->right_,k); //R if(right != nullptr) { return right; } //V if(i++ == k) { return node; } return getVal(node->left_,k); //L }

一下给出一些上面程序的测试程序：

// 二叉树重建问题测试函数 void test4() { BSTree<int> bst; int pre[] = {58,24,0,5,34,41,67,62,64,69,78}; int in[] = {0,5,24,34,41,58,62,64,67,69,78}; bst.rebuild(pre,0,10,in,0,10); bst.preorder(); bst.inorder(); } // 二叉树是否平衡的测试函数 void test5() { BSTree<int> bst; int arr[] = {58, 24, 67, 0, 34, 62, 69, 5, 41, 64, 78}; for (int val : arr) { bst.InsertRecurtion(val); } cout << bst.isBalance() << endl; bst.Insert(12); cout << bst.isBalance() << endl; } // 求倒数第k个节点的测试函数 void test6() { BSTree<int> bst; int arr[] = {58, 24, 67, 0, 34, 62, 69, 5, 41, 64, 78}; for (int val : arr) { bst.InsertRecurtion(val); } bst.inorder(); cout << bst.getVal(12) << endl; }

2.AVL树

(1)AVL树的程序实现

#include <iostream> #include <algorithm> using namespace std; template <typename T> class AVLTree { public: AVLTree() : root_(nullptr) {} ~AVLTree() {} // 插入 void insert(const T& val) { root_ = insert(root_, val); } // 删除 void erase(const T& val) { root_ = erase(root_, val); } private: // AVL树节点 struct Node { Node(T data = T()) : data_(data), left_(nullptr), right_(nullptr), height_(1) { } T data_; Node* left_; Node* right_; int height_; }; // 返回当前节点高度 int height(Node* node) { return node == nullptr ? 0 : node->height_; // 当一个空节点来获取当前节点高度时返回0 } // 右旋操作 Node* rightRotate(Node* node) { // 旋转操作 Node* child = node->left_; node->left_ = child->right_; child->right_ = node; // 更新节点高度 node->height_ = max(height(node->left_), height(node->right_)) + 1; // 更新当前节点高度值在比较出两个孩子节点中较大的后还要进行加1操作 child->height_ = max(height(node->left_), height(node->right_)) + 1; // 返回根节点 return child; } // 左旋操作 Node* leftRotate(Node* node) { // 旋转操作 Node* child = node->right_; node->right_ = child->left_; child->left_ = node; // 更新节点高度 node->height_ = max(height(node->left_), height(node->right_)) + 1; child->height_ = max(height(node->left_), height(node->right_)) + 1; // 返回根节点 return child; } // 左平衡操作 Node* leftBalance(Node* node) { node->left_ = leftRotate(node->left_); return rightRotate(node); } // 右平衡操作 Node* rightBalance(Node* node) { node->right_ = rightRotate(node->right_); return leftRotate(node); } // AVL树根节点指针 Node* root_; // AVL树插入递归接口 Node* insert(Node* node, const T& val) { if (node == nullptr) { return new Node(val); } if (node->data_ > val) { node->left_ = insert(node->left_, val); // 在元素插入到左子树递归回溯时，判断左子树是否太高 if (height(node->left_) - height(node->right_) > 1) { // 左子树太高，若是左子树的左子树太高则进行右旋操作 if (height(node->left_->left_) >= height(node->left_->right_)) { node = rightRotate(node); } // 左子树太高，若是左子树的右子树太高则进行左平衡操作 else { node = leftBalance(node); } } } else if (node->data_ < val) { node->right_ = insert(node->right_, val); // 在元素插入到左子树递归回溯时，判断右子树是否太高 if (height(node->right_) - height(node->left_) > 1) { // 右子树太高，若是右子树的右子树太高则进行左旋操作 if (height(node->right_->right_) >= height(node->right_->left_)) { node = leftRotate(node); } // 右子树太高，若是右子树的左子树太高则进行右平衡操作 else { node = rightBalance(node); } } } else { ; // 相等不进行插入操作 } // 在递归回溯时，因为子树添加了新的节点所以其当前节点也要更新高度 node->height_ = max(height(node->left_), height(node->right_)) + 1; return node; } // AVL树删除递归接口 Node* erase(Node* node, const T& val) { if (node == nullptr) { return nullptr; } if (node->data_ > val) { node->left_ = erase(node->left_, val); //递归回溯后，删除左子树的节点可能导致右子树偏高，不平衡 if (height(node->right_) - height(node->left_) > 1) { //右子树过高，判断右子树的左右子树谁高 if (height(node->right_->right_) >= height(node->right_->left_)) { //右子树的右子树过高 node = leftRotate(node); //当前节点失衡，所以要调整的根节点时当前节点 } else { //右子树的左子树过高 node = rightBalance(node); } } } else if (node->data_ < val) { node->right_ = erase(node->right_, val); //递归回溯后，删除右子树节点可能导致左子树偏高，不平衡 if (height(node->left_) - height(node->right_) > 1) { //左子树偏高，判断左子树的左右子树谁高 if (height(node->left_->left_) >= height(node->left_->right_)) { //左子树的左子树偏高 node = rightRotate(node); } else { //左子树的右子树偏高 node = leftBalance(node); } } } else { // 第三种情况 if (node->left_ != nullptr && node->right_ != nullptr) { // 为了避免删除前驱或后继后出现失衡的情况，我们删除子树高的那边的节点 if (height(node->left_) >= height(node->right_)) { // 左子树高，删除前驱节点 Node* pre = node->left_; while (pre->right_ != nullptr) { pre = pre->right_; } node->data_ = pre->data_; node->left_ = erase(node->left_, pre->data_); } else { // 右子树高，删除后继节点 Node* post = node->right_; while (post->left_ != nullptr) { post = post->left_; } node->data_ = post->data_; node->right_ = erase(node->right_, post->data_); } } // 第一二中情况，最多有一个孩子节点 else { if (node->left_ != nullptr) { Node* p = node->left_; delete node; return p; } else if (node->right_ != nullptr) { Node* p = node->right_; delete node; return p; } else { return nullptr; } } } //删除节点后更新当前节点的高度并返回当前节点 node->height_ = max(height(node->left_), height(node->right_)) + 1; return node; } };

注意：1.在返回当前节点为根节点的高度的函数中，当是空来获取当前节点高度时返回0.2.在更新节点高度操作中获取了该节点左右节点的高度总较大的高度后还要进行加1操作来得到该节点的高度。