白筱汐

想都是问题，做都是答案

0%

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

发表于 更新于 分类于

二叉树的定义

二叉树是一种数据结构，它由一组称为节点的元素组成，这些节点通过边连接。每个节点最多可以有两个子节点，分别称为左子节点和右子节点。

树的深度优先遍历

深度优先遍历又根据处理某个子树的根结点的顺序不同，可以分为：前序遍历、中序遍历、后序遍历。

  • 前序遍历：先访问根结点,再访问左子结点,最后访问右子结点。
  • 中序遍历：先访问左子结点,再访问根结点,最后访问右子结点。
  • 后序遍历：先访问左子结点,再访问右子结点,最后访问根结点。

js代码实现

根据流程描述，使用递归实现是最简单的方式。代码非常的简单，也很容易理解。

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
const tree = {
  val: 1,
  left: {
    val: 2,
    left: { val: 4 },
    right: { val: 5}
  },
  right: {
    val: 3,
    left: { val: 6 },
    right: { val: 7}
  }
}

// 前序遍历：中 左 右
// 1 2 4 5 3 6 7
function preOrder(root) {
    if (!root) return;
    console.log(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

// 中序遍历：左 中 右
// 4, 2, 5, 1, 6, 3, 7
function inOrder(root) {
    if (!root) return;
    inOrder(root.left);
    console.log(root.val);
    inOrder(root.right);
}

// 后序遍历：左 右 中
// 4, 5, 2, 6, 7, 3, 1
function postOrder(root) {
    if (!root) return;
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.val);
}

递归本身其实是语法内部帮我们调用了语言本身的栈实现（函数的调用栈）。如果我们想要非递归实现，则需要手动调用栈。

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
// 前序遍历：中 左 右
function preOrderStack(root) {
  if (!root) return;

  let stack = [root];
  while (stack.length) {
    let node = stack.pop();
    console.log(node.val);
    // 栈是后进先出的，所以先入栈右子节点
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

// 中序遍历：左 中 右
// 1、当前指针指向根节点
// 2、如果指针不为空，当前指针指向的节点入栈。指针指向左子节点。
// 3、如果指针为空，出栈一个节点。指针指向右子节点。
function inOrderStack(root) {
    if (!root) return;

    let stack = []; // 控制节点的访问顺序
    let cur = root; // 当前指针指向根节点
    while (stack.length || cur) {
        while(cur) {
            stack.push(cur); // 当前指针指向的节点入栈
            cur = cur.left; // 访问左子节点
        }

        cur = stack.pop(); 
        console.log(cur.val);
        cur = cur.right; // 访问右子节点
    }
}

// 后序遍历：左 右 中
// 非递归实现非常的繁琐，网上的方法都不太容易理解。这里给出的思路是，先访问父节点，再访问右子节点，最后访问左子节点。
// 把元素放入新栈中，最后出栈，正好访问顺序反转。
function postOrderStack(root) {
    if (!root) return;

    let stack = [root];
    let res = [];
    while (stack.length) {
        // 这里访问的顺序是 中 右 左，加入到新的栈中
        // 然后访问新的栈中的节点，顺序变成 左 右 中
        let node = stack.pop();
        res.push(node);
        
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    while(res.length){
        console.log(res.pop().val);
    }
}

go代码实现

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func NewTreeNode(val int) *TreeNode {
	return &TreeNode{Val: val}
}

func (t *TreeNode) AddLeftChild(child *TreeNode) {
	t.Left = child
}

func (t *TreeNode) AddRightChild(child *TreeNode) {
	t.Right = child
}

// 前序遍历
func preOrder(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Println(root.Val)
	preOrder(root.Left)
	preOrder(root.Right)
}
func preOrderStack(root *TreeNode) {
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		fmt.Println(node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
}
// 中序遍历
func inOrder(root *TreeNode) {
	if root == nil {
		return
	}
	inOrder(root.Left)
	fmt.Println(root.Val)
	inOrder(root.Right)
}
func inOrderStack(root *TreeNode) {
	stack := make([]*TreeNode, 0)
	cur := root
	for len(stack) > 0 || cur != nil {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		fmt.Println(cur.Val)
		cur = cur.Right
	}
}
// 后序遍历
func postOrder(root *TreeNode) {
	if root == nil {
		return
	}
	postOrder(root.Left)
	postOrder(root.Right)
	fmt.Println(root.Val)
}
func postOrderStack(root *TreeNode) {
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	res := make([]*TreeNode, 0)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node)
		if node.Right != nil {
			stack = append(stack, node.Left)
		}
		if node.Left != nil {
			stack = append(stack, node.Right)
		}
	}
	for len(res) > 0 {
		fmt.Println(res[len(res)-1].Val)
		res = res[:len(res)-1]
	}
}

非递归实现二叉树的遍历十分地繁琐，建议使用递归，简单且不易出错。非递归实现后序遍历还有其他方法，笔者认为太过繁琐不易理解，就没有深入研究了，感兴趣的话可以自己搜索一下资料。