二叉树的三种遍历方式（先序、中序、后序）（PerOrder、InOrder、PostOrder）_inorder postorder

一、二叉树的遍历（图片来源于网络）
二叉树的遍历方式分为三种：先序遍历、中序遍历、后序遍历。

1. 先序遍历：根–左--右
2. 中序遍历：左–根--右
3. 后序遍历：左–右--根

二、先序遍历

1. 创建节点

struct Node//创建节点
{
	Node left;
	Node right;
	int value;
};
1
2
3
4
5
6

2. 递归实现先序遍历

void PerOrder(Node head)//遍历节点
{
	if (head == NULL)
		return;
	cout << head->value;
	PerOrder(left);
	PerOrder(right);
}
1
2
3
4
5
6
7
8

3. 栈结构实现先序遍历
   原理：使用的是栈，所以先打印根节点数据，然后放入右孩子，再放入左孩子，取出元素时，就可以现取出左孩子，再取出右孩子。

三、中序遍历

1. 创建节点

struct Node//创建节点
{
	Node left;
	Node right;
	int value;
};
1
2
3
4
5
6

2. 递归实现中序遍历

void InOrder(Node head)
{
	if (head == NULL)
		retun;
		InOrder(head.left);
	cout << head.value<<"  ";//若左孩子为空，则输出叶子节点
		InOrder(head.right);
}
1
2
3
4
5
6
7
8

3. 栈结构实现中序遍历
   原理：当节点不为空时，将节点放入栈中，将指向指向左孩子，当左孩子为空时就打印栈顶数据，并且栈顶节点出栈，节点右孩子入栈。

void InOrder(Node head)
{
	if (head == NULL)
		return;
	stack < Node> q;
	while (!q.empty)
	{
		if (head != NULL)
		{
			q.push(head);
			head = head.left;
		}
		else if (head == NULL)
		{
			head = q.top();
			q.pop();
			cout << head.value << "  ";//若左孩子为空，则输出叶子节点
			head = head.right;
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四、后序遍历

1. 创建节点

struct Node
{
	Node left;
	Node right;
	int value;
};
1
2
3
4
5
6

2. 递归实现后序遍历

void PostOrder(Node head)
{
	if (head == NULL)
		return;
	    PostOrder( head.left);
		PostOrder(head.right);
	cout << head.value << "  ";

}
1
2
3
4
5
6
7
8
9

3. 栈结构实现后序遍历
   原理：压栈顺序：根节点–右孩子–左孩子，然后逆序，再打印数据

void PostOrder(Node head)
{
	if (head == NULL)
		return;
	stack<Node> q;
	stack<Node>p;
	q.push(head);
	while (!q.empty)
	{
		head = q.top();
		p.push(head);
		if (head.left != NULL)
			q.push(head.left);
		if (head.right != NULL)
			q.push(head.right);
	}
	while (!p.empty)
	{
		cout << p.top().value << "  ";
		p.pop();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22