二叉树的先序遍历

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 8 日 17:29:53数据结构和算法评论205字数 520阅读 1 分 44 秒阅读模式

一、先序遍历

先序遍历的意思是：先遍历当前节点，再分别遍历左、右子节点。

例如一棵二叉树为：

二叉树的先序遍历-图片1

它的先序遍历序列（红色虚线标出来的）为：[1, 2, 4, 3, 5 6] 。

二、递归实现

递归的实现很简单，先访问当前节点，然后分别递归访问左右子节点。

/*
 * 先序遍历的递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void pre_order_traversal(tree_node<T> *node, vector<T> &v) {
    if (node == nullptr)
        return;

    // 遍历当前节点
    v.push_back(node->data);

    // 遍历左子树
    if (node->lchild)
        pre_order_traversal(node->lchild);

    // 遍历右子树
    if (node->rchild)
        pre_order_traversal(node->rchild);
}

* 先序遍历的递归实现

* @node 需要遍历的节点

* @v 保存遍历结果的数组

void pre_order_traversal(tree_node<T> *node, vector<T> &v) {

if (node == nullptr)

return;

// 遍历当前节点

v.push_back(node->data);

// 遍历左子树

if (node->lchild)

pre_order_traversal(node->lchild);

// 遍历右子树

if (node->rchild)

pre_order_traversal(node->rchild);

}

三、非递归实现

非递归的方式依赖栈来实现，逻辑：

访问根节点，把当前节点压栈。然后设置当前节点为左子节点，重复过程，直到左子节点为空。
设置当前节点为栈顶节点的右子节点，重复 1 过程。

3.1 图文描述

以上面的二叉树为例，首先访问根元素 1，压栈：

二叉树的先序遍历-图片2

然后继续访问 1 节点的左节点 2，压栈：

二叉树的先序遍历-图片3

节点 2 没有左子节点，退出左树遍历。然后取出栈顶元素 2，访问它的右子节点 4：

二叉树的先序遍历-图片4

右子节点没有子节点，因此继续从栈顶取元素 1，访问它的右子节点 3 并压栈：

二叉树的先序遍历-图片5

节点 3 有左子节点，顺着遍历左子节点 5，节点 5 入栈：

二叉树的先序遍历-图片6

此时 5 没有没有左子节点了，于是取出栈顶元素 5，访问它的右子节点。但是它没有右子节点，继续取出栈顶元素 3，访问它的右子节点 6：

二叉树的先序遍历-图片7

访问完 6 后，因为没有子节点了。所以继续从栈里取元素，但是此时栈也为空了，遍历结束。

3.2 代码描述

/*
 * 先序遍历的非递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void pre_order_traversal(tree_node<T> *root, vector<T> &v) {
    stack<tree_node<T> *> st;
    tree_node<T> *p;

    p = root;
    while (p != nullptr || !st.empty()) {
        // 遍历左子树
        while (p) {
            // 访问当前节点
            v.push_back(p->data);
            // 当前节点入栈
            st.push(p);
            // 遍历左子节点
            p = p->lchild;
        }

        // 取栈顶元素，访问父亲节点的右子节点
        if (!st.empty()) {
            p = st.top()->rchild;
            st.pop();
        }
    }
}