数据结构

二叉树遍历

作者: 苏丙榅
链接: https://subingwen.cn/data-structure/binary-tree/#4-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
来源: 爱编程的大丙

  1. 前序遍历：先访问根节点，然后前序遍历左子树，最后前序遍历右子树
  2. 中序遍历：中序遍历左子树，然后访问根节点，最后中序遍历右子树
  3. 后序遍历：后序遍历左子树，然后后序遍历右子树，最后访问根节点

通过三种遍历方式的定义可知，前、中、后其实是相对于根节点而言的，并且二叉树的左子树和右子树的遍历也是递归的，同样遵循前序、中序、后序的规则，在遍历过程中如果树为空，直接返回，递归结束。

一、先序遍历

1.1、递归遍历

1
2
3
4
5
6
7
8
void preorder(TreeNode* root)
{
    if (root == nullptr)
        return;
    std::cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

1.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void preorderTraversal(TreeNode* root)
{
    if (root == nullptr)
        return;
    // 利用栈先进后出的特性，现将右子树入站，再将左子树入站
    // 这样会先弹出左子树，达到先处理左子树再处理右子树的特点
    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty())
    {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();

        std::cout << node->val << " ";
        if(node->right)
        {
            nodeStack.push(node->right);
        }
        if(node->left)
        {
            nodeStack.push(node->left);
        }
    }
}

二、中序遍历

2.1、递归遍历

1
2
3
4
5
6
7
8
void inorder(TreeNode* tree)
{
    if (tree == nullptr)
        return;
    inorder(tree->left);
    std::cout << tree->val << " ";
    inorder(tree->right);
}

2.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void inorderTraversal(TreeNode* tree)
{
    if (tree == nullptr)
        return;
    std::stack<TreeNode*> nodeStack;
    TreeNode* current = tree;
    while (current != nullptr || !nodeStack.empty())
    {
        // 先将当前节点的所有左子树入栈
        while (current)
        {
            nodeStack.push(current);
            current = current->left;
        }
        current = nodeStack.top();
        nodeStack.pop();
        std::cout << current->val << " ";
        // 处理右子树
        current = current->right;
    }
}

二、后序遍历

3.1、递归遍历

1
2
3
4
5
6
7
8
void postorder(TreeNode* tree)
{
    if (tree == nullptr)
        return;
    postorder(tree->left);
    postorder(tree->right);
    std::cout << tree->val << " ";
}

3.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void postorderTraversal(TreeNode* tree)
{
    std::stack<TreeNode*> stack1,stack2;
    stack1.push(tree);
    while(!stack1.empty())
    {
        TreeNode* current = stack1.top();
        //根据栈先进后出的特点，将根节点先入栈，根节点会后输出
        stack1.pop();
        stack2.push(current);
        //现将左子树放入stack1，再放入右子树，这样压入stack2的顺序就是先压入右子树，再压入左子树
        // 最后会先输出左子树，再输出右子树，最后输出根节点
        if(current->left)
        {
            stack1.push(current->left);
        }
        if(current->right)
        {
            stack1.push(current->right);
        }
    } 
    while(!stack2.empty())
    {
        std::cout << stack2.top()->val << " ";
        stack2.pop();
    }
}

四、层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void levelOrder(TreeNode* tree)
{
    if (tree == nullptr)
        return;
    std::queue<TreeNode*> q;
    q.push(tree);
    while(!q.empty())
    {
        int size = q.size();
        for(int i = 0; i < size; ++i)
        {
            TreeNode* current = q.front();
            std::cout << current->val << " ";
            if(current->left)
            {
                q.push(current->left);
            }
            if(current->right)
            {
                q.push(current->right);
            }
            q.pop();
        }
        std::cout << "\n";
    }
}

五、释放树节点

使用先序遍历、中序遍历还是后序遍历的方式创建二叉树，在释放资源的时候一定使用的是后续遍历的方式，也就是从下往上。

1
2
3
4
5
6
7
8
9
10
11
12
13
void freeTree(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    // 先释放左子树
    freeTree(root->left);
    // 再释放右子树
    freeTree(root->right);
    // 最后释放根节点
    delete root;
}