溫馨提示×

c語言如何實現(xiàn)二叉樹的中序遍歷

小億
83
2024-10-11 17:28:21
欄目: 編程語言

在C語言中，可以通過遞歸或迭代的方式來實現(xiàn)二叉樹的中序遍歷。這里給出兩種方法的代碼示例：

方法一：遞歸

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

// 定義二叉樹節(jié)點結(jié)構(gòu)體
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 中序遍歷的遞歸函數(shù)
void inorderTraversal(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    inorderTraversal(node->left);  // 遍歷左子樹
    printf("%d ", node->val);       // 訪問根節(jié)點
    inorderTraversal(node->right); // 遍歷右子樹
}

// 創(chuàng)建新節(jié)點的輔助函數(shù)
struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // 創(chuàng)建示例二叉樹
    struct TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    // 執(zhí)行中序遍歷
    inorderTraversal(root);

    return 0;
}

方法二：迭代（使用棧）

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

// 定義二叉樹節(jié)點結(jié)構(gòu)體
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 中序遍歷的迭代函數(shù)
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    struct TreeNode* currentNode = root;

    while (currentNode != NULL || !isEmpty(stack)) {
        // 遍歷左子樹，將節(jié)點壓入棧中
        while (currentNode != NULL) {
            stackPush(stack, currentNode);
            currentNode = currentNode->left;
        }

        // 彈出棧頂元素，訪問節(jié)點，并轉(zhuǎn)向右子樹
        currentNode = stackPop(stack);
        printf("%d ", currentNode->val);
        currentNode = currentNode->right;
    }

    free(stack);
}

// 棧結(jié)構(gòu)體定義及操作函數(shù)
struct Stack {
    struct TreeNode** data;
    int top;
    int capacity;
};

void initStack(struct Stack* stack, int capacity) {
    stack->data = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    stack->top = -1;
    stack->capacity = capacity;
}

bool isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void stackPush(struct Stack* stack, struct TreeNode* node) {
    if (stackIsFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->data[++stack->top] = node;
}

struct TreeNode* stackPop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return NULL;
    }
    return stack->data[stack->top--];
}

bool stackIsFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int main() {
    // 創(chuàng)建示例二叉樹
    struct TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    // 執(zhí)行中序遍歷
    inorderTraversal(root);

    return 0;
}

這兩種方法都可以實現(xiàn)二叉樹的中序遍歷。遞歸方法更簡潔直觀，但可能受到?？臻g限制；迭代方法使用顯式棧來避免棧溢出的問題，但代碼相對復雜。

0 踩