数据结构：二叉树基础概念与 C 语言实现

3. 构建二叉树

这里通过一个前序遍历的数组来构建二叉树。例如 "ABD##E#H##CF##G##"，其中 # 表示空节点。

// BTNode.c
BTNode* BinaryTreeCreate(BTDataType* ch, int* pi) {
    if (ch[*pi] == '#') {
        return NULL;
    }
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = ch[(*pi)++];
    newnode->left = BinaryTreeCreate(ch, pi);
    (*pi)++;
    newnode->right = BinaryTreeCreate(ch, pi);
    return newnode;
}

4. 二叉树遍历

遍历主要有四种：前序、中序、后序、层序。核心在于递归处理左右子树的顺序不同。

前序遍历

先遍历根，接着左子树，最后右子树。

void BinaryTreePrevOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}

中序遍历

先遍历左子树，接着根，最后右子树。

void BinaryTreeInOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    BinaryTreeInOrder(root->left);
    printf("%c ", root->data);
    BinaryTreeInOrder(root->right);
}

后序遍历

先遍历右子树，接着左子树，最后根。

void BinaryTreePostOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->data);
}

层序遍历

一层一层地遍历。这需要借助队列来实现。每次取出队头结点，将其左右孩子入队。

void BinaryTreeLevelOrder(BTNode* root) {
    Queue Q;
    QueueInit(&Q);
    if (root) {
        QueuePush(&Q, root);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* front = QueueFront(&Q);
        printf("%c ", front->data);
        QueuePop(&Q);
        if (front->left) {
            QueuePush(&Q, front->left);
        }
        if (front->right) {
            QueuePush(&Q, front->right);
        }
    }
    QueueDestroy(&Q);
}

5. 其他常用操作

节点个数计算

递归计算左右子树节点数并加 1。

int BinaryTreeSize(BTNode* root) {
    return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二叉树高度计算

返回左右子树高度较高的一边加 1。

int BinaryTreeHight(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return fmax(BinaryTreeHight(root->left), BinaryTreeHight(root->right)) + 1;
}

第 k 层节点个数计算

初始 k，若未到目标层则 k-1 并递归左右子树。

int BinaryTreeLevelKSize(BTNode* root, int k) {
    if (root == NULL) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

查找值为 x 的节点

递归查找，注意返回值传递。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == x) {
        return root;
    }
    BTNode* ret1 = BinaryTreeFind(root->left, x);
    if (ret1) {
        return ret1;
    }
    BTNode* ret2 = BinaryTreeFind(root->right, x);
    if (ret2) {
        return ret2;
    }
    return NULL;
}

判断是否是完全二叉树

利用层序遍历，遇到空节点后若还有非空节点，则不是完全二叉树。

int BinaryTreeComplete(BTNode* root) {
    Queue Q;
    QueueInit(&Q);
    if (root) {
        QueuePush(&Q, root);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* front = QueueFront(&Q);
        QueuePop(&Q);
        if (front == NULL) {
            break;
        }
        QueuePush(&Q, front->left);
        QueuePush(&Q, front->right);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* front = QueueFront(&Q);
        QueuePop(&Q);
        if (front != NULL) {
            QueueDestroy(&Q);
            return 0;
        }
    }
    QueueDestroy(&Q);
    return 1;
}

四、完整代码结构

工程通常分为头文件和源文件，以管理依赖和编译。

1. Queue.h & Queue.c

用于实现队列辅助层序遍历。注意包含标准库头文件如 <stdio.h>、<stdlib.h> 等，替换原文件中可能存在的拼写错误（如 sperror.h）。

2. Test.c

测试用例示例。

#include "BTNode.h"

int main() {
    char ch[100] = "ABD##E#H##CF##G##";
    int i = 0;
    BTNode* T = BinaryTreeCreate(ch, &i);

    printf("节点个数：%d\n", BinaryTreeSize(T));
    printf("叶子节点个数：%d\n", BinaryTreeLeafSize(T));
    printf("高度：%d\n", BinaryTreeHight(T));
    printf("第 3 层节点个数：%d\n", BinaryTreeLevelKSize(T, 3));

    BTNode* ret = BinaryTreeFind(T, 'G');
    if (ret) {
        printf("找到 G: %c\n", ret->data);
    } else {
        printf("未找到\n");
    }

    printf("是否完全二叉树：%s\n", BinaryTreeComplete(T) ? "是" : "否");

    printf("前序：");
    BinaryTreePrevOrder(T);
    printf("\n");
    printf("中序：");
    BinaryTreeInOrder(T);
    printf("\n");
    printf("后序：");
    BinaryTreePostOrder(T);
    printf("\n");
    printf("层序：");
    BinaryTreeLevelOrder(T);
    printf("\n");

    BinaryTreeDestory(&T);
    return 0;
}

本文涵盖了二叉树的核心知识点与工程化实现细节。理解递归思想是掌握二叉树的关键，实际开发中建议多动手调试代码，观察栈帧变化与指针指向，从而建立直观的空间模型。