::: hljs-center

二叉树的遍历

:::

以二叉树的链式存储为例,二叉树的遍历方式有以下几种

递归实现

二叉树的定义与存储
void PreOrderTraversal(T) 先序 根,左子树,右子树;
void InOrderTraversal(T) 中序 左子树,根,右子树;
void PostOrderTraversal(T) 后序 左子树,右子树,根;
void LevelOrderTraversal(T) 层次遍历 从上至下，从左到右;

先序遍历

image.png
遍历过程为:

  1. 访问 根节点
  2. 先序 遍历其左子树
  3. 先序 遍历其右子树

这样的过程采用了递归的设计，相应的代码

1
2
3
4
5
6
7
void PreOrderTraversal(BinTree BT){
	if(BT){
		cout << BT->data << endl;
		PreOrderTraversal(BT->left);
		PreOrderTraversal(BT->right);
	}
}

中序遍历

image.png
图中输出: D B E F A G H C I

遍历过程为:

  1. 中序 遍历其左子树
  2. 访问 根节点
  3. 中序 遍历其右子树

代码也就是将上面的访问根节点调换到两次子问题处理中间

1
2
3
4
5
6
7
void InOrderTraversal(BinTree BT){
	if(BT){
		PreOrderTraversal(BT->left);
		cout << BT->data << endl;
		PreOrderTraversal(BT->right);
	}
}

后序遍历

image.png
遍历过程为:

  1. 后序 遍历其左子树
  2. 中序 遍历其右子树
  3. 访问 根节点 
1
2
3
4
5
6
7
void PostOrderTraversal(BinTree BT){
	if(BT){
		PreOrderTraversal(BT->left);
		PreOrderTraversal(BT->right);
		cout << BT->data << endl;
	}
}

不管是何种次序进行遍历，遍历过程中经过节点的路线是一样的，只是访问各接点的时机不同。

中序遍历非递归实现

上面的遍历都是使用递归的形式实现，既然是递归，那肯定可以更朴素的用堆栈来完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InOrderTraversal(BinTree BT) {
	BinTree T = BT;
	Stack s = createStack(); //获取一个栈 
	while(T||!isEmpty(s)){
		while (T){ //一直向左走并将沿途节点压入堆栈 
			push(T,s);
			T = T->left;
		}
		if(!isEmpty(s)){
			T = pop(s);
			cout << T->data;
			T = T->right;
		}
	}
}

前面提到对于树的遍历,三种序列的区别也就是在第几次遇到它的时候进行访问;对于中序遍历是在第二次遇到节点的时候进行输出,所以我们设计出以下步骤,配合堆栈实现中序遍历

遇到一个节点，将它压入栈，并遍历所有左子树
当左子树遍历完之后，从栈顶pop出去并访问它
继续中序遍历刚才pop出去的节点的右子树

层序遍历

在学习层序遍历之前，要先搞懂二叉树遍历的核心问题是什么;二叉树是一个二维结构,既然是遍历,那么必然是要产生一个序列,根据不同的访问节点顺序会产生不同结果的序列,而这个序列是一维结构,所以二叉树的遍历本质问题是 二维结构的一维化

那么二维怎么变成一维?难点是什么?仔细想想上面的遍历方式,访问一个节点的前提是”你是我的右儿子” or “你是我的左儿子”,所以我们是通过一个已知的节点来访问左右儿子节点，再通过左儿子右儿子再往深层遍历;

所以访问过程中就会遇到一个问题,在遍历中,我们访问了节点的左儿子,右儿子怎么办?;如果把右儿子放弃，以后就找不到右儿子了

综上所述，我们需要一种方式来记住节点，可以使用堆栈或者队列来进行保存（例如上文的非递归中序遍历，在堆栈中保存的就是节点本身）

当使用堆栈保存的时候，存的是节点本身（即是说回溯回来的时候使用节点本身来访问左或右儿子）；而使用队列进行记忆的时候，存的是右节点（先访问左节点，再将右节点入队）

层序遍历的队列方式实现:

使用队列先进先出的特性,可以很方便的做到对二叉树进行层序遍历,基本的流程是这样的

遍历从根节点开始,首先将根节点入队,然后进行循环: 节点出队->访问该节点,其左右儿子入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct TreeNode * BinTree;
struct TreeNode{
	char data;
	BinTree left;
	BinTree right;
};

void LevelOrderTraversal(BinTree BT){
	Queue q;BinTree T;
	if(!BT) return;
	Q = createQueue();
	Add(Q,BT);
	while(!isEmpty(Q)){
		T = DeleteQ(Q);
		cout << T->data;
		if(T->left) AddQ(Q,T->left);
		if(T->right) AddQ(Q,T->right);
	}
}

队列的实现 http://www.zsenhe.com/article/85