树的遍历算法

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟
前序、中序、后序的递归和非递归实现

树的遍历算法

1、前序遍历

  • 递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 前序遍历
void dfsPreOrder( Tree* pRoot ){
	if(pRoot == nullptr)
		return;
	Tree* pointer = pRoot;
 
	cout << pointer->val;
 
	if(pointer->left)
		dfsPreOrder(pointer->left);
	if(pointer->right)
		dfsPreOrder(pointer->right);
	return;
}
  • 非递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFS(Tree* pRoot){
  if(pRoot == nullptr)
    return;
	stack<Tree*> nodes;
	Tree* pointer = pRoot;
	nodes.push(pointer);
 
	while(!node.empty()){
		// 遍历根结点
		pointer = nodes.top();		
		nodes.pop();
		cout << pointer->val;
 
		// 遍历右子树 因为是栈，所以先将右子树结点存入，那么就后访问它
		if(pointer->right)		
			nodes.push(pointer->right);
 
		// 遍历左子树
		if(pointer->left)			
			nodes.push(pointer->left);
	}
	return;
}

2、中序遍历

  • 递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 中序遍历
void dfsMidOrder( Tree* pRoot ){
	if( pRoot == nullptr )
		return;
	Tree* pointer = pRoot;
 
	if(pointer->left)
		dfsMidOrder(pointer->left);
	
	cout << pointer->val;
	
	if(pointer->right)
		dfsMidOrder(pointer->right);
	return;
}
  • 非递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void DFS(Tree* pRoot){
	if(pRoot == nullptr)
		return;
	stack<Tree*> nodes;
	Tree* pointer = pRoot;
	while(!node.empty() || pointer){
		while(pointer){			// 遍历左子树
			nodes.push(pointer);
			pointer = pointer->left;
		}
 
		pointer = nodes.top();		// 遍历根结点
		nodes.pop();
		cout << pointer->val;
 
		pointer = pointer->right;	// 遍历右子树
	}
	return;
}

3、后序遍历

  • 递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 后序遍历
void dfsLastOrder(Tree* pRoot){
	if(pRoot == nullptr)
		return;
	Tree* pointer = pRoot;
 
	if(pointer->left)
		dfsLastOrder(pointer->left);
 
	if(pointer->right)
		dfsLastOrder(pointer->right);
 
	cout << pointer->val;
 
	return;
}
  • 非递归形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void DFS(Tree* pRoot){
	if(pRoot == nullptr)
		return;
	stack<Tree*> nodes;
	Tree* pointer = pRoot;
	Tree* right_pointer = nullptr;
 
	while(!node.empty() || temp_ptr){
		// 一直走到左下角
		while(pointer){
			nodes.push(pointer);
			pointer = pointer->left;
		}
		pointer = nodes.top();
 
		// 右子树为空或者已访问，输出当前节点
		if(pointer->right == nullptr || pointer->right == right_pointer){
			cout << pointer->val;
 
			// 将当前结点地址赋值right_pointer作为下一次判断标志，防止重复访问
			right_pointer = pointer;
			nodes.pop();
 
			//p赋值空以便访问右子树
			pointer = nullptr;
		}else{    //访问右子树 
			pointer = pointer->right;
		}
	}
	return;
}

4、层次遍历（广度优先）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS(TreeNode* pRoot){
	queue<TreeNode*> nodeQueue;
	TreeNode* pointer = pRoot;
	if( pointer == nullptr )
		return;
 
	nodeQueue.push(pointer);
	
	while(!nodeQueue.empty()){
		pointer = nodeQueue.front();
		nodeQueue.pop();
		cout << pointer->val;
		if(pointer->left)
			nodeQueue.push(pointer->left);
		if(pointer->right)
			nodeQueue.push(pointer->right);
	}
	return;
}

应用

1、计算树的层数

  • 递归方式
1
2
3
4
5
6
7
8
int TreeDepth(TreeNode* pRoot){
    if(pRoot == NULL){
        return 0;
    }
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);
    return left > right ? left+1 : right+1;
}
  • 非递归方式（层次遍历应用）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int TreeDepth(TreeNode* pRoot) {
    if (!pRoot) return 0;
    queue<TreeNode*> que;
    que.push(pRoot);
    int depth=0;
    while (!que.empty()) {
        int size=que.size();
        depth++;
        for (int i=0;i<size;i++) {      //一次处理一层的数据
            TreeNode *node=que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
    }
    return depth;
}