程序员经验分享-hwhale

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

2023-10-27

3 树的遍历

树的遍历，是指依照一定的规律不反复地访问树中的每个节点，遍历是将非线性的树状结构按一定规律转化为线性结构。

3.1 多叉树遍历

多叉树遍历分为深度优先遍历和广度优先遍历两类。

3.1.1 深度优先遍历 (Depth First Search,DFS)

在这里插入图片描述
深度优先遍历：从根节点开始先沿着树的一个枝遍历到叶子节点，再遍历其他的枝。深度优先遍历又分为先序遍历和后序遍历。

3.1.1.1 先序遍历

树中父节点先于子节点访问
在这里插入图片描述
上图树的先序遍历结果：A → B → D → G → H → I → C → E → J → F

通常先序遍历实现分两种方式：递归方式和非递归方式(栈方式)。

  • 深度优先先序遍历：递归
#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
    char val;
    vector<Node*> children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void preorder(Node* root){
    if(nullptr == root) return;
    cout << root->val << " ";
    for(auto child:root->children){
    	preorder(child);
    }
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
    Node h('H');
    Node i('I');
    Node j('J');

    a.AppendChild(&b);
    a.AppendChild(&c);
    b.AppendChild(&d);
    c.AppendChild(&e);
    c.AppendChild(&f);
    d.AppendChild(&g);
    d.AppendChild(&h);
    d.AppendChild(&i);
    e.AppendChild(&j);
    
    preorder(&a);
    cout << endl;
}

A B D G H I C E J F
  • 深度优先先序遍历：迭代
#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
    char val;
    vector<Node*> children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void preorder(Node* root){
    vector<Node*> s;
    s.push_back(root);
    while(!s.empty()){
    	Node* cur = s.back();
		s.pop_back();
		cout << cur->val << " ";
        auto& child = cur->children;
		for(auto it = child.rbegin();it != child.rend();++it){
	    	s.push_back(*it);
		}
    }
    cout << endl;
}
void preorder2(Node* root){
    stack<Node*> s;
    s.push(root);
    while(!s.empty()){
        Node* cur = s.top();
        s.pop();
        cout << cur->val << " ";
        auto& child = cur->children;
        for(auto it = child.rbegin();it != child.rend();++it){
            s.push(*it);
        }
    }
    cout << endl;
}

int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
    Node h('H');
    Node i('I');
    Node j('J');

    a.AppendChild(&b);
    a.AppendChild(&c);
    b.AppendChild(&d);
    c.AppendChild(&e);
    c.AppendChild(&f);
    d.AppendChild(&g);
    d.AppendChild(&h);
    d.AppendChild(&i);
    e.AppendChild(&j);
    
    cout << "vector:";
    preorder(&a);
    cout << "stack:";
    preorder2(&a);
}

vector:A B D G H I C E J F 
stack:A B D G H I C E J F

3.1.1.2 后序遍历

树中子节点先于父节点访问
在这里插入图片描述
上图树的后序遍历结果：G → H → I → D → B → J → E → F → C → A

  • 深度优先后序遍历：递归
#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
    char val;
    vector<Node*> children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void postorder(Node* root){
    if(nullptr == root) return;
    for(auto child:root->children){
    	postorder(child);
    }
    cout << root->val << " ";
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
    Node h('H');
    Node i('I');
    Node j('J');

    a.AppendChild(&b);
    a.AppendChild(&c);
    b.AppendChild(&d);
    c.AppendChild(&e);
    c.AppendChild(&f);
    d.AppendChild(&g);
    d.AppendChild(&h);
    d.AppendChild(&i);
    e.AppendChild(&j);
    
    postorder(&a);
    cout << endl;
}

G H I D B J E F C A
  • 深度优先后序遍历：迭代
#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
    char val;
    vector<Node*> children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void postorder(Node* root){
    vector<Node*> s;
    vector<Node*> t;
    s.push_back(root);
    while(!s.empty()){
    	Node* cur = s.back();
		s.pop_back();
		t.push_back(cur);
		auto& child = cur->children;
		for(auto it = child.begin();it != child.end();++it){
	    	s.push_back(*it);
		}
    }
    while(!t.empty()){
    	cout << t.back()->val << " ";
		t.pop_back();
    }
    cout << endl;
}
void postorder2(Node* root){
    stack<Node*> s;
    stack<Node*> t;
    s.push(root);
    while(!s.empty()){
        Node* cur = s.top();
        s.pop();
        t.push(cur);
        auto& child = cur->children;
        for(auto it = child.begin();it != child.end();++it){
            s.push(*it);
        }
    }
    while(!t.empty()){
        cout << t.top()->val << " ";
        t.pop();
    }
    cout << endl;
}

int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
    Node h('H');
    Node i('I');
    Node j('J');

    a.AppendChild(&b);
    a.AppendChild(&c);
    b.AppendChild(&d);
    c.AppendChild(&e);
    c.AppendChild(&f);
    d.AppendChild(&g);
    d.AppendChild(&h);
    d.AppendChild(&i);
    e.AppendChild(&j);
    
    cout << "vector:";
    postorder(&a);
    cout << "stack:";
    postorder2(&a);
}

vector:G H I D B J E F C A 
stack:G H I D B J E F C A

3.1.2 广度优先遍历 (Breath First Search,BFS)

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

上图树的广度优先遍历结果：A → B → C → D → E → F → G → H → I → J

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Node{
public:
    char val;
    vector<Node*> children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void bfs(Node* root){
    if(nullptr == root) return;
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
    	auto cur = q.front();
		q.pop();
		cout << cur->val << " ";
		for(auto child:cur->children){
	    	q.push(child);
		}
    }
    cout << endl;
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
    Node h('H');
    Node i('I');
    Node j('J');

    a.AppendChild(&b);
    a.AppendChild(&c);
    b.AppendChild(&d);
    c.AppendChild(&e);
    c.AppendChild(&f);
    d.AppendChild(&g);
    d.AppendChild(&h);
    d.AppendChild(&i);
    e.AppendChild(&j);

    bfs(&a);    
}

A B C D E F G H I J

3.2 二叉树遍历

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

class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(int val):val(val),left(nullptr),right(nullptr){}
    Node(int val,Node* left,Node* right):val(val),left(left),right(right){}
};

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

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

在这里插入图片描述

3.2.1 深度优先遍历

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

3.2.1.1 前序遍历(Pre-order Traversal)

在这里插入图片描述

  • 前序遍历步骤：
    （1）访问根节点
    （2）递归遍历左子树
    （3）递归遍历右子树
    （4）直到所有节点都被访问。
    总结：根左右

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

3.2.1.2 后序遍历(Post-order Traversal)

在这里插入图片描述

  • 后序遍历步骤：
    （1）后序遍历左子树
    （2）后续遍历右子树
    （3）访问根节点
    （4）直到所有节点都被访问。
    总结：左右根

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

2.2.1.3 中序遍历(In-order Traversal)

在这里插入图片描述

  • 中序遍历步骤：
    （1）递归遍历左子树
    （2）访问根节点
    （3）递归遍历右子树
    （4）直到所有节点都被访问。
    总结：左根右

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

  • 深度优先遍历：递归
#include <iostream>
using namespace std;
class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}    
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}    
    void SetLeft(Node* left){
    	this->left = left;
    }
    void SetRight(Node* right){
    	this->right = right;
    }
};
//前序遍历
void preorder(Node* root){
    if(nullptr == root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}
//后续遍历
void postorder(Node* root){
    if(nullptr == root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}
//中序遍历
void inorder(Node* root){
    if(nullptr == root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
 
    a.SetLeft(&b);
    a.SetRight(&c);
    b.SetLeft(&d);
    b.SetRight(&e);
    c.SetLeft(&f);
    c.SetRight(&g);

    cout << "前序遍历结果："; 
    preorder(&a);
    cout << endl;
    cout << "后序遍历结果："; 
    postorder(&a);
    cout << endl;
    cout << "中序遍历结果："; 
    inorder(&a);
    cout << endl;
}

前序遍历结果：A B D E C F G 
后序遍历结果：D E B F G C A 
中序遍历结果：D B E A F C G
  • 深度优先遍历：迭代
#include <iostream>
#include <stack>
using namespace std;
class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}    
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}    
    void SetLeft(Node* left){
    	this->left = left;
    }
    void SetRight(Node* right){
    	this->right = right;
    }
};
//前序遍历
void preorder(Node* root){
    if(nullptr == root) return;
    stack<Node*> s;
    s.push(root);
    while(!s.empty()){
    	Node* cur = s.top();
		s.pop();
		cout << cur->val << " ";
		if(nullptr != cur->right) s.push(cur->right);
		if(nullptr != cur->left) s.push(cur->left);
    }
}
//后续遍历
void postorder(Node* root){
    if(nullptr == root) return;
    stack<Node*> s;
    stack<Node*> t;
    s.push(root);
    while(!s.empty()){
    	Node* cur = s.top();
		s.pop();
		t.push(cur);
		if(nullptr != cur->left) s.push(cur->left);
		if(nullptr != cur->right) s.push(cur->right);
    }
    while(!t.empty()){
    	cout << t.top()->val << " ";
    	t.pop();
    }
    cout << endl;
}
//中序遍历
void inorder(Node* root){
    stack<pair<Node*,bool>> s;
    s.push({root,false});
    while(!s.empty()){
    	auto [cur,vistable] = s.top();
		s.pop();
		if(vistable){
	    	cout << cur->val << " ";
		}else{
	    	if(nullptr != cur->right) s.push({cur->right,false});
	    	s.push({cur,true});
	    	if(nullptr != cur->left) s.push({cur->left,false});
		}
    }
    cout << endl;
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
 
    a.SetLeft(&b);
    a.SetRight(&c);
    b.SetLeft(&d);
    b.SetRight(&e);
    c.SetLeft(&f);
    c.SetRight(&g);

    cout << "前序遍历结果："; 
    preorder(&a);
    cout << endl;

    cout << "后序遍历结果："; 
    postorder(&a);

    cout << "中序遍历结果："; 
    inorder(&a);
}

前序遍历结果：A B D E C F G 
后序遍历结果：D E B F G C A 
中序遍历结果：D B E A F C G

改进：

#include <iostream>
#include <stack>
using namespace std;
class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}    
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}    
    void SetLeft(Node* left){
    	this->left = left;
    }
    void SetRight(Node* right){
    	this->right = right;
    }
};
//前序遍历
void preorder(Node* root){
    if(nullptr == root) return;
    stack<pair<Node*,bool>> s;
    s.push({root,false});
    while(!s.empty()){
    	auto [cur,vistable] = s.top();
		s.pop();
		if(vistable){
			cout << cur->val << " ";
		}else{
	    	if(nullptr != cur->right) s.push({cur->right,false});
	    	if(nullptr != cur->left) s.push({cur->left,false});
	    	s.push({cur,true});
		}
    }
}
//后续遍历
void postorder(Node* root){
    if(nullptr == root) return;
    stack<pair<Node*,bool>> s;
    s.push({root,false});
    while(!s.empty()){
    	auto [cur,vistable] = s.top();
		s.pop();
		if(vistable){
		cout << cur->val << " ";
		}else{
	    	s.push({cur,true});
	    	if(nullptr != cur->right) s.push({cur->right,false});
	    	if(nullptr != cur->left) s.push({cur->left,false});
		}
    }
    cout << endl;
}
//中序遍历
void inorder(Node* root){
    stack<pair<Node*,bool>> s;
    s.push({root,false});
    while(!s.empty()){
    	auto [cur,vistable] = s.top();
		s.pop();
		if(vistable){
	    	cout << cur->val << " ";
		}else{
	    	if(nullptr != cur->right) s.push({cur->right,false});
	    	s.push({cur,true});
	    	if(nullptr != cur->left) s.push({cur->left,false});
		}
    }
    cout << endl;
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
 
    a.SetLeft(&b);
    a.SetRight(&c);
    b.SetLeft(&d);
    b.SetRight(&e);
    c.SetLeft(&f);
    c.SetRight(&g);

    cout << "前序遍历结果："; 
    preorder(&a);
    cout << endl;

    cout << "后序遍历结果："; 
    postorder(&a);

    cout << "中序遍历结果："; 
    inorder(&a);
}

前序遍历结果：A B D E C F G 
后序遍历结果：D E B F G C A 
中序遍历结果：D B E A F C G

加入标志位visitable，表示当前结点能否被访问

3.2.2 广度优先遍历

在这里插入图片描述

  • 后序遍历步骤：
    （1）访问根节点
    （2）按层次从上到下依次遍历

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

#include <iostream>
#include <queue>
using namespace std;
class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}    
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}    
    void SetLeft(Node* left){
    	this->left = left;
    }
    void SetRight(Node* right){
    	this->right = right;
    }
};
int depth(Node* root){
    if(nullptr == root) return 0;
    return max(depth(root->left),depth(root->right))+1;
}
void level(Node* root,int n){
    if(n == 0){
    	cout << root->val << " ";
    }
    if(root->left) level(root->left,n-1);
    if(root->right) level(root->right,n-1);
}
//广度优先遍历：递归
void bfs(Node* root){
    if(nullptr == root) return;
    int n = depth(root);
    for(int i = 0;i < n;++i){
    	level(root,i);
    }
    cout << endl;
}
//广度优先遍历：迭代
void bfs2(Node* root){
    if(nullptr == root) return;
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
    	Node* cur = q.front();
		q.pop();
		cout << cur->val << " ";
		if(nullptr != cur->left) q.push(cur->left);
		if(nullptr != cur->right) q.push(cur->right);
    }
    cout << endl;
}
int main(){
    Node a('A');
    Node b('B');
    Node c('C');
    Node d('D');
    Node e('E');
    Node f('F');
    Node g('G');
 
    a.SetLeft(&b);
    a.SetRight(&c);
    b.SetLeft(&d);
    b.SetRight(&e);
    c.SetLeft(&f);
    c.SetRight(&g);

    cout << "广度优先遍历 递归：";
    bfs(&a);
    cout << "广度优先遍历 迭代：";
    bfs2(&a);
}

广度优先遍历 递归：A B C D E F G 
广度优先遍历 迭代：A B C D E F G
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

高级数据结构和算法

数据结构

算法

深度优先

三、高级数据结构和算法：树的遍历 的相关文章

随机推荐

  • Cadence Allegro PCB设计88问解析(三十) 之 Allegro中 PCB的3D模型导出

    一个学习信号完整性仿真的layout工程师 在进行PCB投板之前 往往需要将PCB的结构发给结构的同事确认 一般会导出DXF和EMN文件 或者导出3D模型 3D模型包含版型 器件的实际3D模型等等 可以比较直观的看到PCB板上的器件情况 下

  • 【git 错误】git 使用中的问题汇总 不定期更新 git报错 Please enter a commit message to explain

    1 Please enter a commit message to explain why this merge is necessary 解决办法 1 按键盘字母 i 进入insert模式 2 修改最上面那行黄色合并信息 可以不修改 3

  • ImportError: /usr/lib/x86_64-linux-gnu/libstdc++.so.6: version `GLIBCXX_3.4.26‘ not foun Python GDAL

    前言 更新完pytorch1 9 0之后 突然GDAL包不能用了 但是代码调试的时候是正常的 本文给出具体的解决过程 提示一下 其实这种因为软件更新导致某个动态库不能通用的情况 一般的解决方法 就是在本机上查找一下有没有别的地方有 这样的解

  • ADAS先进驾驶辅助系统（Advanced Driver Assistant System）

    先进驾驶辅助系统 Advanced Driver AssistantSystem 简称ADAS 是利用安装于车上的各式各样的传感器 可侦测光 热 压力等变数 在第一时间收集车内外的环境数据 进行静 动态物体的辨识 侦测与追踪等技术上的处理

  • YOLOv7——目标检测数据集划分篇

    法一 1 准备VOC数据集 将所有数据集图片放入JPEGImages文件夹中 所有的图片对应的xml文件放入Annotations中 ImageSets文件夹中创建Main文件夹 暂时Main文件夹为空 文件夹结构 datasets Ann

  • 数据标准详细概述-2022

    1 数据标准的是什么 在实际的工作生产中 我们一般会参照国家标准 地方标准 行业标准等来进行具体的活动 来确保我们生成过程符合监管要求 便于上下游协同等 于是我们会见到如下的标准指导文件 同样 数据标准也会以文件的形式存在 在除了国标 行标

  • qq人脸更换_QQ安全中心现在怎么替换人脸设置或删除人脸?

    以下内容收集自网络 题主可以参考一下 1 我们从手机中打开QQ安全中心 如果还不是最新版本的话 请先升级到最新版本 2 在QQ安全中心首页 点击最下方的 工具 按钮 3 在 工具 页面 点击打开 实验室 这个图标 4 在打开的界面 点击打开

  • 四阶魔方玩法总结V1.0

    四阶魔方玩法总结V1 0 1 引言 今写此文 我主要是为了方便自己再次玩其魔方的时候 可以快速的想起 避免又从头学起 毕竟自己学会的 理解的 写出来的东西 再次玩魔方的时候 仅仅是回顾和追忆的过程 不存在学习 理解和消化的过程 避免再次浪费

  • 12.大数据之Hive性能优化

    hive性能调优 1 HADOOP计算框架特性 数据量大不是问题 数据倾斜是个问题 jobs数比较多的作业运行效率相对比较低 比如即使有几百行的表 如果多次关联多次汇总 产生十几个jobs 耗时很长 原因是map reduce作业初始化的时

  • 二叉树类型的常考选择题知识储备（二叉树的性质）

    1 若规定 根节点的层数为 1 则 一个非空二叉树的 第 i 层 上最多有 2i 1 i gt 0 个结点 2 若规定只有根节点的二叉树的深度为1 则 深度为 K 的二叉树的 最大结点数是 2k 1 k gt 0 3 对于任意一个二叉树 如

  • Angular管道操作符(

    一 模板表达式操作符 模板表达式语言使用了JavaScript 语法的子集 并补充了几个用于特定场景的特殊操作符 管道操作符 安全导航操作符 二 管道操作符 在绑定之前 表达式的结果可能需要一些转换 例如 可能希望吧数字显示成金额 强制文本

  • 【Web3】Mnemonic Word Create Wallet

    目录 Create Mnemonic Word 介绍 一 根据 Mnemonic Word 生成密钥对 keypair 二 通过 keypair 获取 Wallet 地址 和 private key 代码 Create Mnemonic W

  • bash: ./make.sh: /bin/sh^M: 解释器错误: 没有那个文件或目录

    原因 在Linux运行 sh文件时报上述错误 原因是因为该文件在windows系统上打开过 关闭后其中的空格符号和Linux的不同 导致这个报错 可以通过sed命令与正则的配合将文件中的空格符号替换成linux的空格 解决方法 sed i

  • 实验6

    一 MPEG 1 Audio LayerII编码器原理 1 多相滤波器组 将PCM样本变换到32个子带的频域信号 如果输入的采样频率为48kHz 那么子带的频率宽度为48 2 32 0 75Hz 缺点 1 等带宽的滤波器组与人类听觉系统的临

  • MSCOCO数据标注详解（超详细）

    博主大大 风吴痕 对MSCOCO的讲解 超级详细而且有代码举例 转发收藏 后面方便自己查看 https blog csdn net wc781708249 article details 79603522

  • SQLite 3.7.13的加密解密

    原文链接 http lancelot blog 51cto com 393579 940805 http lancelot blog 51cto com 393579 940808 http lancelot blog 51cto com

  • stata移动平均插值法mipolate命令

    stata移动平均插值法mipolate命令 xtset id year by id mipolate x3 year gen x3 1 idw 4 idw表示取移动平均的项数 结果

  • Springboot框架通过@Scheduled实现定时任务

    一 开启定时任务方法 Scheduled定时任务是Spring boot自身提供的功能 所以不需要引入Maven依赖包 在项目入口main方法上加注解 EnableScheduling 开启定时任务 二 不同定时方式的解析 1 fixedD

  • rom查找表matlab,用matlab生成查找表输出coe文件给xilinx的Mem_IPCore使用

    这是一个coe文件的例子 Sample initialization file for a 32 bit wide by 16 deep RAM 这是注释说明性文字 memory initialization radix 16 2 10 1

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

    3 树的遍历 树的遍历 是指依照一定的规律不反复地访问树中的每个节点 遍历是将非线性的树状结构按一定规律转化为线性结构 3 1 多叉树遍历 多叉树遍历分为深度优先遍历和广度优先遍历两类 3 1 1 深度优先遍历 Depth First Se

热门标签