树的应用 —— 二叉树遍历【先序、中序、后序】_二叉树前序遍历应用

树的应用 —— 二叉树遍历【先序、中序、后序】

二叉树的遍历就是按某条搜索路径访问二叉树中的每个节点一次且仅一次。

访问的含义很广，例如输出、查找、插入、删除、修改、运算等，都可以被称为访问。

遍历是有顺序的【如何进行二叉树的遍历】

一棵二叉树是由根、左子树、右子树构成的，如下图所示。

那么按照根、左子树、右子树的访问先后顺序不同，可以有6种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD，

如果限定先左后右（先左子树后右子树），则只有前3种遍历方案：DLR、LDR、LRD。

按照根的访问顺序不同，根在前面的被称为先序遍历（DLR），根在中间的被称为中序遍历（LDR），根在最后的被称为后序遍历（LRD）。

因为树的定义本身就是递归的，因此树和二叉树的基本操作用递归算法很容易实现。

【先序遍历】【根左右】

先序遍历指先访问根，然后先序遍历左子树，再先序遍历右子树，即DLR。

[算法步骤]

如果二叉树为空，则为空操作，否则：

①访问根节点；

②先序遍历左子树；

③先序遍历右子树。

[先序遍历秘籍：访问根，先序遍历左子树，在左子树为空或已遍历时才可以遍历右子树。]

[完美图解]

一棵二叉树的先序遍历过程如下。

① 访问根节点A，然后先序遍历A的左子树。

② 访问根节点B，然后先序遍历B的左子树。

③ 访问根节点D，然后先序遍历D的左子树，D的左子树为空，什么也不做，返回。

④ 先序遍历D的右子树，D的右子树为空，什么也不做，返回B。

⑤ 先序遍历B的右子树。

⑥ 访问根节点E，先序遍历E的左子树，E的左子树为空，什么也不做，返回。先序遍历E的右子树，E的右子树为空，什么也不做，返回A。

⑦ 先序遍历A的右子树。

⑧ 访问根节点C，然后先序遍历C的左子树。

⑨ 访问根节点F，然后先序遍历F的左子树，F的左子树为空，什么也不做，返回。

⑩ 先序遍历F的右子树。

⑪ 访问根节点G，先序遍历G的左子树，G的左子树为空，什么也不做，返回。先序遍历G的右子树，G的右子树为空，什么也不做，返回C。

⑫ 先序遍历C的右子树，C的右子树为空，什么也不做，遍历结束。

所以先序遍历序列为 ABDECFG。

[算法代码]

void preorder(Btree T){ //先序遍历
	if(T){
		cout << T->data << " ";
		preorder(T->lchild);
		preorder(T->rchild);
	}
}
1
2
3
4
5
6
7

【中序遍历】【左根右】

中序遍历指中序遍历左子树，然后访问根，再中序遍历右子树，即LDR。

[算法步骤]

如果二叉树为空，则为空操作，否则

①中序遍历左子树；

②访问根节点；

③中序遍历右子树。

[中序遍历秘籍]

中序遍历左子树，在左子树为空或已遍历时才可以访问根，中序遍历右子树。

[完美图解]

一棵二叉树的中序遍历过程如下。

① 中序遍历A的左子树，如下图所示。

② 中序遍历B的左子树，如下图所示

③ 中序遍历D的左子树，D的左子树为空，则访问D，然后中序遍历D的右子树，D的右子树也为空，则返回B，如下图所示。

④ 访问B，然后中序遍历B的右子树，如下图所示。

⑤ 中序遍历E的左子树，E的左子树为空，则访问E，然后中序遍历E的右子树，E的右子树也为空，则返回A，如下图所示。

⑥ 访问A，然后中序遍历A的右子树，如下图所示。

⑦ 中序遍历C的左子树，如下图所示。

⑧ 中序遍历F的左子树，F的左子树为空，则访问F，然后中序遍历F的右子树。

⑨ 中序遍历G的左子树，G的左子树为空，则访问G，然后中序遍历G的右子树，G的右子树也为空，则返回C，如下图所示。

⑩ 访问C，然后中序遍历C的右子树，G的右子树为空，遍历结束，如下图所示。

所以中序遍历序列为 DBEAFGC。

[算法代码]

void inorder(){ //中序遍历
	if(T){
		inorder(T->lchild);
		cout << T-data << " ";
		inorder(T->rchild);
	}
}
1
2
3
4
5
6
7

【后序遍历】【左右根】

后序遍历指后序遍历左子树，后序遍历右子树，然后访问根，即LRD。

[算法步骤]

如果二叉树为空，则空操作，否则

①后序遍历左子树；

②后序遍历右子树；

③访问根节点。

[后序遍历秘籍]

后序遍历左子树，后序遍历右子树，在左子树、右子树为空或已遍历时才可以访问根。

[完美图解]

一棵二叉树的后序遍历过程如下。

① 后序遍历A的左子树。

② 后序遍历B的左子树。

③ 后序遍历D的左子树，D的左子树为空，后序遍历D的右子树，D的右子树也为空，则访问D，返回B。

④ 后序遍历B的右子树。

⑤ 后序遍历E的左子树，E的左子树为空，后序遍历E的右子树，E的右子树也为空，则访问E，此时B的左、右子树都已遍历，访问B，返回A。

⑥ 后序遍历A的右子树。

⑦ 后序遍历C的左子树。

⑧ 后序遍历F的左子树，F的左子树为空，后序遍历F的右子树。

⑨ 后序遍历G的左子树，G的左子树为空，后序遍历G的右子树，G的右子树也为空，则访问G，此时F的左、右子树都已遍历，访问F，然后返回C。

⑩ 后序遍历C的右子树，C的右子树为空，此时C的左、右子树都已遍历，访问C，此时A的左、右子树都已遍历，访问A，遍历结束。

所以后序遍历序列为 DEBGFCA。

[算法代码]

void posorder(){ //后序遍历
	if(T){
		posorder(T->lchild);
		posorder(T->rchild);
		cout << T->data << " ";
	}
}
1
2
3
4
5
6
7

所以

二叉树遍历的代码非常简单明了，“cout<data;”语句在前面就是先序，在中间就是中序，在后面就是后序。

【使用投影法快速得到遍历序列】

① 中序遍历

中序遍历就像在无风的情况下，顺序为左子树、根、右子树，太阳直射，将所有节点都投影到地上。

一棵二叉树，其中序序列投影如下图所示。中序遍历序列为DBEAFGC。

② 先序遍历

先序遍历就像在左边大风的情况下，将二叉树树枝刮向右方，且顺序为根、左子树、右子树，太阳直射，将所有节点都投影到地上。

一棵二叉树，其先序遍历投影序列如下图所示。先序遍历序列为ABDECFG。

③ 后序遍历

后序遍历就像在右边大风的情况下，将二叉树树枝刮向左方，且顺序为左子树、右子树、根，太阳直射，将所有节点都投影到地上。

一棵二叉树，其后序遍历投影序列如下图所示。后序遍历序列为DEBGFCA。