5.2 二叉树的遍历

[giscus[bot]]

5.2 二叉树的遍历

二叉树的遍历 1. 二叉树的遍历简介 二叉树的遍历：指的是从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。 在二叉树的一些实际问题中，经常需要按照一定顺序对二叉树中每个节点逐个进行访问一次，用以查找具有某一特点的节点或者全部节点，然后对这些满足要求的节点进行处理。这里所说的「访问」就是指对该节点进行某种操作...

https://algo.itcharge.cn/05_tree/05_02_binary_tree_traverse/

[sys-xander]

func (t *TreeNode[T]) levelOrder() {
	var nodes = []*TreeNode[T]{t}

	for len(nodes) != 0 {
		var tmp = []*TreeNode[T]{}

		for _, v := range nodes {
			if v != nil {
				tmp = append(tmp, v.left, v.right)
				fmt.Println(v.data)
			}
		}

		nodes = tmp
	}
}

[aripio]

二叉树后序遍历的显式栈实现的第18行代码是多余的：
root = None # 将当前根节点标记为空
因为前面的while loop保证了此时root总是为空。

[WuCC2001]

而且层序遍历的代码里面第24行代码：
if level:
也是多余的
因为while queue保证了当前层有节点

[MissingDirection]

那个中序遍历那里的结果好像错了，应该是['H', 'D', 'I', 'B', 'E', 'A', 'J', 'F', 'K', 'C', 'G']，不是H−D−I−B−E−A−F−J−C−K−G

[itcharge]

您好，我仔细检查了一遍，原文应该是没错的。这里 J 为 F 的右子节点，所以在中序遍历中，按照左根右的顺序，结果应该如下：

1. 先访问根节点 F；
2. 然后访问 F 的右子节点 J；
3. 此时 F 及其所有子节点都访问完了，再去访问 F 的根节点 C；
4. 然后访问 C 的右节点 G 的左子节点 K；
5. 最后访问 K 的根节点 G。
   即顺序为 … F - J - C - K - G。

[WuCC2001]

有一个小疑问，中序遍历里面的“因此，只有在左子树全部入栈后，当前节点才能出栈并被访问。”，是不是应该改成“因此，只有在左子树全部出栈后，当前节点才能出栈并被访问。”？