【数据结构】二叉树先序遍历（递归与非递归）

wander

二叉树先序遍历的实现思想是：

• 访问根节点；
• 访问当前节点的左子树；
• 若当前节点无左子树，则访问当前节点的右子树；
  

图 1 二叉树

以图  1 为例，采用先序遍历的思想遍历该二叉树的过程为：

• 访问该二叉树的根节点，找到 1；
• 访问节点 1 的左子树，找到节点 2；
• 访问节点 2 的左子树，找到节点 4；
• 由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
• 由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
• 访问节点 3 左子树，找到节点 6；
• 由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
• 节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
  

因此，图 1 中二叉树采用先序遍历得到的序列为：

1 2 4 5 3 6 7