顺序
先序
先序遍历是二叉树遍历的一种方式,遵循"根-左-右"的顺序。具体来说,先访问根节点,然后递归地遍历左子树,最后递归地遍历右子树。这种遍历方式常用于创建树的拷贝或进行前缀表达式求值。
- 若二叉树为空,则返回;否则:
- 访问根节点(D)
- 先序遍历左子树(L)
- 先序遍历右子树(R)
如图输出结果:ABDEGCF
(第一个输出节点必为根节点)
中序
中序遍历是二叉树遍历的另一种方式,遵循"左-根-右"的顺序。具体来说,先递归地遍历左子树,然后访问根节点,最后递归地遍历右子树。这种遍历方式在二叉搜索树中特别有用,因为它可以按照节点值的升序顺序输出所有节点。
- 若二叉树为空,则返回;否则:
- 中序遍历左子树(L)
- 访问根节点(D)
- 中序遍历右子树(R)
如图输出结果:DBGEAFC
(先于根节点A输出的节点为左子树的节点
后于根节点A输出的节点为右子树的节点)
后序
后序遍历是二叉树遍历的第三种主要方式,遵循"左-右-根"的顺序。具体来说,先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。这种遍历方式常用于释放树中的节点或进行后缀表达式求值。后序遍历的一个重要特点是,在访问某个节点之前,其所有子节点都已经被访问过。
- 若二叉树为空,则返回;否则:
- 后序遍历左子树(L)
- 后序遍历右子树(R)
- 访问根节点(D)
如图输出结果:DGEBFCA
(最后输出的节点必为根节点)
遍历
递归
先序
中序
后序
非递归
层序
先序
设T是根结点的指针变量,若二叉树为空,则返回;否则,令p=T,执行以下循环:
⑴ 访问p所指向的结点;
⑵ q=p->Rchild ,若q不为空,则q进栈;
⑶ p=p->Lchild ,若p不为空,转(1),否则转(4);
⑷ 退栈到p ,转(1),直到栈空为止。
中序
设T是指向根结点的指针变量,若二叉树为空,则返回;否则,令p=T,执行以下循环:
⑴ 若p不为空,p进栈, p=p->Lchild ,转(1) ;
⑵ 否则(即p为空),退栈到p,访问p所指向的结点;
⑶ p=p->Rchild ,转(1);
直到栈空为止。
后序
后序遍历是三种主要遍历方式中最复杂的一种,因为它需要在访问节点之前先访问其所有子节点。非递归实现通常需要使用两个栈或者一个栈加一个标记来记录节点的访问状态。以下是一种常用的非递归实现方法: