真c++ 从二叉树到红黑树（1）之二叉树节点类及遍历详解
生活随笔
收集整理的這篇文章主要介紹了
真c++ 从二叉树到红黑树（1）之二叉树节点类及遍历详解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
??此文章為從二叉樹到紅黑樹系列文章的第一節，主要介紹寫這系列文章的起因，致謝鄧老師，解釋二叉樹節點類和二叉樹的四種遍歷寫法（包括遞歸和迭代寫法）
文章目錄
- 一、前言與致謝~（點擊右邊波浪線可以返回目錄）
- 二、本系列文章內容基本介紹~
- 1.與鄧老師原有代碼對比~
- 2.主要流程（重點）~
- 3.要看懂文章內的代碼你需要了解的內容~
- 三、樹的語義規定~
- 1.樹的高度與深度~
- 2.樹的遍歷~
- （1）樹的先序遍歷~
- （2）樹的中序遍歷~
- （3）樹的后序遍歷~
- （4）樹的層次遍歷~
- 四、基本二叉樹節點類~
- （一）定義變量和接口~
- 1.需要的變量~
- 2.需要的接口~
- 3.其他輔助函數~
- 4.BinNode.h~
- （二）通用全局靜態函數（不包含后面代碼就運行不了哦）~
- BInNode_Macro.h~
- （三）樹的四種遍歷~
- （重點）借助仿函數來實現遍歷的高明方法~
- 1.層次遍歷的隊列寫法~
- 2.先序遍歷~
- （1）先序遍歷選擇接口~
- （2）先序遍歷的遞歸寫法~
- （3）先序遍歷借助棧的迭代寫法1~
- （4）先序遍歷借助棧的迭代寫法2--便于理解中序和后序的迭代寫法~
- 3.中序遍歷~
- （1）中序遍歷選擇接口~
- （2）中序遍歷的遞歸寫法~
- （3）中序遍歷借助棧的迭代寫法~
- （4）中序遍歷不借助棧的迭代寫法--在理解了怎么求直接后繼后再來看~
- 4.后序遍歷~
- （1）后序遍歷選擇接口~
- （2）后序遍歷的遞歸寫法~
- （3）后序遍歷借助棧的迭代寫法~
- a）找到當前子樹后續遍歷的第一個節點~
- b) 主遍歷函數~
- c）后序遍歷迭代算法完整版~
- （四）求當前節點的直接后繼（用于中序遍歷）~
- （1）若當前節點有右孩子，則其直接后繼必然存在，且屬于其右子樹。~
- （2）若當前節點沒有右孩子，則其直接后繼若存在，并為其祖先。~
- （3）后繼節點代碼~
- （五）BinNode.h完整代碼~
- 五.后序文章鏈接~
一、前言與致謝~（點擊右邊波浪線可以返回目錄）
??c++是一門與時俱進的語言，縱觀網上絕大多數c++的數據結構實現，都是c with class，不得不說，這樣確實有利于理解和學習，但對于那些想借助數據結構來鞏固c++的人來說，不由得有點遺憾（初學直接啃stl源碼會直接自閉的）。
??在此，感謝清華的鄧俊輝老師的c++數據結構教材和視頻，多虧了鄧老師的辛勤耕耘，我才有幸見到現代化的適用于初學者的c++數據結構代碼。在鄧老師教材的第五章，第七章和第八章，全部是介紹樹的知識，看完和仿照敲完代碼之后，獲益匪淺，不止是對數據結構和算法的理解更深了一步，也對c++的特性掌握的更加牢固了一步。
??筆者將其代碼中的一些特性進行了一些更新和修改，讓其更符合現代風格。由于老師對堆區數據的回收都處理的很好，有的地方用智能指針的話，需要改比較多的東西，所以還是保持原來的new和delete。
??本系列文章為了方便，會引用教材和視頻中的一些插圖（侵刪），雖然我對原代碼進行了些許修改，但原代碼所有權依然歸鄧老師所有。
??在寫此系列文章的時候，筆者也對文章進行了排版，讓其更容易進行閱讀，大家放心閱讀，筆者在適當的地方都留了空行和分段。（md的排版真心沒word好= =，排個版都要敲代碼！）
??本系列文章的所有代碼，均在vs2019版本下編譯通過，如果你無法編譯過，請把編譯器的c++版本開啟c++17以上。
二、本系列文章內容基本介紹~
1.與鄧老師原有代碼對比~
我主要對以下幾點進行了更新和修改
2.主要流程（重點）~
筆者根據代碼的內容不同，將分六部分來展現
??強烈建議按照流程進行瀏覽，只有這樣，你才能真正了解紅黑樹！
??但若你沒有時間，也沒關系，我會在一些重點部分，涉及到之前知識點的地方弄一個提示，去指明你去哪才能看到相關的內容。
3.要看懂文章內的代碼你需要了解的內容~
??要完全看懂本系列文章，如果你是初次接觸，不要妄想能在兩三個小時內弄懂此系列文章所有內容，沒人可以做的到，正確的方法是一天抽一兩個小時研究其中一篇文章，對于紅黑樹可能需要更長的時間，你才能真正的看懂代碼，如果你看過鄧老師的教程的話，會更能體會到我這段話的意思。
??如果你嫌長，大可以看其他的文章，但我相信，弄懂本系列文章之后，不僅你的數據結構的功底，還是c++的功底，都可以更上一層樓。（針對c++初學者）。
三、樹的語義規定~
1.樹的高度與深度~
在此系列文章中，會大量用到樹的高度和深度的概念，在此做一個強調
深度： 從根到該節點的唯一路徑長，根的深度為0；從上到下數
高度： 從該節點到葉節點的最長路徑長，所有樹葉的高度為0；從下往上數
另外，規定空樹的高度為-1。
所以，若只有根節點存在，根節點的高度為0。
2.樹的遍歷~
（1）樹的先序遍歷~
先訪問根節點，再依次遍歷左子樹和右子樹 即根左右（一直左到底再右） 3102546（2）樹的中序遍歷~
先訪問左子樹，再依次遍歷根和右子樹 即左根右（即將各個節點映射到一條直線上） 0123456（3）樹的后序遍歷~
先訪問左子樹，再依次遍歷右子樹和根 即左右根 0214653（4）樹的層次遍歷~
從上而下，從左到右訪問樹中各個節點 3150246四、基本二叉樹節點類~
（一）定義變量和接口~
1.需要的變量~
T _data;//存放數據 BinNodePtr _parent; BinNodePtr _lchild; BinNodePtr _rchild; int _height;//高度（通用） RBColor _color;//紅黑樹專用2.需要的接口~
四種遍歷 取得當前節點的直接后繼（BST，AVL，RedBlack用）3.其他輔助函數~
判等器等操作符重載4.BinNode.h~
namespace {enum class RBColor { RED, BLACK };}//===二叉樹節點類===//template<typename T = int>class BinNode {public:using BinNodePtr = BinNode<T>*;public:T _data;//存放數據BinNodePtr _parent;BinNodePtr _lchild;BinNodePtr _rchild;int _height;//高度（通用）RBColor _color;//紅黑樹專用public:BinNode() :_data(0), _parent(nullptr),_lchild(nullptr), _rchild(nullptr), _height(0), _color(RBColor::RED) {}BinNode(const T& data, const BinNodePtr parent = nullptr, const BinNodePtr lchild=nullptr, const BinNodePtr rchild=nullptr,const int &height=0, const RBColor& color = RBColor::RED):_data(data), _parent(parent), _lchild(lchild), _rchild(rchild),_height(height),_color(color) {}public:constexpr bool operator==(const BinNode& bN)const {return this->_data == bN._data;}constexpr bool operator!=(const BinNode& bN)const {return !(this->_data == bN._data);}constexpr bool operator<(const BinNode& bN)const {return this->_data < bN._data;}constexpr bool operator>(const BinNode& bN)const {return this->_data > bN._data;}constexpr bool operator<=(const BinNode& bN)const {return !(this->_data > bN._data);}constexpr bool operator>=(const BinNode& bN)const {return !(this->_data < bN._data);}public:BinNodePtr succ();//取得中序遍歷當前節點的直接后繼，必然無左孩子public:template <typename VST> void travLevel(VST); //子樹層次遍歷template <typename VST> void travPre(VST,const int &method=1); //子樹先序遍歷template <typename VST> void travPost(VST,const int&method=1); //子樹后序遍歷template <typename VST> void travIn(VST,const int&method=1); //子樹中序遍歷};//class BinNode（二）通用全局靜態函數（不包含后面代碼就運行不了哦）~
??鄧老師書上的宏定義有很多個，我將用的多的封裝成相應的constexpr和inline函數，將用的少的放入對應的樹的類中，這樣更有利于管理和應用。
BInNode_Macro.h~
#pragma once/******************************************************************************************* BinNode狀態與性質的判斷******************************************************************************************/#include<algorithm> using std::max;namespace mytree_marcro {template<typename BinNodePtr>static constexpr bool IsRoot(const BinNodePtr& x) {return !(x->_parent);}template<typename BinNodePtr>static constexpr bool IsLChild(const BinNodePtr& x) {return (!IsRoot(x) && (x == x->_parent->_lchild));}template<typename BinNodePtr>static constexpr bool IsRChild(const BinNodePtr& x) {return (!IsRoot(x) && (x == x->_parent->_rchild));//不是根節點，并且其地址跟其父親的右孩子地址相同}template<typename BinNodePtr>static constexpr bool HasLChild(const BinNodePtr& x) {return (x == nullptr) ? false : x->_lchild;}template<typename BinNodePtr>static constexpr bool HasRChild(const BinNodePtr& x) {return (x == nullptr) ? false : x->_rchild;}template<typename BinNodePtr>static constexpr int stature(const BinNodePtr& x) {//獲取高度return x ? x->_height : -1;//空指針高度為-1}}// namespace mytree_marcro（三）樹的四種遍歷~
（重點）借助仿函數來實現遍歷的高明方法~
??對于老手和善用stl的人而言， 這種利用回調函數來進行訪問對應節點的方式，再正常不過。在鄧老師的遍歷代碼中，就高明的用了這種方式，通過這種高內聚，低耦合的方式，從而能對節點進行更多的操作，而并非僅僅是cout就完事。在之后的BST，AVL和RedBlack中，我都會提供一些測試用的仿函數，讀者可根據自己的需要進行改進。
1.層次遍歷的隊列寫法~
??根節點入隊，然后彈出根節點，并將其左右節點入隊。直至隊列為空。
2.先序遍歷~
（1）先序遍歷選擇接口~
由于有三種先序遍歷的寫法，因此創建一個接口函數，并且默認調用迭代版的先序遍歷
template<typename T>template<typename VST> void BinNode<T>::travPre(VST visit,const int& method) {using mytree_trav::travPre_1;using mytree_trav::travPre_2;using mytree_trav::travPre_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 0:travPre_1(this, visit); break;case 1:travPre_2(this, visit); break;default:travPre_R(this, visit); break;} }（2）先序遍歷的遞歸寫法~
以根左右的順序，進行遞歸先序遍歷
/*先序遍歷遞歸版*/ template<typename BinNodePtr, typename VST> static void travPre_R(BinNodePtr x, VST visit) {if (x == nullptr)return;visit(x);travPre_R(x->_lchild, visit);travPre_R(x->_rchild, visit); }（3）先序遍歷借助棧的迭代寫法1~
??尾遞歸轉化為循環。如果只有一個遞歸體，那么直接轉循環就可以。因為此處有兩個遞歸體，因此，還需要借助一個輔助棧來實現。
??遞歸時，分成3部分來看，第一部分基本語句，第二部分遞歸調用左孩子，第三部分遞歸調用右孩子。
??從遞歸時函數調用的堆棧分析來看，相當于先把最后一個語句，也就是遍歷右孩子入棧，再把倒數第二個語句，也就是遍歷左孩子入棧，下一步就是取出棧頂元素進行遍歷。重復循環。（理解了此點，你就能很快的理解為什么需要一個輔助棧！）
（4）先序遍歷借助棧的迭代寫法2–便于理解中序和后序的迭代寫法~
??從書上虛線的的路徑，不難發現遍歷過程中的一個套路，即遍歷可以等價的理解成，從當前節點從上到下訪問左子樹，并visit對應的節點，直到訪問到左子樹為空為止，同時在途中將右孩子均存入棧中。當左子樹訪問到根節點時，就取出棧頂元素，繼續做一次從上到下的向左遍歷。
/*迭代版2*/ template<typename BinNodePtr, typename VST> static void visitLeft_Pre(BinNodePtr x, VST visit, stack<BinNodePtr>& S) {while (x) {visit(x);//訪問當前節點if (HasRChild(x))//右孩子入棧暫存S.push(x->_rchild);x = x->_lchild;} }template<typename BinNodePtr, typename VST> static void travPre_2(BinNodePtr x, VST visit) {stack<BinNodePtr> S;while (true) {visitLeft_Pre(x, visit, S);//從當前節點出發，從上到下，向左訪問。if (S.empty())//直到棧空break;x = S.top();//若棧不空，則取出棧頂節點繼續循環S.pop();} }3.中序遍歷~
（1）中序遍歷選擇接口~
由于有三種中序遍歷的寫法，因此創建一個接口函數，并且默認調用迭代版的中序遍歷
template<typename T>template<typename VST> void BinNode<T>::travIn(VST visit, const int& method) {using mytree_trav::travIn_1;using mytree_trav::travIn_2;using mytree_trav::travIn_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 1:travIn_1(this, visit); break;//1相對普通樹最快case 2:travIn_2(this, visit); break;default:travIn_R(this, visit); break;} }（2）中序遍歷的遞歸寫法~
以左根右的順序，進行遞歸中序遍歷
/*遞歸版*/ template<typename BinNodePtr,typename VST> static void travIn_R(BinNodePtr x, VST visit) {if (x == nullptr)return;travIn_R(x->_lchild,visit);visit(x);travIn_R(x->_rchild,visit); }（3）中序遍歷借助棧的迭代寫法~
??從上圖可以看出，我們遍歷時第一個訪問的必然是最左邊的節點a，但我們的傳入的節點一般為根節點，即都是從i開始進行中序遍歷的。因此，首先也必須要到最左邊的節點a，即要做一次從上到下的向左訪問左子樹，而沿途的節點都不妨存入棧中，方便之后使用。
??每從棧中彈出一個節點，就對其進行visit，都需要對其有沒有右孩子進行檢查，如果有右孩子，則右孩子入棧，并且對右孩子也做一次從上到下的向左遍歷，將沿途的節點全部存入棧中。
??這樣一直到棧為空為止。
（4）中序遍歷不借助棧的迭代寫法–在理解了怎么求直接后繼后再來看~
??本方法實際上本人不推薦使用，因為其每一次遍歷都需要去求后繼，無疑相對前面一種迭代方法而言，增加了不必要的代價。
??因此，此法有興趣者可以看看。此法最重要的是一種利用后繼來遍歷的思想，這點對于線索二叉樹而言非常有效。有興趣的讀者可以看看本人按照大話數據結構改編的線索二叉樹的c++代碼https://blog.csdn.net/bioinformatique/article/details/106082423
/*迭代版2*/ template<typename BinNodePtr, typename VST> static void travIn_2(BinNodePtr x, VST visit) {while (true) {if (HasLChild(x)) {//若有左子樹，則x = x->_lchild;//深入左子樹}else {visit(x);//訪問當前節點，并while (!HasRChild(x)) {//不斷地在無右分支處if (x = x->succ())//回溯至直接后繼,注意此處為賦值visit(x);//如果有后繼，則訪問elsereturn; //（在沒有后繼的末節點處，直接退出）}x = x->_rchild;//（直至有右分支處）轉向非空的右子樹}} }4.后序遍歷~
（1）后序遍歷選擇接口~
由于有兩種后序遍歷的寫法，因此創建一個接口函數，并且默認調用迭代版的后序遍歷
template<typename T>template<typename VST> void BinNode<T>::travPost(VST visit, const int& method) {using mytree_trav::travPost_1;using mytree_trav::travPost_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 1:travPost_1(this, visit); break;default:travPost_R(this, visit); break;} }（2）后序遍歷的遞歸寫法~
以左右根的順序，進行遞歸后序遍歷
/*遞歸版*/ template<typename BinNodePtr, typename VST> static void travPost_R(BinNodePtr x, VST visit) {if (x == nullptr)return;travPost_R(x->_lchild, visit);travPost_R(x->_rchild, visit);visit(x); }（3）后序遍歷借助棧的迭代寫法~
??后序遍歷與中序和先序遍歷不同的是，后序遍歷的第一個被訪問的節點稍有不同，其沒有先序（必然為根節點）和中序（必然為最左孩子）這樣的規律性。
??1. 若最左邊孩子沒有右子樹（最左邊孩子顯然沒有左子樹），則最左邊節點是第一個被訪問的節點。
??2. 若最左邊孩子有右子樹，則是最左邊的節點的右子樹的最左邊的節點。
??首先，無論如何，都需要找到第一個節點。并且沿途的節點也要像中序和前序遍歷一樣很好地利用起來。幸運的是，鄧老師已經幫我們解決了這個難題。
a）找到當前子樹后續遍歷的第一個節點~
??方法就是從當前節點開始，先看其有沒有右孩子，如果有右孩子，則將右孩子入棧，然后再看有沒有左孩子，如果有左孩子，則將左孩子再入棧，并且將左孩子當做“當前節點”繼續循環。
??如果當前節點沒有左孩子，則看這個節點的右孩子有沒有孩子，如果這個節點的右孩子有孩子，則把這個節點作為“當前節點”，繼續進行循環。
??直到“當前節點”沒有孩子為止。那么，此時的棧頂元素，必將為當前樹（子樹）的后序遍歷應該訪問的第一個節點。
如下圖，第一個節點顯然是a
代碼實現為
b) 主遍歷函數~
??在解決了找到當前子樹的相對后繼遍歷的第一個節點后，就解決了后繼遍歷的絕大多數問題。并且，并非在遍歷過程中，所有的節點都需要去執行visitLeft_Post函數。
再來觀看此圖，以及此時的棧結構
我們需要對b進行一次visitLeft_Post函數么，顯然不需要，因為其沒有左子樹。
因此直接訪問b。
下一個被訪問的元素為G么？，顯然不是G，其左右子樹也都沒有在棧中，因此，我們需要以G為子樹進行一次visitLeft_Post函數，從而找到c。
從上面3個圖可以看出，訪問b前不需要進行visitLeft_Post函數，訪問c時需要進行visitLeft_Post函數。那么，到底什么時候需要進行visitLeft_Post函數？
??不妨看一下父子關系。b是a的父親，而G不是b的父親，反而，G是b的兄弟節點！
??不妨可以得出結論，只有當此時棧頂元素不是剛剛彈出的棧頂元素的父親時（必然為剛彈出元素的兄弟），才會進行visitLeft_Post函數，將新的節點插入棧中。
下面給出后序遍歷迭代版的算法
/*迭代版*/ template<typename BinNodePtr, typename VST> static void travPost_1(BinNodePtr x, VST visit) {stack<BinNodePtr> S;S.push(x);while (!S.empty()) {//若棧頂節點不是父親節點，即必為其兄弟節點（除了根節點以外），//若為其兄弟節點，則對兄弟節點進行visitLeft_Post的操作。if (S.top() != x->_parent)visitLeft_Post(S);visit(S.top());x = S.top();//將x設為棧頂元素S.pop();} }c）后序遍歷迭代算法完整版~
//--------------后序遍歷--------------// template<typename BinNodePtr> static void visitLeft_Post(stack<BinNodePtr>& S) {BinNodePtr x = S.top();//將棧頂節點作為當前節點while (true) {//判斷是否有左右孩子，并且先插入右孩子if (HasRChild(x)) {S.push(x->_rchild);}if (HasLChild(x)) {S.push(x->_lchild);}if (x == S.top())//說明棧沒有插入任何元素，即抵達此子樹應該被訪問的第一個節點break;x = S.top();//否則就將棧頂元素給當前的x} }/*迭代版*/ template<typename BinNodePtr, typename VST> static void travPost_1(BinNodePtr x, VST visit) {stack<BinNodePtr> S;S.push(x);while (!S.empty()) {//若棧頂節點不是父親節點，即必為其兄弟節點（除了根節點以外），//若為其兄弟節點，則對兄弟節點進行visitLeft_Post的操作。if (S.top() != x->_parent)visitLeft_Post(S);visit(S.top());x = S.top();//將x設為棧頂元素S.pop();} }（四）求當前節點的直接后繼（用于中序遍歷）~
succ()取得當前節點的后繼節點??與所有遍歷一樣，中序遍歷的實質功能也可理解為，為所有節點賦予一個次序，從而將半線性的二叉樹轉化為線性結構。于是一旦指定了遍歷策略，即可與向量和列表一樣，在二叉樹的節點之間定義后繼關系。其中沒有后繼）的節點稱作末節點。
??對于后面將要介紹的BST，AVL，RedBlack，中序遍歷的作用至關重要。相關算法必需的一項基本操作，就是定位任一節點在中序遍歷序列中的直接后繼。
??分析一個節點的后繼，不妨分做兩種情況分別進行考慮。
（1）若當前節點有右孩子，則其直接后繼必然存在，且屬于其右子樹。~
??在這種情況下，當前節點的直接后繼，必然沒有左孩子。
如下圖a的右孩子b存在，b沒有左孩子，即b為a的直接后繼 如下圖d的右孩子h存在，h有左孩子，即e為d的直接后繼（2）若當前節點沒有右孩子，則其直接后繼若存在，并為其祖先。~
如下圖b的右孩子不存在，則其直接后繼若存在，必為其某一祖先，即c為b的直接后繼 如下圖p的右孩子不存在，但其已經為全樹的最右節點，因此其沒有后繼 讀者們可以根據中序遍歷來進一步體會節點的后繼（3）后繼節點代碼~
//-------取得當前節點的直接后繼----------// template<typename T> BinNode<T>* BinNode<T>::succ() {using BinNodePtr = BinNode<T>*;BinNodePtr s = this;if (HasRChild(s)) {//當前節點有右孩子s = s->_rchild;while (HasLChild(s))//這個右孩子有沒有左孩子，直到沒有左孩子為止s = s->_lchild;}else {//必須分是否是右孩子來判斷，因為這對應不同的情況，如果這個節點不為右孩子，則返回其父親//如果這個節點是右孩子，則需要不斷向上找其父親，直到不為右孩子為止（即為左孩子或根節點)while (IsRChild(s))s = s->_parent;s = s->_parent;//再往上找一格，就能找到后繼。//當然，如果已經到了根節點，根節點的父親當然為空。所以返回空。同時也說明這個節點是最后一個節點。}return s; }（五）BinNode.h完整代碼~
#pragma once#include<queue> #include<stack> #include "BinNode_Macro.h"using std::queue; using std::stack;namespace mytree {using namespace mytree_marcro;namespace {enum class RBColor { RED, BLACK };}//===二叉樹節點類===//template<typename T = int>class BinNode {public:using BinNodePtr = BinNode<T>*;public:T _data;//存放數據BinNodePtr _parent;BinNodePtr _lchild;BinNodePtr _rchild;int _height;//高度（通用）RBColor _color;//紅黑樹專用public:BinNode() :_data(0), _parent(nullptr),_lchild(nullptr), _rchild(nullptr), _height(0), _color(RBColor::RED) {}BinNode(const T& data, const BinNodePtr parent = nullptr, const BinNodePtr lchild=nullptr, const BinNodePtr rchild=nullptr,const int &height=0, const RBColor& color = RBColor::RED):_data(data), _parent(parent), _lchild(lchild), _rchild(rchild),_height(height),_color(color) {}public:constexpr bool operator==(const BinNode& bN)const {return this->_data == bN._data;}constexpr bool operator!=(const BinNode& bN)const {return !(this->_data == bN._data);}constexpr bool operator<(const BinNode& bN)const {return this->_data < bN._data;}constexpr bool operator>(const BinNode& bN)const {return this->_data > bN._data;}constexpr bool operator<=(const BinNode& bN)const {return !(this->_data > bN._data);}constexpr bool operator>=(const BinNode& bN)const {return !(this->_data < bN._data);}public:BinNodePtr succ();//取得中序遍歷當前節點的直接后繼，必然無左孩子public:template <typename VST> void travLevel(VST); //子樹層次遍歷template <typename VST> void travPre(VST,const int &method=1); //子樹先序遍歷template <typename VST> void travPost(VST,const int&method=1); //子樹后序遍歷template <typename VST> void travIn(VST,const int&method=1); //子樹中序遍歷};//class BinNode//--------------遍歷------------------//namespace mytree_trav {//-----------先序遍歷--------------///*迭代版1*//*遞歸轉迭代*//*此法與迭代2在效率上，沒什么區別，但是此法只適用于先序*而迭代2的方式，可以適用于中序和后序遍歷*/template<typename BinNodePtr, typename VST>static void travPre_1(BinNodePtr x, VST visit) {stack<BinNodePtr> S;S.push(x);while (!S.empty()) {x = S.top();S.pop();visit(x);if (HasRChild(x))//入棧次序為先右后左S.push(x->_rchild);if (HasLChild(x))S.push(x->_lchild);}}/*迭代版2*/template<typename BinNodePtr, typename VST>static void visitLeft_Pre(BinNodePtr x, VST visit, stack<BinNodePtr>& S) {while (x) {visit(x);//訪問當前節點if (HasRChild(x))//右孩子入棧暫存S.push(x->_rchild);x = x->_lchild;}}template<typename BinNodePtr, typename VST>static void travPre_2(BinNodePtr x, VST visit) {stack<BinNodePtr> S;while (true) {visitLeft_Pre(x, visit, S);//從當前節點出發，從上到下，向左訪問。if (S.empty())//直到?？?/span>break;x = S.top();//若棧不空，則取出棧頂節點繼續循環S.pop();}}/*先序遍歷遞歸版*/template<typename BinNodePtr, typename VST>static void travPre_R(BinNodePtr x, VST visit) {if (x == nullptr)return;visit(x);travPre_R(x->_lchild, visit);travPre_R(x->_rchild, visit);}//--------------后序遍歷--------------//template<typename BinNodePtr>static void visitLeft_Post(stack<BinNodePtr>& S) {BinNodePtr x = S.top();//將棧頂節點作為當前節點while (true) {//判斷是否有左右孩子，并且先插入右孩子if (HasRChild(x)) {S.push(x->_rchild);}if (HasLChild(x)) {S.push(x->_lchild);}if (x == S.top())//說明棧沒有插入任何元素，即抵達此子樹應該被訪問的第一個節點break;x = S.top();//否則就將棧頂元素給當前的x}}/*迭代版*/template<typename BinNodePtr, typename VST>static void travPost_1(BinNodePtr x, VST visit) {stack<BinNodePtr> S;S.push(x);while (!S.empty()) {//若棧頂節點不是父親節點，即必為其兄弟節點（除了根節點以外），若為其兄弟節點，則對兄弟節點進行visitLeft_Post的操作。if (S.top() != x->_parent)visitLeft_Post(S);visit(S.top());x = S.top();//將x設為棧頂元素S.pop();}}/*遞歸版*/template<typename BinNodePtr, typename VST>static void travPost_R(BinNodePtr x, VST visit) {if (x == nullptr)return;travPost_R(x->_lchild, visit);travPost_R(x->_rchild, visit);visit(x);}//---------中序遍歷---------//template<typename BinNodePtr>static void visitLeft_In(BinNodePtr x, stack<BinNodePtr>& S) {//將所有左孩子插入棧中while (x) {S.push(x);x = x->_lchild;}}/*迭代版1*/template<typename BinNodePtr, typename VST>static void travIn_1(BinNodePtr x, VST visit) {stack<BinNodePtr> S;while (true) {visitLeft_In(x, S);//將所有左孩子插入棧中if (S.empty())break;x = S.top();visit(x);S.pop();x = x->_rchild;//如果棧頂元素有右孩子，則對右孩子的左子樹進行visitLeft_In，若右孩子為空，則直接結束visitLeft_In}}/*迭代版2*/template<typename BinNodePtr, typename VST>static void travIn_2(BinNodePtr x, VST visit) {while (true) {if (HasLChild(x)) {//若有左子樹，則x = x->_lchild;//深入左子樹}else {visit(x);//訪問當前節點，并while (!HasRChild(x)) {//不斷地在無右分支處if (x = x->succ())//回溯至直接后繼,注意此處為賦值visit(x);//如果有后繼，則訪問elsereturn; //（在沒有后繼的末節點處，直接退出）}x = x->_rchild;//（直至有右分支處）轉向非空的右子樹}}}/*遞歸版*/template<typename BinNodePtr,typename VST>static void travIn_R(BinNodePtr x, VST visit) {if (x == nullptr)return;travIn_R(x->_lchild,visit);visit(x);travIn_R(x->_rchild,visit);}}//namespace mytree_travtemplate<typename T>template<typename VST>void BinNode<T>::travLevel(VST visit) {if (this == nullptr)//提前判斷是否為空樹return;queue<BinNodePtr> Q;Q.push(this);//根節點入隊BinNodePtr current = nullptr;//防止多次調用構造析構，故在循環為創建臨時變量while (!Q.empty()) {//如果隊列不為空current = Q.front();visit(current);Q.pop();if (HasLChild(current))Q.push(current->_lchild);if (HasRChild(current))Q.push(current->_rchild);}}template<typename T>template<typename VST>void BinNode<T>::travPre(VST visit,const int& method) {using mytree_trav::travPre_1;using mytree_trav::travPre_2;using mytree_trav::travPre_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 0:travPre_1(this, visit); break;case 1:travPre_2(this, visit); break;default:travPre_R(this, visit); break;}}template<typename T>template<typename VST>void BinNode<T>::travPost(VST visit, const int& method) {using mytree_trav::travPost_1;using mytree_trav::travPost_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 1:travPost_1(this, visit); break;default:travPost_R(this, visit); break;}}template<typename T>template<typename VST>void BinNode<T>::travIn(VST visit, const int& method) {using mytree_trav::travIn_1;using mytree_trav::travIn_2;using mytree_trav::travIn_R;if (this == nullptr)//提前判斷是否為空樹return;switch (method){case 1:travIn_1(this, visit); break;//1相對普通樹最快case 2:travIn_2(this, visit); break;default:travIn_R(this, visit); break;}}//-------取得當前節點的直接后繼----------//template<typename T>BinNode<T>* BinNode<T>::succ() {using BinNodePtr = BinNode<T>*;BinNodePtr s = this;if (HasRChild(s)) {//當前節點有右孩子s = s->_rchild;while (HasLChild(s))//這個右孩子有沒有左孩子，直到沒有左孩子為止s = s->_lchild;}else {//必須分是否是右孩子來判斷，因為這對應不同的情況，如果這個節點不為右孩子，則返回其父親//如果這個節點是右孩子，則需要不斷向上找其父親，直到不為右孩子為止（即為左孩子或根節點)while (IsRChild(s))s = s->_parent;s = s->_parent;//再往上找一格，就能找到后繼。//當然，如果已經到了根節點，根節點的父親當然為空。所以返回空。同時也說明這個節點是最后一個節點。}return s;} }//namespace mytree五.后序文章鏈接~
學一個東西，不知道其道理，不高明！
總結
以上是生活随笔為你收集整理的真c++ 从二叉树到红黑树（1）之二叉树节点类及遍历详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 智慧社区网格化管理php,智慧社区建设：
- 下一篇： 十二时辰篇：这该死的 996