几种特殊的二叉树的概念

  • 满二叉树: 二叉树中的所有除叶子结点度都是 2, 即除了叶子结点, 其他所有结点都有左右孩
  • 扩充二叉树: 添加一些结点后得到的满二叉树就叫作扩充二叉树. 扩充二叉树新加入的结点称为外部结点, 原来的结点称为内部结点
  • 完全二叉树: 最后一层左到右填充孩子结点, 可以满也可以不满
  • 搜索二叉树: 有大小顺序, 对于某个子树都有 左 < 根 < 右
  • 平衡二叉树: 搜索二叉树的特殊版本, 保持任意子树 左 < 根 < 右, 而且任意子树的左右子结点的高度差 < 2

根据上面的, 满二叉树是完全二叉树的充分条件

实现

二叉树常使用链表实现, 不过在某些特殊的二叉树中使用数组实现更为方便, 比如

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 树的结点
type Node struct {
    val interface{} // 指向数据
    left *Node // 左孩子
    right *Node // 右孩子
}

// 二叉树的实现
type BinaryTree struct {
	root *Node // 头结点
	len  int   // 树的长度
}

二叉树遍历

  1. 深度遍历, 即从根结点访问到叶子结点再返回, 有前序, 中序, 后序遍历三种.

    这三种遍历记忆方法便是这是针对根来说, 序便是访问根的位置. 根左右, 左根右, 左右根

  2. 宽度遍历, 即层级遍历, 从左往右访问完一层后再访问下一层

使用递归实现

对于三种时序遍历来说, 使用递归都是很简单, 代码是一样的, 只是在访问结点的时机不同

树深度遍历顺序
树深度遍历顺序

  • 前序遍历
1
2
3
4
5
6
7
func recusivPreOrderTraversal(root *Node) {
	if root != nil { // 当前结点不存在时退出
		fmt.Printf("%s ", root.data) // 访问结点
		recusivPreOrderTraversal(root.left) // 找左孩子
		recusivPreOrderTraversal(root.right) // 找右孩子
	}
}
  • 中序遍历
1
2
3
4
5
6
7
func recusivInOrderTraversal(root *Node) {
	if root != nil {
		recusivInOrderTraversal(root.left)
		fmt.Printf("%s ", root.data)
		recusivInOrderTraversal(root.right)
	}
}
  • 后序遍历
1
2
3
4
5
6
7
func recusivPostOrderTraversal(root *Node) {
	if root != nil {
		recusivPostOrderTraversal(root.left)
		recusivPostOrderTraversal(root.right)
		fmt.Printf("%s ", root.data)
	}
}

非递归的遍历实现

  • 前序遍历
  1. 使用一个栈来保存遍历过的结点, 在首次遍历到结点时, 便调用访问方法
  2. 保存父结点, 其左孩子到栈中, 循环判断直到末尾的叶子结点
  3. 弹出栈中结点, 转到当前结点的右孩子
  4. 结点为空或者栈中没有结点时结束循环
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func stackPreOrderTraversal(node *Node) {
	stack := &Stack{}
	for node != nil || !stack.isEmpty() {
		for node != nil {
			fmt.Printf("%s ", node.data)
			stack.push(&StackNode{data: node})
			node = node.left
		}

		if !stack.isEmpty() {
			stackNode := stack.pop()
			node = stackNode.data.right
		}
	}
}
  • 中序遍历

同样使用一个栈来保存一遍历到的结点, 跟前序遍历只有一个不同, 访问结点的时间在弹出结点时

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// 中序-非递归栈实现
func stackInOrderTraversal(node *Node) {
	stack := &Stack{}
	for node != nil || !stack.isEmpty() {
		// 找到最底层的左子树叶子结点
		for node != nil {
			stack.push(&StackNode{data: node})
			node = node.left
		}

		// 现在栈里最顶结点就是树里最左的叶子结点 A
        // 将其弹出后, 转到该结点的右孩子, 之后在右子树做相同循环
        // 如果此时这个右孩子已经是叶子结点, 那么 A 就是一个父结点
        // 如果 A 没有右孩子, 那重回上面循环时, node != nil 为 false, 便再把 A 的父结点弹出
		if !stack.isEmpty() {
			stackNode := stack.pop()
			fmt.Printf("%s ", stackNode.data.data)
			node = stackNode.data.right
		}
	}
}
  • 后序遍历

后序遍历的非递归方法比较复杂, 在遍历时我们在把结点压入栈前第一次访问到, 在弹出栈时第二次访问到

后遍历的顺序是左右根, 栈的访问是先进后出, 如果压入栈的顺序的是根右左便可, 我们使用另一个栈来保存这个顺序

这个顺序和前序遍历的相似, 将前序先访问左孩子改为先访问右孩子即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 双栈方式实现后序遍历
func doubleStackPostOrderTraversal(node *Node) {
	s1 := &Stack{}
	s2 := &Stack{}
	for node != nil || !s1.isEmpty() {
		for node != nil {
			s1.push(&StackNode{data: node})
			s2.push(&StackNode{data: node})
            // 先访问右孩子
			node = node.right
		}

		if !s1.isEmpty() {
			stackNode := s1.pop()
            // 转到左孩子
			node = stackNode.data.left
		}
	}

    // 访问栈中的结点
	for !s2.isEmpty() {
		fmt.Printf("%s ", s2.pop().data.data)
	}
}

也可以使用一个栈来做遍历, 首先我们遍历到最左边的叶子结点, 这时弹出的叶子结点, 然后访问. 然后我们再转到右子树, 所以我们需要将父结点弹出, 但这里有一个问题, 根结点是最后才访问的, 那么这个父结点需要再重新入栈, 这个如何判断入栈便是一个难点

父结点弹出来后

  1. 首先判断父结点是否有右孩子, 如果没有, 那么便应该访问
  2. 或者如果父结点的右孩子已经被访问过, 那便应该访问. 则我们需要一个标记, 标记这个右结点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func stackPostOrderTraversal(node *Node) {
	s1 := &Stack{}
	var pre *Node
	for node != nil || !s1.isEmpty() {
		for node != nil {
			s1.push(&StackNode{data: node})
			node = node.left
		}

		if !s1.isEmpty() {
			// 经过上面循环, 以某个结点为子树的话, 栈中要么是父结点, 要么是左结点
			// 如果有右子结点, 那说明这个一个父结点, 根据后序左右根规则, 需要将父结点重新入栈
			// 然后转到右子树, 入栈右子树, 然后这个右结点会被入栈
			// 假设某个右叶子结点, 在此时出栈, 那么其符合条件 1, 此时记录下这个结点
			// 然后下一次出栈的就是它的父结点, 此时对比父结点的右结点 == 上次我们记录的结点
			stackNode := s1.pop()
			if stackNode.data.right == nil || pre == stackNode.data.right {
				fmt.Printf("%s ", stackNode.data.data)
				pre = stackNode.data
				// 当左结点没有了右子结点, 那说明这个结点是左叶子结点, 则应该访问左叶子结点
				// 此时应该把结点置空, 这样下次循环时便跳过
				node = nil
			} else {
				// 重新入栈父结点
				s1.push(stackNode)
				node = stackNode.data.right
			}
		}
	}
}

层级遍历

层级遍历使用一个队列辅助访问顺序, 先访问完一层后再访问下一层

入队的时机在每个结点在出队时为访问时机, 判断是否有左右孩子, 将左右孩子每分别入队, 这样循环便可以遍历完所有结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 链表队列
type Queue struct {
	head *QueueNode // 队列头
	tail *QueueNode // 队列尾
}

// 链表结点
type QueueNode struct {
	data *Node
	next *QueueNode
}

// 添加到队首
func (q *Queue) offer(node *QueueNode) {
	if q.tail == nil {
		q.head = node
		q.tail = node
	} else {
		q.tail.next = node
		q.tail = node
	}
}

// 从队列中取出
func (q *Queue) poll() *QueueNode {
	if q.head == nil {
		return nil
	}

	node := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return node
}

// 层级遍历
func levelTraversal(root *Node) {
	if root == nil {
		return
	}

	queue := Queue{}
	queue.offer(&QueueNode{data: root})
	for {
		node := queue.poll()
		if node == nil {
			break
		}
		fmt.Printf("%s ", node.data.data)
		if node.data.left != nil {
			queue.offer(&QueueNode{data: node.data.left})
		}

		if node.data.right != nil {
			queue.offer(&QueueNode{data: node.data.right})
		}
	}
}

代码地址: https://github.com/ivicel/zju-data-structure