高級數(shù)據(jù)結(jié)構(gòu)和算法3：樹的遍歷

樹的遍歷葛碧，是指依照一定的規(guī)律不反復地訪問（或取出節(jié)點中的信息，或?qū)?jié)點做其它的處理）樹中的每個節(jié)點斩箫，遍歷是將非線性的樹狀結(jié)構(gòu)按一定規(guī)律轉(zhuǎn)化為線性結(jié)構(gòu)拄踪。

1. 多叉樹遍歷

多叉樹遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩類蝇恶。樹孩子表示法比較容易遍歷。
圖形演示：visualgo DFS BFS

1.1 深度優(yōu)先遍歷(DFS:Depth First Search)

深度優(yōu)先遍歷：從根節(jié)點開始先沿著樹的一個枝遍歷到葉子節(jié)點惶桐，再遍歷其他的枝撮弧。深度優(yōu)先遍歷又分為先序遍歷和后序遍歷。

1.1.1 先序遍歷

樹中父節(jié)點先于子節(jié)點訪問
上圖樹的先序遍歷結(jié)果：A → B → D → G → H → I → C → E → J → F
通常先序遍歷實現(xiàn)分兩種方式：遞歸方式和非遞歸方式(棧方式)姚糊。
參考代碼

遞歸深度優(yōu)先遍歷：先序遍歷

void RecurtionPreDFS(int root,Node* nodes){
    printf("%c ",nodes[root].data);
    for(int i= 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        RecurtionPreDFS(post,nodes);
    }
}

非遞歸深度優(yōu)先遍歷：先序遍歷

void PreDFS(int root,Node* nodes){
    stack<int> s;
    s.push(root);
    while(!s.empty()){
        int now = s.top();
        s.pop();
        printf("%c ",nodes[now].data);// 出棧訪問
        for(int i= nodes[now].children.size()-1; i>=0;--i){
            int post = nodes[now].children[i];
            s.push(post);
        }
    }
}

迭代是橫向思維贿衍，遞歸是縱向思維

1.1.2 后序遍歷

樹中子節(jié)點先于父節(jié)點訪問
上圖樹的后序遍歷結(jié)果：G → H → I → D → B → J → E → F → C → A
遞歸深度優(yōu)先遍歷：后序遍歷

void RecurtionPostDFS(int root,Node* nodes){
    for(int i= 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        RecurtionPostDFS(post,nodes);
    }
    printf("%c ",nodes[root].data);
}

非遞歸深度優(yōu)先遍歷：后序遍歷

void PostDFS(int root,Node* nodes){
    stack<int> s;
    s.push(root);
    int prev= -1;
    while(!s.empty()){
        int now = s.top();
        if(nodes[now].children.size() != 0 // 還有子節(jié)點
           && prev != nodes[now].children.back()){ // 回溯，上一個節(jié)點是最后一個遍歷的子節(jié)點
            for(int i= nodes[now].children.size()-1; i>=0;--i){
                int post = nodes[now].children[i];
                s.push(post);
            }
        } else {
            s.pop();
            printf("%c ",nodes[now].data);// 出棧訪問
        }
        prev = now;
    }
}

1.2 廣度優(yōu)先遍歷(Breath First Search)

廣度優(yōu)先遍歷：從根節(jié)點開始從上到下按照層依次遍歷叛拷。

上圖樹的廣度優(yōu)先遍歷結(jié)果：A → B → C → D → E → F → G → H → I → J

void BFS(int root,Node* nodes){
    queue<int> s;
    s.push(root);
    printf("%c ",nodes[root].data);// 入隊訪問
    while(!s.empty()){
        int now = s.front();
        s.pop();
        for(int i= 0;i<nodes[now].children.size();++i){
            int post = nodes[now].children[i];
            s.push(post);
            printf("%c ",nodes[post].data);// 入隊訪問
        }
    }
}

完整測試程序

#include <bits/stdc++.h>
using namespace std;

struct Node{// 孩子表示法
   char data;
   vector<int> children;
};

// 非遞歸深度優(yōu)先遍歷：先序遍歷
void PreDFS(int root,Node* nodes){
    stack<int> s;
    s.push(root);
    while(!s.empty()){
        int now = s.top();
        s.pop();
        printf("%c ",nodes[now].data);// 出棧訪問
        for(int i= nodes[now].children.size()-1; i>=0;--i){// 逆序遍歷
            int post = nodes[now].children[i];
            s.push(post);
        }
    }
}
// 遞歸深度優(yōu)先遍歷：先序遍歷
void RecurtionPreDFS(int root,Node* nodes){
    printf("%c ",nodes[root].data);
    for(int i= 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        RecurtionPreDFS(post,nodes);
    }
}
// 非遞歸深度優(yōu)先遍歷：后序遍歷
void PostDFS(int root,Node* nodes){
    stack<int> s;
    s.push(root);
    int prev= -1;
    while(!s.empty()){
        int now = s.top();
        if(nodes[now].children.size() != 0 // 還有子節(jié)點
           && prev != nodes[now].children.back()){ // 回溯，上一個節(jié)點是最后一個遍歷的子節(jié)點
            for(int i= nodes[now].children.size()-1; i>=0;--i){
                int post = nodes[now].children[i];
                s.push(post);
            }
        } else {
            s.pop();
            printf("%c ",nodes[now].data);// 出棧訪問
        }
        prev = now;
    }
}
// 遞歸深度優(yōu)先遍歷：后序遍歷
void RecurtionPostDFS(int root,Node* nodes){
    for(int i= 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        RecurtionPostDFS(post,nodes);
    }
    printf("%c ",nodes[root].data);
}
// 非遞歸廣度優(yōu)先遍歷
void BFS(int root,Node* nodes){
    queue<int> s;
    s.push(root);
    printf("%c ",nodes[root].data);// 入隊訪問
    while(!s.empty()){
        int now = s.front();
        s.pop();
        for(int i= 0;i<nodes[now].children.size();++i){
            int post = nodes[now].children[i];
            s.push(post);
            printf("%c ",nodes[post].data);// 入隊訪問
        }
    }
}

int depth(int root,Node* nodes){
    int maxDep = 0;
    for(int i = 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        int dep = depth(post,nodes);
        maxDep = max(dep,maxDep);
    }
    return maxDep+1;
}

// 遞歸廣度優(yōu)先遍歷
void RecurtionBFS(int root,Node* nodes,int level){
    if(0 == level) return;
    if(1 == level) {
        printf("%c ",nodes[root].data);
        return;
    }
    for(int i = 0;i<nodes[root].children.size();++i){
        int post = nodes[root].children[i];
        RecurtionBFS(post,nodes,level-1);
    }
}
void RecurtionBFS(int root,Node* nodes){
    int dep = depth(root,nodes);
    for(int i= 1;i<=dep;++i){// 按層次打印
        RecurtionBFS(root,nodes,i);
    }
}

int main() {
   Node nodes[10] = {
       {'A',{1,2}},
       {'B',{3}},
       {'C',{4,5}},
       {'D',{6,7,8}},
       {'E',{9}},
       {'F'},
       {'G'},
       {'H'},
       {'I'},
       {'J'}
   };
   int root = 0;
   printf("非遞歸深度優(yōu)先遍歷：先序遍歷\n");
   PreDFS(root,nodes);
   printf("\n遞歸深度優(yōu)先遍歷：先序遍歷\n");
   RecurtionPreDFS(root,nodes);
   printf("\n非遞歸深度優(yōu)先遍歷：后序遍歷\n");
   PostDFS(root,nodes);
   printf("\n遞歸深度優(yōu)先遍歷：后序遍歷\n");
   RecurtionPostDFS(root,nodes);
   printf("\n非遞歸廣度優(yōu)先遍歷\n");
   BFS(root,nodes);
   printf("\n遞歸廣度優(yōu)先遍歷\n");
   RecurtionBFS(root,nodes);
   printf("\n樹的深度:%d\n",depth(root,nodes));
   return 0;
}

練習

LeetCode 589. N叉樹的前序遍歷
LeetCode 590. N叉樹的后序遍歷
LeetCode 429. N叉樹的層序遍歷
LeetCode 559. N叉樹的最大深度

槍挑一條線岂却、棍掃一大片

2. 二叉樹遍歷

二叉樹通常使用鏈式存儲忿薇。

struct Node{// 孩子表示法
   char data;
   struct Node* right;
   struct Node* left;
};

二叉樹的廣度優(yōu)先遍歷與多叉樹的廣度優(yōu)先遍歷是一樣的裙椭，因為是層次遍歷，所以也稱為層次遍歷署浩。
二叉樹的深度優(yōu)先遍歷揉燃，根據(jù)父節(jié)點與左右子節(jié)點訪問順序的不同，而分為三類：

前序遍歷(Pre-order Traversal)
中序遍歷(In-order Traversal)
后序遍歷(Post-order Traversal)

深度優(yōu)先遍歷.png

深度優(yōu)先遍歷三種遍歷方式各有兩種實現(xiàn)方式筋栋。

2.1 深度優(yōu)先遍歷

2.1.1 前序遍歷(Pre-order Traversal)

上圖前序遍歷結(jié)果：A → B → D → E → C → F → G

前序遍歷步驟：

訪問根節(jié)點
遞歸遍歷左子樹
遞歸遍歷右子樹

直到所有節(jié)點都被訪問炊汤。

2.1.2 后序遍歷(Post-order Traversal)

上圖后序遍歷結(jié)果：D → E → B → F → G → C → A

后序遍歷步驟：

訪問根節(jié)點
遞歸遍歷右子樹
遞歸遍歷左子樹

直到所有節(jié)點都被訪問。

2.1.3 中序遍歷(In-order Traversal)

上圖中序遍歷結(jié)果：D → B → E → A → F → C → G

中序遍歷步驟：

遞歸遍歷左子樹
訪問根節(jié)點
遞歸遍歷右子樹

直到所有節(jié)點都被訪問弊攘。

2.2 廣度優(yōu)先遍歷

上圖后序遍歷結(jié)果：A → B → C → D → E → F → G

后序遍歷步驟：

訪問根節(jié)點
按層次從上到下依次遍歷

完整測試程序

#include <bits/stdc++.h>
using namespace std;

struct Node{// 孩子表示法
   char data;
   struct Node* left;
   struct Node* right;
};
// 遞歸深度優(yōu)先遍歷：先序遍歷
void RecurtionPreDFS(Node* nodes){
    if(NULL != nodes){
        printf("%c ",nodes->data);
        RecurtionPreDFS(nodes->left);
        RecurtionPreDFS(nodes->right);
    }
}
// 遞歸深度優(yōu)先遍歷：后序遍歷
void RecurtionPostDFS(Node* nodes){
    if(NULL != nodes){
        RecurtionPostDFS(nodes->left);
        RecurtionPostDFS(nodes->right);
        printf("%c ",nodes->data);
    }
}
// 遞歸深度優(yōu)先遍歷：中序遍歷
void RecurtionInDFS(Node* nodes){
    if(NULL != nodes){
        RecurtionInDFS(nodes->left);
        printf("%c ",nodes->data);
        RecurtionInDFS(nodes->right);
    }
}
// 非遞歸深度優(yōu)先遍歷：先序遍歷
void PreDFS2(Node* nodes){
    if(NULL == nodes) return;
    stack<Node*> s;// 保存已訪問的節(jié)點
    s.push(nodes);
    while(!s.empty()){
        Node* now = s.top();
        s.pop();
        printf("%c ",now->data);
        if(NULL != now->right) s.push(now->right);
        if(NULL != now->left) s.push(now->left);
    }
}
void PreDFS(Node* nodes){
    stack<Node*> s;
    Node* now = nodes;
    while(NULL != now||!s.empty()){
        if(NULL != now){
            printf("%c ",now->data); // 打印節(jié)點  
            s.push(now);
            now = now->left;  // 左側(cè)有節(jié)點
        }else{
            Node* p = s.top(); 
            s.pop();
            now = p->right;
        }
    }
}
// 非遞歸深度優(yōu)先遍歷：中序遍歷
void InDFS2(Node* nodes){
    stack<Node*> s;
    Node* now = nodes;
    while(NULL != now||!s.empty()){
        if(NULL != now){ 
            s.push(now);
            now = now->left;  // 左側(cè)有節(jié)點
        }else{
            Node* p = s.top(); 
            s.pop();
            printf("%c ",p->data); // 打印節(jié)點 
            now = p->right;
        }
    }
}
// 中序
void InDFS(Node* nodes){
    stack<Node*> s;
    Node *prev = NULL,*now = NULL; // 記錄當前節(jié)點和上一個節(jié)點之間的關(guān)系
    s.push(nodes);
    while(!s.empty()){
        now = s.top();
        if(NULL == prev // now為根節(jié)點
            || prev->left == now || prev->right == now // prev是now的父節(jié)點
          ){
            if(NULL != now->left){
                s.push(now->left); // 左孩子入棧
            }else if(NULL != now->right){
                s.push(now->right); // 右孩子入棧
            }
        }else if(now->left == prev){ // prev是now的左孩子(回溯)
            printf("%c ",now->data); // 打印節(jié)點
            if(NULL != now->right){
                s.push(now->right); // 右孩子入棧
            }
        }else if(now->right == prev){ // prev是now的右孩子(回溯)
            s.pop();
        }else{
            printf("%c ",now->data); // 打印節(jié)點
            s.pop();
        }
        prev = now;
    }
}
// 非遞歸深度優(yōu)先遍歷：后序遍歷
// 使用雙棧抢腐，將先序遍歷逆序
void PostDFS(Node* nodes){
    stack<Node*> s;
    stack<Node*> t; //1.添加結(jié)果棧
    Node* now = nodes;
    while(NULL != now||!s.empty()){
        if(NULL != now){
            t.push(now); // 2.將打印數(shù)據(jù)入棧  
            s.push(now);
            now = now->right;  // 3.左右調(diào)換
        }else{
            Node* p = s.top(); 
            s.pop();
            now = p->left; // 3.左右調(diào)換
        }
    }
    while(!t.empty()){ // 4.打印結(jié)果棧
        Node* p = t.top(); 
        t.pop();
        printf("%c ",p->data); // 打印節(jié)點
    }
}
void PostDFS2(Node* nodes){
    stack<Node*> s;
    Node *prev = NULL,*now = NULL; // 記錄當前節(jié)點和上一個節(jié)點之間的關(guān)系
    s.push(nodes);
    while(!s.empty()){
        now = s.top();
        if(NULL == prev // now為根節(jié)點
            || prev->left == now || prev->right == now // prev是now的父節(jié)點
          ){
            if(NULL != now->left){
                s.push(now->left); // 左孩子入棧
            }else if(NULL != now->right){
                s.push(now->right); // 右孩子入棧
            }
        }else if(now->left == prev){ // prev是now的左孩子(回溯)
            if(NULL != now->right){
                s.push(now->right); // 右孩子入棧
            }
        }else{
            printf("%c ",now->data); // 打印節(jié)點
            s.pop();
        }
        prev = now;
    }
}
// 廣度優(yōu)先遍歷
void BFS(Node* nodes){
    queue<Node*> s;
    s.push(nodes);
    printf("%c ",nodes->data);// 入隊訪問
    while(!s.empty()){
        Node* now = s.front();
        s.pop();
        if(NULL != now->left){
            s.push(now->left);
            printf("%c ",now->left->data);// 入隊訪問
        }
        if(NULL != now->right){
            s.push(now->right);
            printf("%c ",now->right->data);// 入隊訪問
        }
    }
}
int Depth(Node* nodes){
    if(NULL == nodes) return 0;
    return max(Depth(nodes->right),Depth(nodes->right))+1;
}

// 遞歸廣度優(yōu)先遍歷
void RecurtionBFS(Node* nodes,int level){
    if(NULL == nodes || 0 == level) return;
    if(1 == level){
        printf("%c ",nodes->data);
    }
    RecurtionBFS(nodes->left,level-1);
    RecurtionBFS(nodes->right,level-1);
}

void RecurtionBFS(Node* nodes){
    if(NULL == nodes) return;
    int dep = Depth(nodes);
    for(int i=1;i<=dep;++i){
        RecurtionBFS(nodes,i);
    }
}

int main() {
    
    // 葉子節(jié)點
    Node d = {'D',NULL,NULL};
    Node e = {'E',NULL,NULL};
    Node f = {'F',NULL,NULL};
    Node g = {'G',NULL,NULL};

    // 分支節(jié)點
    Node b = {'B',&d,&e};
    Node c = {'C',&f,&g};
    
    // 根節(jié)點
    Node a = {'A',&b,&c};
    Node* root = &a;

   printf("\n遞歸深度優(yōu)先遍歷：先序遍歷\n");
   RecurtionPreDFS(root);
   printf("\n遞歸深度優(yōu)先遍歷：后序遍歷\n");
   RecurtionPostDFS(root);
   printf("\n遞歸深度優(yōu)先遍歷：中序遍歷\n");
   RecurtionInDFS(root);

   printf("\n非遞歸深度優(yōu)先遍歷：先序遍歷\n");
   PreDFS(root);
   printf("\n");
   PreDFS2(root);
   printf("\n非遞歸深度優(yōu)先遍歷：后序遍歷\n");
   PostDFS(root);
   printf("\n");
   PostDFS2(root);
   printf("\n非遞歸深度優(yōu)先遍歷：中序遍歷\n");
   InDFS(root);
   printf("\n");
   InDFS2(root);

   printf("\n廣度優(yōu)先遍歷\n");
   BFS(root);
   printf("\n遞歸廣度優(yōu)先遍歷\n");
   RecurtionBFS(root);
   printf("\n");
   printf("樹的深度:%d\n",Depth(root));
}

3.練習

中序遍歷.png

前序遍歷.png

后序遍歷.png

層次遍歷.png

練習

LeetCode 100. 相同的樹
LeetCode 144. 二叉樹的前序遍歷
LeetCode 94. 二叉樹的中序遍歷
LeetCode 145. 二叉樹的后序遍歷
LeetCode 102. 二叉樹的層次遍歷
LeetCode 104. 二叉樹的最大深度
LeetCode 111. 二叉樹的最小深度

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市襟交，隨后出現(xiàn)的幾起案子迈倍，更是在濱河造成了極大的恐慌，老刑警劉巖捣域，帶你破解...
沈念sama閱讀 212,454評論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件啼染，死亡現(xiàn)場離奇詭異，居然都是意外死亡焕梅，警方通過查閱死者的電腦和手機迹鹅，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,553評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來贞言，“玉大人斜棚，你說我怎么就攤上這事∥献郑” “怎么了打肝？”我有些...
開封第一講書人閱讀 157,921評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長挪捕。經(jīng)常有香客問我粗梭，道長，這世上最難降的妖魔是什么级零？我笑而不...
開封第一講書人閱讀 56,648評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任断医，我火速辦了婚禮，結(jié)果婚禮上奏纪，老公的妹妹穿的比我還像新娘鉴嗤。我一直安慰自己，他們只是感情好序调，可當我...
茶點故事閱讀 65,770評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布醉锅。她就那樣靜靜地躺著，像睡著了一般发绢。火紅的嫁衣襯著肌膚如雪硬耍。梳的紋絲不亂的頭發(fā)上垄琐，一...
開封第一講書人閱讀 49,950評論 1贊 291
城市分裂傳說
那天，我揣著相機與錄音经柴，去河邊找鬼狸窘。笑死，一個胖子當著我的面吹牛坯认，可吹牛的內(nèi)容都是我干的翻擒。我是一名探鬼主播，決...
沈念sama閱讀 39,090評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼牛哺，長吁一口氣：“原來是場噩夢啊……” “哼陋气！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起荆隘，我...
開封第一講書人閱讀 37,817評論 0贊 268
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤恩伺，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后椰拒，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體晶渠，經(jīng)...
沈念sama閱讀 44,275評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,592評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年燃观，在試婚紗的時候發(fā)現(xiàn)自己被綠了褒脯。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,724評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡缆毁，死狀恐怖番川，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情脊框，我是刑警寧澤颁督，帶...
沈念sama閱讀 34,409評論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站浇雹，受9級特大地震影響沉御，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜昭灵，卻給世界環(huán)境...
茶點故事閱讀 40,052評論 3贊 316
男人毒藥：我在死后第九天來索命
文/蒙蒙一吠裆、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧烂完，春花似錦试疙、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,815評論 0贊 21
一樁弒父案祝旷，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至，卻和暖如春怀跛，著一層夾襖步出監(jiān)牢的瞬間奇昙，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,043評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工敌完，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人羊初。一個月前我還...
沈念sama閱讀 46,503評論 2贊 361
代替公主和親
正文我出身青樓滨溉，卻偏偏與公主長得像，于是被迫代替她去往敵國和親长赞。傳聞我的和親對象是個殘疾皇子晦攒，可洞房花燭夜當晚...
茶點故事閱讀 43,627評論 2贊 350