数据结构学习:树的遍历 前序 中序 后序 层序

小麦大叔 发表于 2022/01/01 00:02:59 2022/01/01
【摘要】 文章目录 树的遍历深度优先遍历前序遍历(Pre Order Traversal)中序遍历(In Order Traversal)后序遍历(Post Order Traversal) 广度有限...

树的遍历

树的遍历(也称为树的搜索),树的遍历指的是按照某种规则,不重复地访问某种树的所有节点的过程。树的遍历不同于链表,队列,栈这些线性数据结构,树结构有多种不同的遍历方式,可以分为:

  • 深度优先遍历 :前序遍历/中序遍历/后序遍历
  • 广度优先遍历
    二者的区别在于
    深度优先搜索先访问子节点,再访问父节点,最后是第二个子节点;
    广度优先搜索先访问第一个子节点,再访问第二个子节点,最后访问父节点;

深度优先遍历

下面,对下图所示的二叉树进行深度优先遍历,同样,结果不唯一,将按照前序/中序/后序分别加以区分;
在这里插入图片描述

前序遍历(Pre Order Traversal)

前序遍历指的是先访问根,然后再访问子树的遍历方式;

F, B, A, D, C, E, G, I, H.

中序遍历(In Order Traversal)

  • 先访问左子树,然后访问根,再访问右子树;

或者

  • 先访问右子树,然后访问根,再访问左子树;

不过,一般按照第一种的方式进行中序遍历;

A, B, C, D, E, F, G, H, I.

后序遍历(Post Order Traversal)

先访问子树,再访问根的遍历方式;

A, C, E, D, B, H, I, G, F.

广度有限遍历

层序遍历(Level Order Traversal)

下图的遍历结果 F, B, G, A, D, I, C, E, H.
在这里插入图片描述

C++四种遍历实现

根据下图所示的二叉树,分别进行四种遍历的C++程序的实现,可以预先根据上面遍历的规则,计算四种遍历的结果,对比一下程序;
在这里插入图片描述

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 50
using namespace std;

class TreeNode {
public:
	TreeNode(int x) : vali(x),valc(0),lchild(nullptr), rchild(nullptr) {}
	TreeNode(char x) : vali(0), valc(x), lchild(nullptr), rchild(nullptr) {}
	TreeNode(const TreeNode& treenode) {
		vali = treenode.vali;
		valc = treenode.valc;
	}
	char valc;
	int vali;
	TreeNode *lchild;
	TreeNode *rchild;

	static void post_order_traversal(TreeNode *root) {
		if (root->lchild != NULL)
			post_order_traversal(root->lchild);
		if (root->rchild != NULL)
			post_order_traversal(root->rchild);
		// Do Something with root
		cout << root->valc << " ";
	}
	static void in_order_traversal(TreeNode *root) {
		if (root->lchild != NULL)
			in_order_traversal(root->lchild);
		// Do Something with root
		cout << root->valc << " ";
		if (root->rchild != NULL)
			in_order_traversal(root->rchild);
	}

	static void pre_order_traversal(TreeNode *root) {
		// Do Something with root
		cout << root->valc << " ";
		if (root->lchild != NULL)
			pre_order_traversal(root->lchild);
		if (root->rchild != NULL)
			pre_order_traversal(root->rchild);
	}
	static void layer_traver(TreeNode *root) {
		int head = 0, tail = 0;
		TreeNode *p[SIZE] = { nullptr };
		TreeNode *tmp;
		if (root != nullptr) {
			p[head] = root;
			tail++;
			// Do Something with p[head]			
		} else {
			return;
		}
		//环形队列作为缓冲器
		while (head % SIZE != tail % SIZE) {			
			tmp = p[head % SIZE];
			// Do Something with p[head]			
			cout << tmp->valc << " ";
			if (tmp->lchild != NULL) { // left
				p[tail++ % SIZE] = tmp->lchild;				
			}
			if (tmp->rchild != NULL) { // right
				p[tail++ % SIZE] = tmp->rchild;				
			}
			head++;
		}
		return;
	}	
	
	static void layer_traver_stl(TreeNode *root) {
		queue<TreeNode*> node_list;
		TreeNode *tmp;
		if (root != nullptr) {
			node_list.push(root);
			// Do Something with p[head]			
		}
		else {
			return;
		}
		while (node_list.size()) {		
			tmp = node_list.front();
			node_list.pop();
			cout << tmp->valc << " ";
			if (tmp->lchild != NULL) { // left
				node_list.push(tmp->lchild);
			}
			if (tmp->rchild != NULL) { // right
				node_list.push(tmp->rchild);
			}
		}
		return;
	}
};

int main() {
	TreeNode root('A');

	TreeNode node1('B');
	TreeNode node2('C');
	TreeNode node3('D');
	TreeNode node4('E');
	TreeNode node5('F');
	TreeNode node6('G');
	TreeNode node7('H');
	TreeNode node8('I');
	TreeNode node9('J');
	TreeNode node10('K');
	
	root.lchild = &node1;
	node1.lchild = &node3;
	node1.rchild = &node4;
	node3.lchild = &node7;
	node3.rchild = &node8;
	node4.lchild = &node9;
	root.rchild = &node2;
	node2.lchild = &node5;
	node2.rchild = &node6;
	node6.lchild = &node10;

	cout << "\n前序遍历:";
	TreeNode::pre_order_traversal(&root);
	cout << "\n中序遍历:";
	TreeNode::in_order_traversal(&root);
	cout << "\n后序遍历:";
	TreeNode::post_order_traversal(&root);
	cout << "\n层序遍历01:";
	TreeNode::layer_traver(&root);
	cout << "\n层序遍历02:";
	TreeNode::layer_traver_stl(&root);
	getchar();
	return 0;
}

  
 
  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134

程序最终运行结果如下:
在这里插入图片描述

二叉树遍历的其他例子

下面额外在网络上收集了多个二叉树,可以对照着练习一下,这样就可以搞懂前序/中序/后序遍历的方式,结合代码,理解具体的实现;
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

参考

树的遍历

文章来源: great.blog.csdn.net,作者:小麦大叔,版权归原作者所有,如需转载,请联系作者。

原文链接:great.blog.csdn.net/article/details/95768639

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。