c語(yǔ)言如何遍歷二叉樹

小億
83
2024-09-03 06:04:17

在C語(yǔ)言中，遍歷二叉樹有多種方法，包括前序遍歷、中序遍歷和后序遍歷。這里給出一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明如何實(shí)現(xiàn)這三種遍歷方法。

首先，我們需要定義一個(gè)二叉樹節(jié)點(diǎn)的結(jié)構(gòu)體：

#include<stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

接下來(lái)，我們實(shí)現(xiàn)三種遍歷方法的函數(shù)：

// 前序遍歷：根節(jié)點(diǎn) -> 左子樹 -> 右子樹
void preOrderTraversal(TreeNode *node) {
    if (node == NULL) {
        return;
    }

    printf("%d ", node->data);
    preOrderTraversal(node->left);
    preOrderTraversal(node->right);
}

// 中序遍歷：左子樹 -> 根節(jié)點(diǎn) -> 右子樹
void inOrderTraversal(TreeNode *node) {
    if (node == NULL) {
        return;
    }

    inOrderTraversal(node->left);
    printf("%d ", node->data);
    inOrderTraversal(node->right);
}

// 后序遍歷：左子樹 -> 右子樹 -> 根節(jié)點(diǎn)
void postOrderTraversal(TreeNode *node) {
    if (node == NULL) {
        return;
    }

    postOrderTraversal(node->left);
    postOrderTraversal(node->right);
    printf("%d ", node->data);
}

最后，我們可以創(chuàng)建一個(gè)二叉樹并遍歷它：

int main() {
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = 1;
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->data = 2;
    root->right->data = 3;
    root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->left->data = 4;
    root->left->right->data = 5;
    root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->left->data = 6;
    root->right->right->data = 7;

    printf("前序遍歷：");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍歷：");
    inOrderTraversal(root);
    printf("\n");

    printf("后序遍歷：");
    postOrderTraversal(root);
    printf("\n");

    return 0;
}

運(yùn)行這個(gè)程序，你將看到以下輸出：

前序遍歷：1 2 4 5 3 6 7
中序遍歷：4 2 5 1 6 3 7
后序遍歷：4 5 2 6 7 3 1

這就是如何在C語(yǔ)言中遍歷二叉樹的方法。注意，這個(gè)例子中的二叉樹結(jié)構(gòu)比較簡(jiǎn)單，實(shí)際應(yīng)用中的二叉樹可能會(huì)更復(fù)雜。

0 踩