欢迎观临
路漫漫其修远兮,吾将上下而求索

二叉树遍历(前序、中序、后序、层次、深度优先、广度优先遍历)

1. 基本概念

树的遍历在实际使用中有非常重要的作用。对于二叉树来说,遍历可以分为深度优先广度优先;其中深度优先可分为前序,中序,后序遍历;广度优先即层次遍历

由于树的定义本身就是递归定义,因此采用递归的方法去实现树的前序,中序,后序三种遍历不仅容易理解而且代码简洁;而对于广度遍历来说,则须要其他数据结构如队列的辅助。

2 四种遍历详解

四种基本的遍历思想为:
– 前序遍历:根结点 —> 左子树 —> 右子树
– 中序遍历:左子树—> 根结点 —> 右子树
– 后序遍历:左子树 —> 右子树 —> 根结点
– 层次遍历:按层次逐层遍历即可

//二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left, right;
};

2.1 前序遍历

依据上文提到的遍历思路:根结点 —> 左子树 —> 右子树,前序遍历的递归形式非常容易给出:

void preOrderTraverse1(TreeNode* root) {
    if (root != NULL) {
        cout << root->val << " ";
        preOrderTraverse1(root->left);
        preOrderTraverse1(root->right);
    }
}

如果考虑前序遍历的非递归形式,则考虑对任意节点,访问该节点后,先访问其左子树,之后再访问右子树;则在访问左子树时需要将该节点暂存;需要的用到的数据结构是栈。示例代码如下:

void preOrderTraverse2(TreeNode* root) {
    stack<TreeNode*> ts;
    TreeNode* cur = root;
    while(!!cur || !ts.empty()) {
        if(!!cur) {
            cout << cur->val << " ";
            ts.push(cur);
            cur = cur->left;
        } else {
            cur = ts.pop();
            cur = cur->right;
        }
    }
}

2.2 中序遍历

依据上文提到的遍历思路:左子树 —> 根结点 —> 右子树,中序遍历的递归形式也非常容易给出:

void inOrderTraverse1(TreeNode* root) {
    if (root != NULL) {
        inOrderTraverse1(root->left);
        cout << root->val << " ";
        inOrderTraverse1(root->right);
    }
}

非递归形式的中序遍历和前序类似,只是将访问节点放到了出栈后;即对于任意节点,先将其入栈暂存,再访问其左子树,然后出栈时先访问该节点,再访问右子树。示例代码如下:

void inOrderTraverse2(TreeNode* root) {
    stack<TreeNode*> ts;
    TreeNode* cur = root;
    while(!!cur || !ts.empty()) {
        if(!!cur) {
            ts.push(cur);
            cur = cur->left;
        } else {
            cur = ts.pop();
            cout << cur->val << " ";
            cur = cur->right;
        }
    }
}

2.3 后序遍历

依据上文提到的遍历思路:左子树 —> 右子树 —> 根结点,后序遍历的递归形式也很简单:

void postOrderTraverse1(TreeNode* root) {
    if (root != NULL) {
        inOrderTraverse1(root->left);
        inOrderTraverse1(root->right);
        cout << root->val << " ";
    }
}

后序遍历的非递归实现是三种遍历方式中最难的一种。对任意节点P,为保证访问顺序,需要对将节点P,右孩子,左孩子按顺序入栈;假设先将节点P入栈,对于任意栈顶节点P,假设P不存在子节点,则能够直接訪问它;若是P存在子节点,但是其子节点都已被訪问过了,则也能够直接訪问该结点;若非上述两种情况,则将P的右孩子和左孩子依次入栈。这样就保证了后序遍历的顺序访问节点。

void postOrderTraverse2(TreeNode *root) {
    stack<TreeNode*> ts;
    TreeNode* cur = root; //当前结点
    TreeNode* pre=NULL; //前一次訪问的结点
    ts.push(cur);
    while(!ts.empty()) {
        cur = ts.top();
        if((!cur->left && !cur->right) || (!!pre && (pre==cur->left || pre==cur->right))) {
            cout << cur->val << " ";
            ts.pop();
            pre=cur;
        } else {
            if(cur->right)
                ts.push(cur->right);
            if(cur->left)
                ts.push(cur->left);
        }
    }
}

2.4 层序遍历

借助队列数据结构,层次遍历的实现比較简单。先在队列中增加根结点,之后对于出队的任意节点,先访问它,同时若有子节点,则将子节点入队列。

void levelTraverse(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    TreeNode* cur = root; //当前结点
    q.push(cur);
    while (!q.empty()) {
        cur = q.pop();
        cout << cur->val << " ";
        if (cur->left) {
            q.push(cur->left);
        }
        if (cur->right) {
            q.push(cur->right);
        }
    }
}
赞(0) 打赏
未经允许不得转载:云海鹰影博客 » 二叉树遍历(前序、中序、后序、层次、深度优先、广度优先遍历)
分享到: 更多 (0)

欢迎留言 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏