二叉树的广度遍历和深度遍历

2024-01-28 21:32:04

二叉树的遍历

假定二叉树的节点的定义如下：

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
}

调用一次visit()视作对节点的数据进行一次访问。

1 二叉树的广度优先遍历（层次遍历）

广度优先遍历可以用队列来实现

void levelTraversal(TreeNode* root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* temp = q.pop();
        visit(temp ->val);
        if(temp ->left)
            q.push(x->left);
        if(temp ->right)
            q.push(x->right);
    }
}

2 二叉树的深度优先遍历

2.1 递归算法

//前序遍历
void preTrav(TreeNode* root)
{
    if(!root)
        return;
    visit(x->val);
    preTrav(root->left);
    preTrav(root->right);
}
//中序遍历
void inTrav(TreeNode* root)
{
    if(!root)
        return;
    inTrav(root->left);
    visit(x->val);
    inTrav(root->right);
}
//后序遍历
void postTrav(TreeNode* root)
{
    if(!root)
        return;
    postTrav(root->left);
    postTrav(root->right);
    visit(x->val);
}

2.2 非递归算法

2.2.1 一种简明易记的非递归算法

遍历过程可以认为每个节点都将被访问两次。当访问到一个节点时，如果是第一次访问，将这个节点、这个节点的非空左右节点加入栈（入栈的顺序根据访问顺序调整），如果是第二次访问，说明是回溯到了这个节点，此时调用visit()函数访问这个节点的数据。

（参考来源：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/）

//前序遍历
void preTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){
            res.push_back(temp.second->val);
        }
        else{
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
            stk.push(pair<bool, TreeNode*>(true, temp.second));
        }
    }
}
//中序遍历
void inTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){
            visit(temp.second->val);
        }
        else{
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            stk.push(pair<bool, TreeNode*>(true, temp.second));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
        }
    }
    return;
}
//后序遍历
void postTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){
            visit(temp.second->val);
        }
        else{
            stk.push(pair<bool, TreeNode*>(true, temp.second));
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
        }
    }
}

2.2.2 常规非递归算法

前序遍历

void preTrav(TreeNode* root)
{
    stack<TreeNode*> stk; 
    if(root) 
        stk.push(root);
    while(!stk.empty()){
        TreeNode* temp = stk.top();
        stk.pop();
        visit(temp->val);
        if(temp->right)
            stk.push(temp->right);
        if(temp->left)
            stk.push(temp->left);
    }
    return;
}

中序遍历

void inTrav(TreeNode* root)
{
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while (!stk.empty() || node) {
        while (node) {//沿着左子树遍历
            stk.emplace(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        visit(node->val);
        node = node->right;
    }
}

后序遍历

void postTrav(TreeNode* root)
{
    stack<TreeNode*> stk;
    TreeNode *prev = NULL;
    while(root || !stk.empty()) {
        while(root) { //沿着左子树遍历
            stk.emplace(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if(!root->right|| root->right == prev) {//右子树是叶子结点或者上一个刚遍历的节点
            visit(root->val);
            prev = root;
            root = NULL;
        } 
        else{//继续沿着右子树遍历
            stk.emplace(root);
            root = root->right;
        }
    }
}

码农公寓