树的遍历

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

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

    深度优先遍历

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

    前序遍历(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;
}

程序最终运行结果如下:

在这里插入图片描述

二叉树遍历的其他例子

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

在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

参考

树的遍历