目录

算法二叉树的递归遍历

JAY.LIN 收录于未分类

2025-03-10 约 241 字预计阅读 1 分钟

https://bing.ee123.net/img/rand?artid=146166969

目录

【算法】二叉树的递归遍历

前序遍历

void preOrder(Node *node)
    {
        if(node != nullptr)
        {
            cout << node->data_ << " ";
            preOrder(node->left_);
            preOrder(node->right_);
        }
    }

中序遍历

void inOrder(Node *node)
    {
        if (node != nullptr)
        {
            inOrder(node->left_);
            cout << node->data_ << " ";
            inOrder(node->right_);
        }
    }

后序遍历

void postOrder(Node *node)
    {
        if (node != nullptr)
        {
            postOrder(node->left_);
            postOrder(node->right_);
            cout << node->data_ << " ";
        }
    }

层序遍历

递归实现求二叉树的层数，求以node为根节点的子树的高度

int level(Node* node)
    {
        if(node == nullptr)
        {
            return 0;
        }
        int left = level(node->left_);
        int right = level(node->right_);
        return left > right ? left + 1 : right + 1;
    }

递归求二叉树节点的个数

int number(Node *node)
    {
        if(node == nullptr)
        {
            return 0;
        }
        int left = number(node->left_);
        int right = number(node->right_);
        return left + right + 1;
    }

// 递归层数遍历
    void levelOrder()
    {
        int h = level();
        for(int i = 0; i < h; i++)
        {
            levelOrder(root_, i);
        }
    }
    void levelOrder(Node *node, int i)
    {
        if(node == nullptr)
        {
            return;
        }
        if(i == 0)
        {
            cout << node->data_ << " ";
            return;
        }
        levelOrder(node->left_, i - 1);
        levelOrder(node->right_, i - 1);
    }