如何遍历一棵二叉树?
如何遍历一棵二叉树?
二叉树的遍历分为前序遍历、中序遍历、后序遍历和层次遍历。本文将详细梳理这四种二叉树的遍历方法。
我们给定一棵二叉树,结构如下:
先给出二叉树的数据结构:
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.Left = null)返回,弹栈C,栈内A-B | C | |||
traverse(C) | 执行traverse(C.Right = null),压栈C,栈内A-B-C | |||
traverse(C.Right = null )返回,弹栈C,栈内A-B | C | |||
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.Left = null)返回,弹栈E,栈内A-B-D | E | |||
traverse(E) | 执行traverse(E.Right = null),压栈E,栈内A-B-D-E | |||
traverse(E.Right = null)返回,弹栈E,栈内A-B-D | E | |||
traverse(D.Left = E)返回,弹栈D,栈内A-B | D | |||
traverse(D) | 执行traverse(D.Right = null),压栈D,栈内A-B-D | |||
traverse((D.Right = null)返回,弹栈D,栈内A-B | D | |||
traverse(B.Right = D)返回,弹栈B,栈内A | B | |||
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 | |||
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.Left = null)返回,弹栈H,栈内A-F-G | H | |||
traverse(H) | 执行traverse(H.Right = null),压栈H,栈内A-F-G-H | |||
traverse(H.Right = null)返回,弹栈H,栈内A-F-G | H | |||
traverse(G.Right = H)返回,弹栈G,栈内A-F | G | |||
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.Left = null) 返回,弹栈I,栈内A-F | I | |||
traverse(I) | 执行traverse(I.Right = null),压栈I,栈内A-F-I | |||
traverse(I.Right = null)返回,弹栈I,栈内A-F | I | |||
traverse(F.Right = I)返回,弹栈F,栈内A | F | |||
traverse(A.Right = F)返回,弹栈A,栈内无,此时根节点的右子树遍历完吧 | A |
从上表中可以看出,在一个二叉树中一个节点的遍历需要以下几个步骤:
- 把当前执行环境压入栈中,遍历左子树。
- 等待左子树遍历完成,弹出当前执行环境,继续执行。对应上表的(X.Left = Y返回)
- 把当前环境压入栈中,遍历右子树。
- 等待右子树遍历完成,弹出当前执行环境,继续执行。对应上表的(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 协议 ,转载请注明出处!