二叉树的各类遍历方法

2018-05-15  本文已影响17人  顽强的猫尾草

二叉树的遍历主要有四种:前序、中序、后序、层序。

遍历的实现方式主要是:递归和非递归。
递归遍历的实现非常容易,非递归的实现需要用到栈,难度要高一点。

节点的定义

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

前序遍历

先访问根节点,再访问左子树,最后访问右子树。

递归版本

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    preOrder(root, ret);
    return ret;
}
void preorder(TreeNode* p, vector<int> &ret) {
    if(p==NULL) return;
    ret.push_back(p->val);      // 存储根节点
    preorder(p->left, ret);     // 访问左子树
    preorder(p->right, ret);    // 访问右子树
}

非递归版本

需要利用辅助栈来实现:

  1. 首先把根节点压入栈中;
  2. 此时栈顶元素即为当前根节点,弹出并访问即可;
  3. 把当前根节点的右子树和左子树分别入栈,考虑到栈是先进后出,所以必须右子树先入栈,左子树后入栈;
  4. 重复 2~3 步骤,直到栈为空。
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root==NULL) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty()) {
        TreeNode* tp = st.top();    //取出栈顶元素
        st.pop();
        ret.push_back(tp->val);     //先访问根节点
        if(tp->right!=NULL) st.push(tp->right);    //由于栈时先进后出,考虑到访问顺序,先将右子树压栈
        if(tp->left!=NULL) st.push(tp->left);      //将左子树压栈
    }
    return ret;
}

中序遍历

先访问左子树,再访问根节点,最后访问右子树。

递归版本

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root, ret);
    return ret;
}
void inorder(TreeNode* p, vector<int>& ret) {
    if(p==NULL) return;
    inorder(p->left, ret);     // 访问左子树
    ret.push_back(p->val);     // 访问根节点
    inorder(p->right, ret);    // 访问右子树
}

非递归版本

中序遍历的非递归版本比前序稍微复杂一点,除了用到辅助栈之外,还需要一个指针 p 指向下一个待访问的节点:

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    while(!st.empty() || p!=NULL){
        if(p) {    // p 非空,代表还有左子树,继续
            st.push(p);
            p=p->left;
        }
        else {    // 如果为空,代表左子树已经走到尽头了
            p = st.top();
            st.pop();
            ret.push_back(p->val);     // 访问栈顶元素
            if(p->right) {
                st.push(p->right);     // 如果存在右子树,将右子树入栈
                p = p->right->left;    // p 始终为下一个待访问的节点
            }
            else p=NULL;
        }
    }
    return ret;
}

后序遍历

先访问左子树,再访问右子树,最后访问根节点。

递归版本

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    postorder(root, ret);
    return ret;
}
void postorder(TreeNode* p, vector<int>& ret) {
    if(p==NULL) return;
    postorder(p->left, ret);
    postorder(p->right, ret);
    ret.push_back(p->val);
}

非递归版本

采用一个辅助栈和两个指针 p 和 r,p 代表下一个需要访问的节点,r 代表上一次需要访问的节点:

  1. 如果 p 非空,则将 p 入栈,p 指向 p 的左子树;
  2. 如果 p 为空,代表左子树到了尽头,此时判断栈顶元素:
    2.1 如果栈顶元素存在右子树且没有被访问过(等于 r 代表被访问过),则右子树入栈,p 指向右子树的左子树;
    2.2 如果栈顶元素不存在或者已经被访问过,则弹出栈顶元素,访问,然后 p 置为 NULL,r 记录上一次访问的节点 p。
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    TreeNode* p = root;
    stack<TreeNode*> st;
    TreeNode* r = NULL;
    while(p || !st.empty()) {
        if(p) {
            st.push(p);
            p = p->left;
        }
        else {
            p = st.top();
            if(p->right && p->right!=r) {
                p = p->right;
                st.push(p);
                p = p->left;
            }
            else {
                p = st.top();
                st.pop();
                ret.push_back(p->val);
                r = p;
                p = NULL;
            }
        }
    }
    return ret;
}

层序遍历

每一层从左到右访问每一个节点。
层序遍历需要借助队列 queue 来完成,因为要满足先进先去的访问顺序。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if(root==NULL) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        vector<int> temp;
        queue<TreeNode*> tmpQue;    // 存储下一层需要访问的节点
        while(!q.empty()) {    // 从左到右依次访问本层
            TreeNode* tempNode = q.front();
            q.pop();
            temp.push_back(tempNode->val);
            if(tempNode->left!=NULL) tmpQue.push(tempNode->left);      // 左子树压入队列
            if(tempNode->right!=NULL) tmpQue.push(tempNode->right);    // 右子树压入队列
        }
        ret.push_back(temp);
        q = tmpQue;    // 访问下一层
    }
    return ret;
}
上一篇 下一篇

猜你喜欢

热点阅读