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

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 
#include 
using namespace std;
class Node{
public:
    char val;
    vector 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 
#include 
using namespace std;
class Node{
public:
    char val;
    vector children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void preorder(Node* root){
    vector 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 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 
#include 
using namespace std;
class Node{
public:
    char val;
    vector 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 
#include 
using namespace std;
class Node{
public:
    char val;
    vector children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void postorder(Node* root){
    vector s;
    vector 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 s;
    stack 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 
#include 
#include 
using namespace std;
class Node{
public:
    char val;
    vector children;
    Node(char val):val(val){}
    void AppendChild(Node* child){
    	children.push_back(child);
    }
};
void bfs(Node* root){
    if(nullptr == root) return;
    queue 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 
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 
#include 
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 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 s;
    stack 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> 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 
#include 
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> 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> 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> 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 
#include 
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 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

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

C/C++/C#相关栏目本月热门文章