二叉树经典遍历

该篇总结了基础的二叉树遍历方式

深度优先遍历

包括前序、中序、后序三种

递归形式的遍历

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

但是递归占用太多计算机资源，还经常超时，所以下面的手写非递归形式遍历，要借助其他数据结构

 

前序遍历(Preorder)

• 访问根节点。
• 递归地对左子树进行前序遍历。
• 递归地对右子树进行前序遍历。 前序遍历的访问顺序为「根-左-右」。

// 前序遍历
void Preorder(TreeNode* root){
    stack<TreeNode*> a;
    TreeNode* node=root;
    while(node!=NULL||!a.empty()){
        while(node!=NULL){
            //结点操作
            a.push(node);
            node=node->left;
        }
    
    //遍历代码精髓就是当一直向左遍历到空的时候再依靠栈返回到父节点，由此对父节点以及右节点进行遍历
    if(!a.empty()){
        node=a.tap();
        a.pop();
        node=node-&gt;right;
    }
}

}

中序遍历(Inorder)

• 递归地对左子树进行中序遍历。
• 访问根节点。
• 递归地对右子树进行中序遍历。 中序遍历的访问顺序为「左-根-右」。

// 前序遍历
void Preorder(TreeNode* root){
    stack<TreeNode*> a;
    TreeNode* node=root;
    while(node!=NULL||!a.empty()){
        while(node!=NULL){
            a.push(node);
            node=node->left;
        }
        
    //和前序遍历一样的，只不过结点操作点放在出栈之后了
    if(!a.empty()){
        node=a.top();
        a.pop();
    //结点操作
    node=node-&gt;right;
    }
}

}

后序遍历(Postorder)

• 递归地对左子树进行后序遍历。
• 递归地对右子树进行后序遍历。
• 访问根节点。 后序遍历的访问顺序为「左-右-根」

//后序遍历
void Postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

stack<TreeNode*> s;
TreeNode* prev = nullptr;
do {
    while (root != nullptr) {
        s.push(root);
        root = root->left;
    }
    while (root == nullptr && !s.empty()) {
        root = s.top();
        //其他结构不变，仍然是保证“先遍历左节点再遍历右结点”，那么难点就在于如何遍历中间结点了，只需要在遍历“出栈”结点时将其标记，这样这个结点回到父节点时可以直接对中间结点进行操作
        if (root->right == nullptr || root->right == prev) {
            cout << root->val << " ";
            s.pop();
            prev = root;
            root = nullptr;
        } else {
            root = root->right;
        }
    }
} while (!s.empty());

}

 

 

广度优先遍历(Level)

最基础的就是经典层序遍历，在实际运用中可能会更改遍历顺序等

• 从根节点开始，逐层遍历二叉树。
• 从左到右依次访问每个节点。 层序遍历按照层级顺序逐个访问节点。

//bfs
void bfs(TreeNode* root){
    if(root==NULL){
        return;
    }
    Queue<TreeNode*> q;
    TreeNode* node=root;
    q.push(node);
    while(node!=NULL&&!q.empty()){
        node=q.front();
        q.pop();
        //遍历操作
        if(node->left!=NULL)
            q.push(node->left);
        if(node->right!=NULL)
            q.push(node->right);
    }
}