美文网首页
高级数据结构和算法3：树的遍历

高级数据结构和算法3：树的遍历

作者: jdzhangxin | 来源:发表于2019-08-14 10:21 被阅读0次

树的遍历，是指依照一定的规律不反复地訪问（或取出节点中的信息，或对节点做其它的处理）树中的每个节点，遍历是将非线性的树状结构按一定规律转化为线性结构。

1. 多叉树遍历

多叉树遍历分为深度优先遍历和广度优先遍历两类。树孩子表示法比较容易遍历。
图形演示：visualgo DFS BFS

1.1 深度优先遍历(DFS:Depth First Search)

深度优先遍历：从根节点开始先沿着树的一个枝遍历到叶子节点，再遍历其他的枝。深度优先遍历又分为先序遍历和后序遍历。

1.1.1 先序遍历

树中父节点先于子节点访问
上图树的先序遍历结果：A → B → D → G → H → I → C → E → J → F
通常先序遍历实现分两种方式：递归方式和非递归方式(栈方式)。
参考代码

递归深度优先遍历：先序遍历

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);
    }
}

非递归深度优先遍历：先序遍历

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 后序遍历

树中子节点先于父节点访问
上图树的后序遍历结果：G → H → I → D → B → J → E → F → C → A
递归深度优先遍历：后序遍历

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);
}

非递归深度优先遍历：后序遍历

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 // 还有子节点
           && prev != nodes[now].children.back()){ // 回溯，上一个节点是最后一个遍历的子节点
            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 广度优先遍历(Breath First Search)

广度优先遍历：从根节点开始从上到下按照层依次遍历。


上图树的广度优先遍历结果：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;
};

// 非递归深度优先遍历：先序遍历
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);
        }
    }
}
// 递归深度优先遍历：先序遍历
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);
    }
}
// 非递归深度优先遍历：后序遍历
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 // 还有子节点
           && prev != nodes[now].children.back()){ // 回溯，上一个节点是最后一个遍历的子节点
            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;
    }
}
// 递归深度优先遍历：后序遍历
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);
}
// 非递归广度优先遍历
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;
}

// 递归广度优先遍历
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("非递归深度优先遍历：先序遍历\n");
   PreDFS(root,nodes);
   printf("\n递归深度优先遍历：先序遍历\n");
   RecurtionPreDFS(root,nodes);
   printf("\n非递归深度优先遍历：后序遍历\n");
   PostDFS(root,nodes);
   printf("\n递归深度优先遍历：后序遍历\n");
   RecurtionPostDFS(root,nodes);
   printf("\n非递归广度优先遍历\n");
   BFS(root,nodes);
   printf("\n递归广度优先遍历\n");
   RecurtionBFS(root,nodes);
   printf("\n树的深度:%d\n",depth(root,nodes));
   return 0;
}

练习

枪挑一条线、棍扫一大片

2. 二叉树遍历

二叉树通常使用链式存储。

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

二叉树的广度优先遍历与多叉树的广度优先遍历是一样的，因为是层次遍历，所以也称为层次遍历。
二叉树的深度优先遍历，根据父节点与左右子节点访问顺序的不同，而分为三类：

  • 前序遍历(Pre-order Traversal)
  • 中序遍历(In-order Traversal)
  • 后序遍历(Post-order Traversal)
深度优先遍历.png

深度优先遍历三种遍历方式各有两种实现方式。

2.1 深度优先遍历

2.1.1 前序遍历(Pre-order Traversal)


上图前序遍历结果：A → B → D → E → C → F → G

前序遍历步骤：

  1. 访问根节点
  2. 递归遍历左子树
  3. 递归遍历右子树

直到所有节点都被访问。

2.1.2 后序遍历(Post-order Traversal)


上图后序遍历结果：D → E → B → F → G → C → A

后序遍历步骤：

  1. 访问根节点
  2. 递归遍历右子树
  3. 递归遍历左子树

直到所有节点都被访问。

2.1.3 中序遍历(In-order Traversal)


上图中序遍历结果：D → B → E → A → F → C → G

中序遍历步骤：

  1. 递归遍历左子树
  2. 访问根节点
  3. 递归遍历右子树

直到所有节点都被访问。

2.2 广度优先遍历


上图后序遍历结果：A → B → C → D → E → F → G

后序遍历步骤：

  1. 访问根节点
  2. 按层次从上到下依次遍历

完整测试程序

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

struct Node{// 孩子表示法
   char data;
   struct Node* left;
   struct Node* right;
};
// 递归深度优先遍历：先序遍历
void RecurtionPreDFS(Node* nodes){
    if(NULL != nodes){
        printf("%c ",nodes->data);
        RecurtionPreDFS(nodes->left);
        RecurtionPreDFS(nodes->right);
    }
}
// 递归深度优先遍历：后序遍历
void RecurtionPostDFS(Node* nodes){
    if(NULL != nodes){
        RecurtionPostDFS(nodes->left);
        RecurtionPostDFS(nodes->right);
        printf("%c ",nodes->data);
    }
}
// 递归深度优先遍历：中序遍历
void RecurtionInDFS(Node* nodes){
    if(NULL != nodes){
        RecurtionInDFS(nodes->left);
        printf("%c ",nodes->data);
        RecurtionInDFS(nodes->right);
    }
}
// 非递归深度优先遍历：先序遍历
void PreDFS2(Node* nodes){
    if(NULL == nodes) return;
    stack<Node*> s;// 保存已访问的节点
    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); // 打印节点  
            s.push(now);
            now = now->left;  // 左侧有节点
        }else{
            Node* p = s.top(); 
            s.pop();
            now = p->right;
        }
    }
}
// 非递归深度优先遍历：中序遍历
void InDFS2(Node* nodes){
    stack<Node*> s;
    Node* now = nodes;
    while(NULL != now||!s.empty()){
        if(NULL != now){ 
            s.push(now);
            now = now->left;  // 左侧有节点
        }else{
            Node* p = s.top(); 
            s.pop();
            printf("%c ",p->data); // 打印节点 
            now = p->right;
        }
    }
}
// 中序
void InDFS(Node* nodes){
    stack<Node*> s;
    Node *prev = NULL,*now = NULL; // 记录当前节点和上一个节点之间的关系
    s.push(nodes);
    while(!s.empty()){
        now = s.top();
        if(NULL == prev // now为根节点
            || prev->left == now || prev->right == now // prev是now的父节点
          ){
            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); // 打印节点
            if(NULL != now->right){
                s.push(now->right); // 右孩子入栈
            }
        }else if(now->right == prev){ // prev是now的右孩子(回溯)
            s.pop();
        }else{
            printf("%c ",now->data); // 打印节点
            s.pop();
        }
        prev = now;
    }
}
// 非递归深度优先遍历：后序遍历
// 使用双栈，将先序遍历逆序
void PostDFS(Node* nodes){
    stack<Node*> s;
    stack<Node*> t; //1.添加结果栈
    Node* now = nodes;
    while(NULL != now||!s.empty()){
        if(NULL != now){
            t.push(now); // 2.将打印数据入栈  
            s.push(now);
            now = now->right;  // 3.左右调换
        }else{
            Node* p = s.top(); 
            s.pop();
            now = p->left; // 3.左右调换
        }
    }
    while(!t.empty()){ // 4.打印结果栈
        Node* p = t.top(); 
        t.pop();
        printf("%c ",p->data); // 打印节点
    }
}
void PostDFS2(Node* nodes){
    stack<Node*> s;
    Node *prev = NULL,*now = NULL; // 记录当前节点和上一个节点之间的关系
    s.push(nodes);
    while(!s.empty()){
        now = s.top();
        if(NULL == prev // now为根节点
            || prev->left == now || prev->right == now // prev是now的父节点
          ){
            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); // 打印节点
            s.pop();
        }
        prev = now;
    }
}
// 广度优先遍历
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;
}

// 递归广度优先遍历
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() {
    
    // 叶子节点
    Node d = {'D',NULL,NULL};
    Node e = {'E',NULL,NULL};
    Node f = {'F',NULL,NULL};
    Node g = {'G',NULL,NULL};

    // 分支节点
    Node b = {'B',&d,&e};
    Node c = {'C',&f,&g};
    
    // 根节点
    Node a = {'A',&b,&c};
    Node* root = &a;

   printf("\n递归深度优先遍历：先序遍历\n");
   RecurtionPreDFS(root);
   printf("\n递归深度优先遍历：后序遍历\n");
   RecurtionPostDFS(root);
   printf("\n递归深度优先遍历：中序遍历\n");
   RecurtionInDFS(root);

   printf("\n非递归深度优先遍历：先序遍历\n");
   PreDFS(root);
   printf("\n");
   PreDFS2(root);
   printf("\n非递归深度优先遍历：后序遍历\n");
   PostDFS(root);
   printf("\n");
   PostDFS2(root);
   printf("\n非递归深度优先遍历：中序遍历\n");
   InDFS(root);
   printf("\n");
   InDFS2(root);

   printf("\n广度优先遍历\n");
   BFS(root);
   printf("\n递归广度优先遍历\n");
   RecurtionBFS(root);
   printf("\n");
   printf("树的深度:%d\n",Depth(root));
}

3.练习

中序遍历.png
前序遍历.png
后序遍历.png
层次遍历.png

练习

相关文章

  • 高级数据结构和算法3：树的遍历

    树的遍历，是指依照一定的规律不反复地訪问（或取出节点中的信息，或对节点做其它的处理）树中的每个节点，遍历是将非线性...

  • 二叉树的遍历

    数据结构算法 二叉树的遍历

  • 关于函数递归和迭代的转化, 及尾递归相关知识的接触和思考

    javascript实现数据结构： 树和二叉树,二叉树的遍历和基本操作 js 二叉树 【数据结构与算法】深入浅出递...

  • 常见数据结构

    参考文档数据结构中的树Bit-map空间压缩和快速排序去重浅谈算法和数据结构: 七 二叉查找树Java遍历树（深度...

  • 图的深度优先遍历

    数据结构遍历的意义 树的遍历 图的遍历 树的前序遍历 图遍历和树遍历区别 知识回顾 树的深度优先遍历 普通函数和递...

  • 数据结构导读目录

    数据结构(1)-常见数据结构数据结构(2)-栈和队列和Hash表数据结构(3)-树和二叉树的遍历数据结构(4)-二...

  • 数据结构与算法目录

    操作系统目录 哈希树遍历链表数组排序堆与栈队列高级算法

  • 深度优先算法 DFS

    Depth First Search(DFS)数据结构中图的遍历方式之一（可以看做树的先序遍历）算法思想：从开始结...

  • 二叉树遍历算法

    摘要：二叉树主要有3种遍历算法，分为为先序、中序、后序。本文对二叉树的3种遍历算法的遍历规则进行介绍，并给出3种遍...

  • 二叉树的四种遍历方法

    二叉树的数据结构 1、前序遍历（递归） 2、中序遍历（递归） 3、后序遍历（递归） 4、层次遍历（队列）

网友评论

      本文标题：高级数据结构和算法3：树的遍历

      本文链接：https://www.haomeiwen.com/subject/bzqhrctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|高级数据结构和算法3：树的遍历|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！