二叉树

满足以下两个条件的树就是二叉树：

• 本身是有序树
• 树中包含的各个节点的度不能超过2，即只能是：0、1、2

定义二叉树的结构

type Node struct {
	Left  *Node
	Data  interface{}
	Right *Node
}

先序遍历

其思想是：

1. 访问根节点；
2. 访问当前节点的左子树；
3. 若当前节点无左子树，则访问当前节点的右子树；

以图为例：

1. 访问该二叉树的根节点，找到节点1；
2. 访问节点1的左子树，找到节点2；
3. 访问节点2的左子树，找到节点4；
4. 访问节点4的左子树失败，访问节点4的右子树失败，结束节点4的查询。继续查找节点2的右子树，找到节点5；
5. 访问节点5的左子树失败，访问节点5的右子树失败，结束节点5的查询。结束节点2的查询，查询节点1的右子树，找到节点3；
6. 访问节点3的左子树，找到节点6；
7. 访问节点6的左子树失败，访问节点6的右子树失败，结束节点6的查询。继续查找节点3右子树，知道节点7；
8. 访问节点7的左子树失败，访问节点7的右子树失败，结束节点7的查询。结束节点3的查询，结束节点1的查询；

!> 顺序如下：1、2、4、5、3、6、7

递归实现

func PreOrder(n *Node) {
	if n != nil {
		fmt.Printf("%v ", n.Data)
		PreOrder(n.Left)
		PreOrder(n.Right)
	}
}

示例测试

func ExamplePreOrder() {
	PreOrder(&one)
	// Output:
	// 1 2 4 5 3 6 7
}

中序遍历

其实想是：

1. 访问当前节点的左子树；
2. 访问当前节点；
3. 访问当前节点的右子树；

以图为例：

1. 访问根节点，遍历找到左子树直到失败；找到节点4，找到节点4的右子树失败，结束节点4的遍历；
2. 访问节点4的根节点，找到节点2；
3. 访问节点2的右子树，遍历找左子树失败，找到节点5，遍历找到右子树失败，结束节点5的遍历，也结束节点2的遍历；
4. 结束节点1的左子树查询，找到节点1；
5. 遍历节点1的右子树，遍历找到左子树为6，结束节点6的遍历；
6. 找到节点3；
7. 遍历节点3的右子树，遍历找到左子树失败；找到节点7，遍历节点7的右子树失败，结束节点7的遍历；

!> 顺序如下：4，2，5，1，6，3，7

递归实现

func InOrder(n *Node) {
	if n != nil {
		InOrder(n.Left)
		fmt.Printf("%v ", n.Data)
		InOrder(n.Right)
	}
}

示例测试

func ExampleInOrder() {
	InOrder(&one)
	// Output:
	// 4 2 5 1 6 3 7
}

后续遍历

其思想是：

1. 遍历访问当前节点的左子树；
2. 遍历访问当前节点的右子树；
3. 访问当前节点；

以图为例：

1. 从根节点开始，遍历左子树直到失败，1->2->4，找到节点4，结束节点4的查询；
2. 回退到节点2，遍历右子树，找到节点5的左子树失败、右子树失败，找到节点5，结束节点5的查询；
3. 节点2的左右子树遍历完成，找到节点2，结束节点2的查询；
4. 回退到节点1，遍历右子树，1->3->6，找到节点6的左子树失败、右子树失败，找到节点6，结束节点6的查询；
5. 回到到节点3，遍历右子树，3->7，找到节点7的左子树失败、右子树失败，找到节点7，结束节点7的查询；
6. 节点3左右子树遍历完成，找到节点3，结束节点3的查询；
7. 回退到节点1，节点1左右子树遍历完成，找到节点1，结束节点1的查询；

!> 顺序为：4、5、2、6、7、3、1

递归实现

func AftOrder(n *Node) {
	if n!=nil {
		AftOrder(n.Left)
		AftOrder(n.Right)
		fmt.Printf("%v ", n.Data)
	}
}

示例测试

func ExampleAftOrder() {
	AftOrder(&one)
	// Output:
	// 4 5 2 6 7 3 1
}

层次遍历

其思想是：

1. 节点入队；
2. 节点出队，节点左孩子和右孩子入队；
3. 知道所有节点出队；

以图为例：

1. 根节点1入队；
2. 根节点1出队，找到节点1，根节点1的左孩子节点2和右孩子3节点入队；
3. 节点2出队，找到节点2，节点2的左孩子节点4和右孩子节点5入队；
4. 节点3出队，找到节点3，节点3的左孩子节点6和右孩子节点7入队；
5. 节点4出队，没有左右孩子，找到节点4；
6. 节点5出队，没有左右孩子，找到节点5；
7. 节点6出队，没有左右孩子，找到节点6；
8. 节点7出队，没有左右孩子，找到节点7；

队列实现

func LayerOrder(n *Node) {
	queue := list.New()
	queue.PushBack(n)
	for queue.Len() > 0 {
		header := queue.Front()
		v := header.Value.(*Node)
		fmt.Print(v.Data," ")
		queue.Remove(header)
		if v.Left != nil {
			queue.PushBack(v.Left)
		}
		if v.Right != nil {
			queue.PushBack(v.Right)
		}
	}
}

示例测试

func ExampleLayerOrder() {
	LayerOrder(&one)
	// Output:
	// 1 2 3 4 5 6 7
}