二叉树的遍历 (前序、中序、后序)

树的定义本身就是递归的，因此树的基本操作用递归是很容易实现，代码也很美观，下面总结了二叉树的三种遍历方式，并用Golang进行了实现。



定义



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





图1 二叉树如图1所示，如果限制先左后右遍历，则有三种遍历方案，按照根的访问顺序不同，有：

• DLR：前序遍历

• LDR：中序遍历

• LRD：后序遍历



算法



图2 二叉树用例

节点定义统一为：



type Node struct {
	value string
	left  *Node
	right *Node
}




前序遍历



访问根，然后遍历左子树，左子树为空或已遍历才可以遍历右子树。



结合图2所示



1. 先访问根结点A，然后访问A的左子树BDE；

2. 对于左子树BCD而言，先访问根B，然后再访问左子树D；

3. 遍历D的左子树，发现为空，于是返回，遍历D的右子树，也为空，于是返回到B；

4. 访问B的右子树E，同理，E的左右子树都为空，返回到最初的根结点A，开始访问A的右子树；

5. 访问节点C，再访问C的左子树，节点为F；

6. 再访问F的左右子树，结果为G，然后返回到C；

7. 访问C的右子树，发现为空，至此，遍历结束。



最后的结果为：ABDECFG

用递归的写法为：



func preOrder(root *Node)  {
	if root == nil {
		return
	}
	fmt.Println(root.value)
	preOrder(root.left)
	preOrder(root.right)
}




中序遍历



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



结合图2所示



1. 中序遍历A的左子树BDE，对于BDE来说，再遍历B的左子树D，D的左右子树为空，所以返回D；

2. 访问B，接着访问B的右子树E，E的左右子树都为空，则返回E；

3. 至此，A的左子树访问完毕，则访问根结点A，接着访问A的右子树CFG；

4. 先访问C的左子树F，F的左子树为空，则访问根结点F，再访问F的右子树G；

5. G的左右子树都为空，则返回G；

6. C的左子树遍历完毕，返回C，再访问C的右子树，为空，则遍历结束。



最后返回结果为：DBEAFGC

用递归实现为：



func inOrder(root *Node)  {
	if root == nil{
		return
	}
	inOrder(root.left)
	fmt.Println(root.value)
	inOrder(root.right)
}




###后序遍历



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



结合图2所示



1. 先遍历A的左子树BDE，对于BDE而言先遍历B的左子树D；

2. D的左右子树为空，返回D，再遍历B的右子树E；

3. E的左右子树为空，返回E，再访问根结点B，至此，BDE遍历结束；

4. 再遍历A的右子树；

5. 先遍历C的左子树，F的左子树为空，则遍历F的右子树G，G的左右子树为空，则返回G；

6. 再访问F，接着遍历C的右子树，为空，于是访问C；

7. 最后访问根结点A，至此，遍历结束。



最后返回结果为：DEBGFCA

用递归实现为：



func posOrder(root *Node)  {
	if root == nil{
		return
	}
	posOrder(root.left)
	posOrder(root.right)
	fmt.Println(root.value)
}