如何遍历一棵二叉树?

如何遍历一棵二叉树?

二叉树的遍历分为前序遍历、中序遍历、后序遍历和层次遍历。本文将详细梳理这四种二叉树的遍历方法。

我们给定一棵二叉树,结构如下:

二叉树

先给出二叉树的数据结构:

class TreeNode
{
	public TreeNode(string value)
	{
		Value = value;
	}
	public string Value;
	public TreeNode Left;
	public TreeNode Right;
}

然后构建出如上图所示的二叉树:

var node = new TreeNode("A");
node.Left = new TreeNode("B");
node.Right = new TreeNode("F");

node.Left.Left = new TreeNode("C");
node.Left.Right = new TreeNode("D");
node.Left.Right.Left = new TreeNode("E");

node.Right.Left = new TreeNode("G");
node.Right.Right = new TreeNode("I");
node.Right.Left.Left = new TreeNode("H");

先序遍历、中序遍历、后序遍历代码如下:

public void Traverse(TreeNode treeNode)
{
	if (treeNode == null) return;
	//Console.Write(treeNode.Value + " ");先序遍历
	Traverse(treeNode.Left);
	//Console.Write(treeNode.Value + " ");//中序遍历
	Traverse(treeNode.Right);
	//Console.Write(treeNode.Value + " "); 后续遍历
}

可以看到,前中后序遍历的区别在于在哪个地方使用node。我在学习二叉树的遍历时这地方着实让我困惑了一会儿,其实主要还是对递归思维的理解不够透彻。

我们结合文初给出的二叉树,当第一次调用Traverse(A)时,treeNode !=null,调用Traverse(B),在调用Traverse(B)之前,需要把Traverse(A)压栈,以便Traverse(B)返回时继续执行Traverse(A)。以此类推,在执行Traverse(C)的时候把Traverse(B)压栈,在执行Traverse(C.Left)时把Traverse(C)压栈。此时栈内地结构如下:

栈底 操作
traverse(A) 执行traverse(B),压栈
traverse(B) 执行traverse(C)
traverse(C) 执行traverse(C.Ledt)

因为C.Left==null,Traverse(C.Left);返回,弹出traverse(C),执行Traverse(C.Right),C.Right == null,又返回,此时把traverse(B)弹出来,执行traverse(B.Right),也就是traverse(D),此时又要把traverse(B)压进去,依次递归,压栈和弹栈顺序如下:

栈底 操作 先序 中序 后续
执行traverse(A) A
traverse(A) 执行traverse(A.Left = B),压栈A,栈内A B
traverse(B) 执行traverse(B.Left = C),压栈B,栈内A-B C
traverse(C) 执行traverse(C.Ledt = null),压栈C,栈内A-B-C
traverse(C) traverse(C.Left = null)返回,弹栈C,栈内A-B C
traverse(C) 执行traverse(C.Right = null),压栈C,栈内A-B-C
traverse(C) traverse(C.Right = null )返回,弹栈C,栈内A-B C
traverse(B) traverse(B.Left= C)返回,弹栈B,栈内A B
traverse(B) 执行traverse(B.Right = D),压栈B,栈内A-B D
traverse(D) 执行traverse(D.Left = E),压栈D,栈内A-B-D E
traverse(E) 执行traverse(E.Left = null),压栈E,栈内A-B-D-E
traverse(E) traverse(E.Left = null)返回,弹栈E,栈内A-B-D E
traverse(E) 执行traverse(E.Right = null),压栈E,栈内A-B-D-E
traverse(E) traverse(E.Right = null)返回,弹栈E,栈内A-B-D E
traverse(D) traverse(D.Left = E)返回,弹栈D,栈内A-B D
traverse(D) 执行traverse(D.Right = null),压栈D,栈内A-B-D
traverse(D) traverse((D.Right = null)返回,弹栈D,栈内A-B D
traverse(B) traverse(B.Right = D)返回,弹栈B,栈内A B
traverse(A) traverse(A.Left = B)返回,弹栈A,栈内空 #此时根节点的左子树遍历完毕 A
traverse(A) 执行traverse(A.Right = F),压栈A,栈内A F
traverse(F) 执行traverse(F.Left = G),压栈F,栈内A-F G
traverse(G) 执行traverse(G.Left = null),压栈G,栈内A-F-G
traverse(G) raverse(G.Left = null)返回,弹栈G,栈内A-F G
traverse(G) 执行traverse(G.Right = H),压栈G,栈内A-F-G H
traverse(H) 执行traverse(H.Left = null),压栈H,栈内A-F-G-H
traverse(H) traverse(H.Left = null)返回,弹栈H,栈内A-F-G H
traverse(H) 执行traverse(H.Right = null),压栈H,栈内A-F-G-H
traverse(H) traverse(H.Right = null)返回,弹栈H,栈内A-F-G H
traverse(G) traverse(G.Right = H)返回,弹栈G,栈内A-F G
traverse(F) traverse(F.Left = G)返回,弹栈F,栈内A F
traverse(F) 执行traverse(F.Right = I),压栈F,栈内A-F I
traverse(I) 执行traverse(I.Left = null),压栈I,栈内A-F-I
traverse(I) traverse(I.Left = null) 返回,弹栈I,栈内A-F I
traverse(I) 执行traverse(I.Right = null),压栈I,栈内A-F-I
traverse(I) traverse(I.Right = null)返回,弹栈I,栈内A-F I
traverse(F) traverse(F.Right = I)返回,弹栈F,栈内A F
traverse(A) traverse(A.Right = F)返回,弹栈A,栈内无,此时根节点的右子树遍历完吧 A

从上表中可以看出,在一个二叉树中一个节点的遍历需要以下几个步骤:

  1. 把当前执行环境压入栈中,遍历左子树。
  2. 等待左子树遍历完成,弹出当前执行环境,继续执行。对应上表的(X.Left = Y返回)
  3. 把当前环境压入栈中,遍历右子树。
  4. 等待右子树遍历完成,弹出当前执行环境,继续执行。对应上表的(XRight = Y返回)

先序遍历在步骤1之前执行,也就是只要碰到这个节点,不遍历子节点,立即执行。

中序遍历在步骤2和步骤3之间执行,也就是遍历完当前节点的左子节点后执行。

后序遍历是在步骤4之后执行,也就是当前节点的左右子节点全部遍历完成后执行。

看完了二叉树的前中后序遍历,那么如何对二叉树进行分层遍历呢?

其实也很简单,主要利用队列的先进先出思想:

public void TraverseByLayer(TreeNode treeNode)
{
	var queue = new Queue<TreeNode>();
	queue.Enqueue(treeNode);
	while(queue.Count > 0)
	{
		var q = queue.Dequeue();
		Console.WriteLine(q.Value+" ");
		if(q.Left!=null)
			queue.Enqueue(q.Left);
		if(q.Right!=null)
			queue.Enqueue(q.Right);
	}
}

二叉树的遍历主要用到栈的先进后出和队列的先进先出特点,在大厂的算法面试题中较为常见。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!