二叉树

回顾整理二叉树遍历相关内容。 对于二叉树而言，其遍历有两种方式，一种是深度优先，即先优先向下进行遍历，一种是广度优先，逐层向下遍历。

二叉树结构

type Tree struct {
	Val   int
	Left  *Tree
	Right *Tree
}

深度优先搜索

Deepth-First-Search DFS， 对于深度优先而言，又有三种方式，即前序，中序和后序。前中后序之间的前中后，指的是根结点的位置。

前序递归

func PreOrder(root *Tree) []int {
    var result []int
    if root == nil {
          return result
    }
    result = append(result, root.Val)
    result = append(result, PreOrder(root.Left)...)
    result = append(result, PreOrder(root.Right)...)
    return result
}

前序非递归

func PreOrderNonRecursive(root *Tree) []int {
	var result []int
	if root == nil {
		return result
	}
	stack := list.New()
	p := root
	for p != nil || stack.Len() != 0 {
		for p != nil {
			result = append(result, p.Val)
			stack.PushBack(p)
			p = p.Left
		}
		if stack.Len() != 0 {
			node := stack.Back()
			stack.Remove(node)
			p = node.Value.(*Tree).Right
		}
	}
	return result
}

中序递归

func InOrder(root *Tree) []int {
	var result []int
	if root == nil {
		return nil
	}
	result = append(result, PreOrder(root.Left)...)
	result = append(result, root.Val)
	result = append(result, PreOrder(root.Right)...)
	return result
}

中序非递归

func InOrderNonRecursive(root *Tree) []int {
	var result []int
	if root == nil {
		return result
	}
	stack := list.New()
	p := root
	for p != nil || stack.Len() != 0 {
		for p != nil {
			stack.PushBack(p)
			p = p.Left
		}
		if stack.Len()  != 0 {
			node := stack.Back()
			stack.Remove(node)
			result = append(result, node.Value.(*Tree).Val)
			p = node.Value.(*Tree).Right
		}
	}
	return result
}

后序递归

func PostOrder(root *Tree) []int {
	var result []int
	if root == nil {
		return nil
	}
	result = append(result, PreOrder(root.Left)...)
	result = append(result, PreOrder(root.Right)...)
	result = append(result, root.Val)
	return result
}

后序非递归

func PostOrderNonRecursive(root *Tree) []int {
	var result []int
	if root == nil {
		return result
	}
	stack := list.New()
	p := root
	lastVisit := new(Tree)
	for p != nil || stack.Len() != 0 {
		for p != nil {
			stack.PushBack(p)
			p = p.Left
		}
		if stack.Len() != 0 {
			node := stack.Back()
			if node.Value.(*Tree).Right != nil && lastVisit != node.Value.(*Tree).Right {
				p = node.Value.(*Tree).Right
				continue
			}
			result = append(result, node.Value.(*Tree).Val)
			stack.Remove(node)
			lastVisit = node.Value.(*Tree)
		}
	}
	return result
}

广度优先搜索

Breadth-First-Search BFS 或者说是 Level Traversal，对于广度优先而言，其基于队列的数据结构，可以很简单的实现出来

func LevelTraversal(root *Tree) []int {
	var result []int
	if root == nil {
		return result
	}
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() != 0 {
		node := queue.Front()
		nTree := node.Value.(*Tree)
		queue.Remove(node)
		if nTree == nil {
			continue
		}
		result = append(result, nTree.Val)
		queue.PushBack(nTree.Left)
		queue.PushBack(nTree.Right)
	}
	return result
}

需要注意在for循环里，不能直接用 node.Value.(*Tree) == nil 来判断，因为interface特性，会认为其不为 nil，哪怕nTree为nil。 详细内容，可以参考 go interface机制，这里侧重算法，不再细讲。

• 总结
  • 二叉树遍历分为两种，一种是深度优先，一种是广度优先
  • 深度优先分为前，中，后序三种实现方式
  • 深度优先可以使用递归和非递归两种方式实现
  • 深度优先主要借助栈来实现
  • 广度优先主要借助队列来实现