企业官网建设流程全解析

关于做花茶网站的策划书,在招聘网站做销售工资高吗,织梦网站安全,软件开发工程师有前途吗1.BST树相关知识续二叉树重建问题//重建的递归接口Node* _rebuild(int pre[],int i,int j,int in[],int m,int n){if(ij || mn){return nullptr;}//将前序的序列的第一个节点创建为根节点Node* node new Node(pre[i]);//在中序中找到当前节点为根节点的左右子树的中序…1.BST树相关知识续二叉树重建问题//重建的递归接口 Node* _rebuild(int pre[],int i,int j,int in[],int m,int n) { if(ij || mn) { return nullptr; } //将前序的序列的第一个节点创建为根节点 Node* node new Node(pre[i]); //在中序中找到当前节点为根节点的左右子树的中序序列确定个数转化到左右子树的前序序列 for (int k m; k n ; k) { if(in[k] pre[i]) { //找到后连接左右子树根节点 node-left_ _rebuild(pre,i1,i(k-m),in,m,k-1); node-right_ _rebuild(pre,i(k-m)1,j,in,k1,n); return node; } } return nullptr; }判断是否平衡问题//判断是否平衡的递归接口 int isBalance(Node *node,int l,bool flag) { if(node nullptr) { return l; } int left isBalance(node-left_,l1,flag); if(!flag) { return left; } int right isBalance(node-right_,l1,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() { BSTreeint 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() { BSTreeint 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() { BSTreeint 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操作来得到该节点的高度。(2)相关知识AVL树是二叉平衡搜索树是对原BST树有着平衡要求的树主要就是对不满足平衡要求的节点进行四种旋转操作来转化为满足平衡。