树的遍历

节点结构
struct node {
    int val;
    struct node *left;
    struct node *right;
};  
前序遍历
void pre_order_traveral(struct node *head) {
    std::stack<struct node *> data_stack;
    data_stack.emplace(head);

    while(!data_stack.empty()) {
        struct node *n = data_stack.top();
        data_stack.pop();

        std::cout << n->val << " ";
        if (n->right != nullptr) {
            data_stack.emplace(n->right);
        }
        if (n->left != nullptr) {
            data_stack.emplace(n->left);
        }
    }
}
中序遍历
void mid_order_traveral(struct node *head) {
    std::stack<struct node*> data_stack;

    data_stack.emplace(head);

    while(!data_stack.empty()) {
        struct node *n = data_stack.top();
        struct node *left = n->left;
        struct node *right = n->right;

        data_stack.pop();

        if (left == nullptr && right == nullptr) {
            std::cout << n->val << " ";
            continue;
        }
        
        if (right != nullptr) {
            data_stack.emplace(right);
        }

        n->left = nullptr;
        n->right = nullptr;
        data_stack.emplace(n);

        if (left != nullptr) {
            data_stack.emplace(left);
        }
    }
}
后序遍历
void post_order_traveral(struct node *head) {
    std::stack<struct node*> data_stack;

    data_stack.emplace(head);

    while(!data_stack.empty()) {

        struct node *n = data_stack.top();
        data_stack.pop();

        struct node *left  = n->left;
        struct node *right = n->right;
        
        if (left == nullptr && right == nullptr) {
            std::cout << n->val << " ";
            continue;
        }

        n->left  = nullptr;
        n->right = nullptr;
        data_stack.emplace(n);

        if (right != nullptr) {
            data_stack.emplace(right);
        }
        if (left != nullptr) {
            data_stack.emplace(left);
        }

    }
}
层序遍历
void level_order_traveral(struct node *head) {
    std::queue<struct node*> data_queue;
    
    data_queue.emplace(head);
    while (!data_queue.empty()) {
        int visit_size = data_queue.size();

        for (int i = 0; i < visit_size; ++i) {
            struct node * n = data_queue.front();
            data_queue.pop();

            std::cout << n->val << " ";

            if (n->left != nullptr) {
                data_queue.emplace(n->left);
            }

            if (n->right != nullptr) {
                data_queue.emplace(n->right);
            }
        }
    }
}

评论

暂无评论