學數據結構到現在寫的最久的一部分，簡單總結一下這一周
1.考慮到未來考試要求，實現語言從java換成了C++，沒想到意外的順利
2.沒別的了，干就完了
3.代碼肯定有錯誤的地方，雖然我自認為是完美主義者，但都是為了效率沒辦法啦

//! *指針變量，例如：int b = *p； *代表取值運算符，返回地址指向的值（不是地址本身，p是地址本身） //! 做個比喻*p就是找到地址為p的箱子，然后*打開箱子取出里面的東西，然后把東西賦值給b //! 定義指針變量，例如：int *p = &a; 中的int*p只是表明p是一個指針變量，變量類型為int*（int類型指針變量），不要和別的*p整混 //! &代表取地址符，&a就是拿到變量a的地址//! **指針變量，也稱二重指針，例如：int *p = a； int **q = &p； //! 二重指針就是指指向一個指針類型變量的地址的指針，這里p存放a的地址，q存放的就是p的地址 此時 *q = p； //! 同理int ***m = &q； 稱為三重指針，就是存放二重指針q的地址的，此時 *m = q； //! *p = a = **q = *（*q）= ***m = *（*（*m）） ； 知道了上面的原理這個不難推出來把//! 結構體指針變量，例如：Node *node = new Node(10); 此時訪問node的成員變量element有兩種等同的方法： //! (*node).element 或 node -> element ，所謂 ->運算符就是結構體指針訪問其指向的結構體成員變量專用的，這樣就不用*node了 //! node此時就是一個結構體指針變量，普通結構體訪問成員變量只需要node.element就可以了，但此時node是指針，我們是new出來的//! 遞歸：在函數和子過程內部，直接或間接地調用自己（比如在函數定義內部出現了自己的函數名） //! 遞歸思想：把問題轉化成同類的規模更小的子問題，先解決子問題，再通過相同的求解步驟逐步解決更高層次的問題，最終得到最終解 //! 公式表達：x0 -> （x1 = f(x0)） -> x2 = f(x1) -> x3 = f(x2) ...->xn = f（x（n-1）） xn為最終解 （文字表達好抽象，不如畫圖看視頻） //! 因為我們是把大問題逐步分解為小問題，再由最小小問題開始逐步回到大問題，所以我們需要記住大問題和中間小問題，因為棧具有記憶性，先進后出，遞歸就是應用了系統棧 //! 棧內部：{f(x(n-1)),f(x(n-2))....f(x1),f(x0)} 問題從f(x(n-1))開始依次push進去，然后從數組尾部依次pop即使是一個有序數組，插入和刪除元素的時間復雜度也只能做到O（n） //而使用二叉搜索樹，插入刪除和搜索的最壞時間復雜度均可優化至O(logn)//二叉搜索樹：一棵二叉樹，任何結點的左子結點小于該節點，右子節點大于該節點 //二叉搜索樹沒有索引index（下標）一說，因為索引和元素的大小和位置都無關，沒有意義//前序遍歷（Preorder Traversal） //訪問順序：根結點，前序遍歷左子樹，前序遍歷右子樹//中序遍歷（Inorder Traversal） //訪問順序：中序遍歷左子樹，根節點，中序遍歷右子樹（先右后左也可以，只要根節點在中間訪問，都叫中序遍歷，同理前序后序） //二叉搜索樹進行中序遍歷，會使元素以升序或降序呈現//后序遍歷（Postorder Traversal） //訪問順序：后序遍歷左子樹，后序遍歷右子樹，根節點//層序遍歷（Levelorder Traversal） //訪問順序：一層一層訪問結點//頭文件版的二叉搜索樹，直接在頭文件里寫類的定義就行//!二叉搜索樹的添加刪除，搜索操作的時間復雜度跟樹的高度有關，為O（h）（相比線性表的O（n）搜索以及添加的話） //! 滿二叉樹的高度基本是logn，所以滿的二叉搜索樹的時間復雜度也接近O（logn） //! 但是如果二叉搜索樹建立的順序，輸入是一個有序數組的話，比如1，2，3，4，5，。。。n這樣建立的二叉搜索樹高度就等于n //! 也就是最壞時間復雜度等于O（n），被稱為二叉搜索樹退化為鏈表 //! 所以我們要盡力維持時間復雜度在O（h）而不是O（n）//! 平衡的概念：二叉樹結點數量固定，左右子樹高度越接近就越平衡，完全二叉樹和滿二叉樹是最平衡的//! 所以如何改進我們的二叉搜索樹？？ //! 1.改變添加刪除的元素順序，簡介控制樹的高度 2.改善添加元素后的二叉樹，使之更平衡 //! 我們設計的二叉搜索樹是給別人用的，所以添加刪除的順序，我們無法改變，所以我們只能從添加后的二叉樹的平衡改進入手 //! 一顆達到適度平衡的二叉搜索樹 ，我們稱之為平衡二叉搜索樹 比如：AVL樹，紅黑樹 //! AVL樹是以其發明者命名的，發明者是一個蘇聯科學家，AVL樹是最早發明的自平衡二叉搜索樹之—，搜索、添加、刪除的時間復雜度是O(logn)O(logn) //! 平衡因子：該結點平衡因子等于左子樹高度減去右子樹高度，絕對值小于等于1，即超過1或小于-1，即為失衡，就要自動調整#include <iostream> #include "queue" #include "stack" #include <string> #include <algorithm> using namespace std;class Node { public:int element;Node *left;Node *right;Node *parent;Node(){this->element = 0;this->left = nullptr;this->right = nullptr;this->parent = nullptr;}Node(int element){this->element = element;this->left = nullptr;this->right = nullptr;this->parent = nullptr;} };class BinarySearchTreesZH { private:int size;public://我這里把根節點寫成public了，主要后面寫一些函數可以方便點Node *root = nullptr;void add(int element); //添加元素Node *searchBST(int element, Node *root); //二叉樹搜索bool isEmpty(); //是否為空void clear(); //清空void clear(Node *node); //清空以node為根結點的子樹void preorderTraversal(Node *root); //前序遍歷遞歸void inorderTraversal(Node *root); //中序遍歷遞歸void postorderTraversal(Node *root); //后序遍歷遞歸void levelorderTraversal(Node *root); //層序遍歷（隊列）void preorderTraversalNoRecursion(Node *root); //前序遍歷迭代（模擬棧）void inorderTraversalNoRecursion(Node *root); //中序遍歷迭代（模擬棧）void postorderTraversalNoRecursion(Node *root); //后序遍歷迭代（模擬棧）int height(Node *node); //求樹高度迭代int heightNoRecursion(Node *node); //求樹高度迭代（層序遍歷）bool isCompleteTree(Node *node); //完全性檢驗（層序遍歷）Node *invertTreePreOrder(Node *node); //翻轉二叉樹（前序遍歷）Node *invertTreeInOrder(Node *node); //翻轉二叉樹（中序遍歷）Node *invertTreePostOrder(Node *node); //翻轉二叉樹（后序遍歷）Node *invertTreeLeverOrder(Node *node); //翻轉二叉樹（層序遍歷）Node *searchNode(int key, Node *node); //查找結點（前序遍歷）Node *predecessor(Node *node); //找前驅結點Node *successor(Node *node); //找后繼節點void remove(Node *node); //刪除節點 };bool BinarySearchTreesZH::isEmpty() {if (size == 0){return true;}else{return false;} }void BinarySearchTreesZH::add(int element) {Node *node = new Node(element); // 新new一個結點在堆區，存儲輸入的數值//! 要記得new傳送回來的是對象在堆區的地址，一定要用指針變量來接收if (root == nullptr){ //如果樹目前為空，則使之成為根結點root = node;size++;return;}//通過二叉搜索樹的特性，查找需要插入的位置Node *nextCompare = root;//代表需要進行比較的結點，比它大則移動到它的右結點，比他小就移動到它的左結點，進行下一次比較Node *parent = root;//記錄移動前的nextCompare，即nextCompare循環到null時，它的父結點，也是插入位置的父結點while (nextCompare != nullptr){parent = nextCompare;if (node->element < nextCompare->element){nextCompare = nextCompare->left;}else if (node->element > nextCompare->element){nextCompare = nextCompare->right;}else if (node->element = nextCompare->element) //若已有相同元素，直接return{return;}}if (node->element < parent->element) //與找到的父結點進行比較，并插入{parent->left = node;}else if (node->element > parent->element){parent->right = node;}//這里不用delete nextCompare 和parent ，因為不是new出來的，隨著成員函數執行完就自動銷毀了size++;return; } //二叉搜索樹搜索元素 Node *BinarySearchTreesZH::searchBST(int element, Node *root) {if (root == nullptr){return nullptr;}Node *node = root;while (node != nullptr){if (element == node->element){return node;}if (element < node->element){node = node->left;}if (element > node->element){node = node->right;}}cout<<"Not Found"<<endl;return nullptr; }//前序遍歷，遞歸版本，三個遍歷的遞歸寫法思想都一致，唯一區別就是在什么時候訪問根結點 //畫個圖和棧更好理解，這里不多解釋 void BinarySearchTreesZH::preorderTraversal(Node *node) {if (node == nullptr){return;}cout << node->element << " ";preorderTraversal(node->left);preorderTraversal(node->right); } //! 簡單理解遞歸遍歷二叉樹，把遍歷整個二叉樹這個大問題，轉化為遍歷根節點的無數個子樹 //! 因為遍歷一個只有三個結點的二叉樹的解決方式是一樣的，比如中序遍歷，先訪問左子節點，根節點就在中間訪問，然后訪問右子結點 //! 而遞歸只不過是把訪問子結點這個過程變成了先訪問一顆以這個子結點為根結點的三個結點的子樹的過程，然后把過程結果返回，當作該子結點的訪問結果 //! 深入理解就是棧的思想，畫圖//中序遍歷，遞歸版本 void BinarySearchTreesZH::inorderTraversal(Node *node) {if (node == nullptr){return;}inorderTraversal(node->left);cout << node->element << " "; //! 就是根節點在中間訪問，先訪問左子樹，然后根節點，然后右子樹，對于子樹的訪問也是一樣在中間訪問根節點inorderTraversal(node->right); }//后序遍歷，遞歸版本 void BinarySearchTreesZH::postorderTraversal(Node *node) {if (node == nullptr){return;}postorderTraversal(node->left);postorderTraversal(node->right);cout << node->element << " "; }//! 層序遍歷，很重要，精髓在于對于隊列的應用 void BinarySearchTreesZH::levelorderTraversal(Node *node) {queue<Node *> list; //創建結構體指針隊列，數據類型Node*，但是層序遍歷不用指針也可以if (node == nullptr){return;}else{list.push(node); //把根節點push進去}while (list.size() != 0) //只要隊列不為空就一直出隊進隊{cout << list.front()->element << " ";//這里就是把隊首的元素的左右子節點進隊，然后彈出隊首元素，就可以把二叉樹中所有節點一層一層的按次序進隊和出隊//還是畫圖比較好理解if (list.front()->left != nullptr){list.push(list.front()->left);}if (list.front()->right != nullptr){list.push(list.front()->right);}list.pop();} }//! 前序遍歷的非遞歸版本，精髓在于用棧模擬遞歸的過程，但實際進棧出棧順序與遞歸并不一樣， //! 比較抽象，建議畫圖理解，比較重要 void BinarySearchTreesZH::preorderTraversalNoRecursion(Node *node) {stack<Node *> stk;if (node == nullptr){return;}stk.push(node);while (stk.size() != 0){Node *top = stk.top();cout << stk.top()->element << " ";stk.pop();//! 注意前序遍歷是中左右，出棧順序是先左后右，進棧就要先右后左if (top->right != nullptr){stk.push(top->right);}if (top->left != nullptr){stk.push(top->left);}} }//! 中序遍歷，非遞歸版，跟上一個前序遍歷的非遞歸版比，思路相同，但是實現方法和過程完全不同 //! 比較抽象，依然建議畫圖理解 //! 巧妙地改變了入棧順序實現了中序遍歷 void BinarySearchTreesZH::inorderTraversalNoRecursion(Node *node) {if (node == nullptr){return;}stack<Node *> stk;stk.push(node);while (stk.size() != 0){while (node->left != nullptr){stk.push(node->left);node = node->left;}//! 整體思路為遇到根節點，就遍歷左子樹的所有左節點，并全部入棧，然后挨個出棧，//! 出棧中檢測是否有右節點，如果有則以右節點為根結點，再次遍歷全部左結點，全部入棧，然后挨個出棧Node *top = stk.top();cout << top->element << " ";stk.pop();if (top->right != nullptr){node = top->right;stk.push(top->right);}} }//! 后序遍歷，非遞歸版，可以通過改變前序遍歷非遞歸版中左右結點的入棧順序，和翻轉數組的想法實現 void BinarySearchTreesZH::postorderTraversalNoRecursion(Node *node) {if (node == nullptr){return;}string s = " ";stack<Node *> stk;stk.push(node);Node *top = stk.top();while (stk.size() != 0){top = stk.top();stk.pop();s = s + to_string(top->element) + " ";if (top->left != nullptr){ //! 整體思路和前序遍歷相同，入棧順序自己想想前序中左右，和后序左右中，就明白了stk.push(top->left);}if (top->right != nullptr){stk.push(top->right);}}reverse(s.begin(), s.end()); //reverse函數反轉字符串cout << s; }//! 求二叉樹的高度,遞歸版本 //! 遞歸的精髓就在于，把大問題分解為解答過程相同的小問題 //! 既然我們要求根節點的高度，根節點的高度又等于其子節點的最大高度加一 //! 那么問題就轉化為了求每個節點及其子節點的高度，而最小問題就是葉節點的子節點為空，高度為0 int BinarySearchTreesZH::height(Node *node) {int nodeHeight = 0;int leftSonHeight = 0; //代表左子節點高度int rightSonHeight = 0; //代表右子節點高度if (node == nullptr){ //如果到了空結點，則其高度為0nodeHeight = 0;return nodeHeight;}leftSonHeight = height(node->left);rightSonHeight = height(node->right);if (leftSonHeight >= rightSonHeight) //當前結點的高度等于其左右子節點最大高度+1{nodeHeight = leftSonHeight + 1;}else{nodeHeight = rightSonHeight + 1;}return nodeHeight; }//! 求二叉樹的高度，迭代版本 //! 所謂二叉樹的高度就是二叉樹有多少層，所以在層序遍歷里加一個層數計數就可以了 //! 但這個層數計數反倒是難想，其實在層序遍歷的隊列中，上一層全部出隊后，下一層有多少元素，就是隊列的size（） int BinarySearchTreesZH::heightNoRecursion(Node *node) {queue<Node *> list; //創建結構體指針隊列，數據類型Node*，但是層序遍歷不用指針也可以if (node == nullptr){return 0;}else{list.push(node); //把根節點push進去}int height = 0;int nextCengNum = 1; //! 第一層元素數為1int j = 0; //! 循環計數器，每一層循環nextCengNum次就會清零，并高度+1while (list.size() != 0) //只要隊列不為空就一直出隊進隊{//這里就是把隊首的元素的左右子節點進隊，然后彈出隊首元素，就可以把二叉樹中所有節點一層一層的按次序進隊和出隊//還是畫圖比較好理解if (list.front()->left != nullptr){list.push(list.front()->left);}if (list.front()->right != nullptr){list.push(list.front()->right);}list.pop();j++;if (j == nextCengNum){height++;nextCengNum = list.size();j = 0;}}return height; }//! 檢驗二叉樹是否為完全二叉樹 //! 層序遍歷每一個結點，有三種情況，分情況討論 bool BinarySearchTreesZH::isCompleteTree(Node *node) {if (node == nullptr){return false;}queue<Node *> list;list.push(node);while (list.size() != 0) //! 大遍歷{Node *front = list.front();if (front->left != nullptr && front->right != nullptr) //! 若該結點同時擁有左右子結點，則繼續出隊入隊{list.pop();if (front->left != nullptr){list.push(front->left);}if (front->right != nullptr){list.push(front->right);}}else if (front->left == nullptr && front->right != nullptr) //! 若該結點沒有左只有右，直接返回false{return false;}else //! 若該結點沒有左右子結點，或只有左子結點，則子節點入隊后，隊列該結點后面所有結點都是葉結點（沒有子節點）{if (front->left != nullptr){list.push(front->left);}list.pop(); //把當前符合規則的這個先pop出去while (list.size() != 0) //檢驗后面的是不是都是葉結點，若不是return false{front = list.front();if (front->left != nullptr || front->right != nullptr){return false;}list.pop();}}}//每次檢驗都通過，返回truereturn true; }//! 二叉樹的翻轉：本質就是二叉樹的遍歷的應用 //! 以任意形式遍歷二叉樹的每一個結點，訪問每一個結點的同時調換其左右子樹 //! 中序遍歷額外注意一下調換后的參數問題 Node *BinarySearchTreesZH::invertTreePreOrder(Node *node) {if (node == nullptr){return node;}Node *tmp = node->left;node->left = node->right;node->right = tmp;invertTreePreOrder(node->left); //!這里遍歷的主要目的是遍歷過程中的副作用。即翻轉invertTreePreOrder(node->right); //! 所以這里不return，要靈活運用遍歷框架return node; } Node *BinarySearchTreesZH::invertTreeInOrder(Node *node) {if (node == nullptr){return node;}invertTreeInOrder(node->left);Node *tmp = node->left;node->left = node->right;node->right = tmp;//! 中序遍歷的特殊點：由于調換了左右子樹，所以第二個遞歸參數應該是現在的左子樹才是原來的右子樹invertTreeInOrder(node->left);return node; } Node *BinarySearchTreesZH::invertTreePostOrder(Node *node) {if (node == nullptr){return node;}invertTreePostOrder(node->left);invertTreePostOrder(node->right);Node *tmp = node->left;node->left = node->right;node->right = tmp;return node; } Node *BinarySearchTreesZH::invertTreeLeverOrder(Node *node) {if (node == nullptr){return node;}queue<Node *> list;list.push(node);while (list.size() != 0){Node *front = list.front();list.pop();Node *tmp = front->left;front->left = front->right;front->right = tmp;if (front->left != nullptr){list.push(front->left);}if (front->right != nullptr){list.push(front->right);}}return node; }//! 查找某個結點的前驅或后繼結點（要求結點要有parent指針） //! 前驅結點定義：中序遍歷中的前一個結點，而不是二叉樹結構中的上一個母結點 Node *BinarySearchTreesZH::predecessor(Node *node) {if (node == nullptr){return node;}//! 前驅結點是左子樹中的最右結點if (node->left != nullptr){node = node->left;while (node->right != nullptr){node = node->right;}return node;}else{while (node->parent != nullptr && node->parent->right != node){node = node->parent;}//! 此時到這里有兩種可能//! node->parent = nullptr(即沒有前驅結點) 或 node->parent ->right = node（即前驅結點是node->parent）//! 無論哪種 直接返回parent都可以return node->parent;} } //! 查找某個結點的后繼結點（要求結點要有parent指針） //! 后繼結點定義：中序遍歷中的后一個結點 Node *BinarySearchTreesZH::successor(Node *node) {if (node == nullptr){return node;}//! 前驅結點是右子樹中的最左結點if (node->right != nullptr){node = node->right;while (node->left != nullptr){node = node->left;}return node;}else{while (node->parent != nullptr && node->parent->left != node){node = node->left;}//! 此時到這里有兩種可能//! node->parent = nullptr(即沒有前驅結點) 或 node->parent ->left = node（即前驅結點是node->parent）//! 無論哪種 直接返回parent都可以return node->parent;} }//! 刪除結點 void BinarySearchTreesZH::remove(Node *node) {if (node->left != nullptr && node->right != nullptr) //! 把刪除度為2 的結點的問題轉化為刪除{node->element = predecessor(node)->element;remove(predecessor(node));}else if (node->left == nullptr && node->right == nullptr) //! 刪除度為0的結點{if (node->parent == nullptr) //! 若結點是根結點直接置空{node = nullptr;}if (node == node->parent->left) //!結點時葉結點時的置空{node->parent->left = nullptr;}if (node == node->parent->right){node->parent->right = nullptr;}//!我覺得這里直接全都node = nullptr應該是一樣的}else{//! 刪除度為1的結點if (node->parent == nullptr) //!若結點是根結點，用其子結點替代成為根結點{if (node->left != nullptr){root = node->left;}else if (node->right != nullptr){root = node->right;}}else if (node == node->parent->left){ //! 結點是父結點的左子結點或右子結點時，改動雙向指針，和雙向鏈表刪除結點操作一樣if (node->left != nullptr){node->parent->left = node->left;node->left->parent = node->parent;}else if (node->right != nullptr){node->parent->left = node->left;node->left->parent = node->parent;}}else if (node == node->parent->right){if (node->left != nullptr){node->parent->right = node->left;node->left->parent = node->parent;}else if (node->right != nullptr){node->parent->right = node->left;node->left->parent = node->parent;}}} } //!用值在以node為根節點的樹中查找結點 Node *BinarySearchTreesZH::searchNode(int key, Node *node) {if (node == nullptr){return node;}if (node->element == key){cout << "find finished" << endl;return node;}return searchNode(key, node->left); //!這里遍歷的主要目的是遍歷的同時比較結點值，并返回找到的結點return searchNode(key, node->right); //! 所以這里要記得return，把找到的結點return出來，要靈活運用框架return nullptr; }//銷毀整個二叉樹 void BinarySearchTreesZH::clear() {if (root == nullptr){return;}if (root->left != nullptr){return clear(root->left);}if (root->right != nullptr){return clear(root->right);}size = 0;delete this; }//銷毀以某結點為根結點的子樹 void BinarySearchTreesZH::clear(Node *root) {if (root == nullptr){return;}if (root->left != nullptr){return clear(root->left);}if (root->right != nullptr){return clear(root->right);}delete root; }

總結

以上是生活随笔為你收集整理的2021-10-11 二叉树，二叉搜索树及其相关23个操作 C++实现笔记（复习用，含C指针复习）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。