数据结构初阶：二叉树的链式存储结构

该二叉树的结构如下所示：

三、链式二叉树的基本操作

在链式二叉树中，主要进行以下操作：前序遍历、中序遍历、后序遍历、层序遍历、计算总结点个数、计算叶子节点个数、计算第 k 层节点个数、计算深度、查找元素等。

3.1、前序遍历

前序遍历指访问根节点的操作发生在访问左右子树之前（根 -> 左 -> 右）。

// 前序遍历 (根->左->右)
void PreOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->leftChild);
    PreOrder(root->rightChild);
}

递归终止条件为 root == NULL。遍历过程严格遵循'根->左->右'原则。

3.2、中序遍历

中序遍历即访问根节点的操作发生在访问左子树之后，在访问右子树之前（左 -> 根 -> 右）。

// 中序遍历 (左->根->右)
void InOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    InOrder(root->leftChild);
    printf("%c ", root->data);
    InOrder(root->rightChild);
}

3.3、后序遍历

后序遍历即访问根节点的操作发生在访问左子树和右子树之后（左 -> 右 -> 根）。

// 后序遍历 (左->右->根)
void LastOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    LastOrder(root->leftChild);
    LastOrder(root->rightChild);
    printf("%c ", root->data);
}

3.4、计算二叉树的总结点个数

采用递归方式，统计左子树和右子树的节点数并相加。

int BinaryTreeSize_of_Node(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}

3.5、计算二叉树的叶子结点个数

当 leftChild 和 rightChild 均为 NULL 时，返回 1。

int BinaryTreesize_of_Leaf(BTNode* root) {
    if (root == NULL) return 0;
    if (root->leftChild == NULL && root->rightChild == NULL) return 1;
    return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}

3.6、计算第 k 层节点个数

通过递归减少 k 值，当 k=1 时返回 1。

int BinaryTreeSize_of_K(BTNode* root, int k) {
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}

3.7、计算二叉树的深度

比较左右子树的深度，取较大值加 1。

int BinaryTreeSize_of_Depth(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
    int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

3.8、查找元素

遍历整个二叉树，若存在该元素则输出提示。

void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
    if (root == NULL) return;
    if (root->data == val) {
        printf("找到了!\n");
        return;
    }
    BinaryTreeSearch_of_val(root->leftChild, val);
    BinaryTreeSearch_of_val(root->rightChild, val);
}

3.9、层序遍历

借助队列实现，先将根节点入队，循环取出队头元素并打印，将其左右孩子入队。

void LevelOrder(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        printf("%c ", top->data);
        Pop_Queue(pQueue);
        if (top->leftChild) {
            Push_Queue(pQueue, top->leftChild);
        }
        if (top->rightChild) {
            Push_Queue(pQueue, top->rightChild);
        }
    }
    DestroyQueue(pQueue);
}

3.10、判断是否为完全二叉树

通过层序遍历，当遇到空节点后，后续所有节点必须为空才算完全二叉树。

bool IsBinaryTree_of_Complete(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        QElemtype top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top == NULL) {
            break;
        }
        Push_Queue(pQueue, top->leftChild);
        Push_Queue(pQueue, top->rightChild);
    }
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top != NULL) {
            DestroyQueue(pQueue);
            return false;
        }
    }
    DestroyQueue(pQueue);
    return true;
}

3.11、外部代码的引入

需确保引入了队列的头文件（如 Queue.h），并根据需要调整数据类型（如将队列元素类型定义为 struct BinaryTree*）。

四、综合代码

以下是整合后的二叉树核心代码及测试主函数：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Queue.h"

typedef char Elemtype;

typedef struct BinaryTree {
    Elemtype data;
    struct BinaryTree* leftChild;
    struct BinaryTree* rightChild;
} BTNode;

BTNode* BuyNode(Elemtype data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL) {
        perror("create new node fail!\n");
    }
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return newNode;
}

BTNode* createNewBT() {
    BTNode* NodeA = BuyNode('A');
    BTNode* NodeB = BuyNode('B');
    BTNode* NodeC = BuyNode('C');
    BTNode* NodeD = BuyNode('D');
    BTNode* NodeE = BuyNode('E');
    BTNode* NodeF = BuyNode('F');
    BTNode* NodeG = BuyNode('G');
    BTNode* NodeH = BuyNode('H');
    BTNode* NodeI = BuyNode('I');
    BTNode* NodeO = BuyNode('O');
    NodeA->leftChild = NodeB;
    NodeA->rightChild = NodeC;
    NodeB->leftChild = NodeD;
    NodeB->rightChild = NodeE;
    NodeD->leftChild = NodeH;
    NodeC->leftChild = NodeF;
    NodeF->leftChild = NodeI;
    NodeH->leftChild = NodeO;
    return NodeA;
}

void PreOrder(BTNode* root) {
    if (root == NULL) { printf("NULL "); return; }
    printf("%c ", root->data);
    PreOrder(root->leftChild);
    PreOrder(root->rightChild);
}

void InOrder(BTNode* root) {
    if (root == NULL) { printf("NULL "); return; }
    InOrder(root->leftChild);
    printf("%c ", root->data);
    InOrder(root->rightChild);
}

void LastOrder(BTNode* root) {
    if (root == NULL) { printf("NULL "); return; }
    LastOrder(root->leftChild);
    LastOrder(root->rightChild);
    printf("%c ", root->data);
}

int BinaryTreeSize_of_Node(BTNode* root) {
    if (root == NULL) return 0;
    return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}

int BinaryTreesize_of_Leaf(BTNode* root) {
    if (root == NULL) return 0;
    if (root->leftChild == NULL && root->rightChild == NULL) return 1;
    return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}

int BinaryTreeSize_of_K(BTNode* root, int k) {
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}

int BinaryTreeSize_of_Depth(BTNode* root) {
    if (root == NULL) return 0;
    int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
    int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
    if (root == NULL) return;
    if (root->data == val) { printf("找到了!\n"); return; }
    BinaryTreeSearch_of_val(root->leftChild, val);
    BinaryTreeSearch_of_val(root->rightChild, val);
}

void LevelOrder(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        printf("%c ", top->data);
        Pop_Queue(pQueue);
        if (top->leftChild) Push_Queue(pQueue, top->leftChild);
        if (top->rightChild) Push_Queue(pQueue, top->rightChild);
    }
    DestroyQueue(pQueue);
}

bool IsBinaryTree_of_Complete(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        QElemtype top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top == NULL) break;
        Push_Queue(pQueue, top->leftChild);
        Push_Queue(pQueue, top->rightChild);
    }
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top != NULL) { DestroyQueue(pQueue); return false; }
    }
    DestroyQueue(pQueue);
    return true;
}

int main() {
    BTNode* NodeA = createNewBT();
    printf("前序遍历:"); PreOrder(NodeA); printf("\n");
    printf("中序遍历:"); InOrder(NodeA); printf("\n");
    printf("后序遍历:"); LastOrder(NodeA); printf("\n");
    printf("总结点个数：%d\n", BinaryTreeSize_of_Node(NodeA));
    printf("叶子结点个数：%d\n", BinaryTreesize_of_Leaf(NodeA));
    printf("第 4 层节点个数：%d\n", BinaryTreeSize_of_K(NodeA, 4));
    printf("二叉树深度：%d\n", BinaryTreeSize_of_Depth(NodeA));
    BinaryTreeSearch_of_val(NodeA, 'I');
    printf("层序遍历："); LevelOrder(NodeA); printf("\n");
    if (IsBinaryTree_of_Complete(NodeA)) printf("是完全二叉树\n");
    else printf("不是完全二叉树\n");
    return 0;
}

以下是队列辅助实现的代码：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef struct BinaryTree* QElemtype;

typedef struct QueueNode {
    QElemtype data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* phead;
    QueueNode* ptail;
} Queue;

void InitQueue(Queue* pQueue) {
    pQueue->phead = pQueue->ptail = NULL;
}

void Push_Queue(Queue* pQueue, QElemtype x) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        perror("Fail reason: ");
        exit(0);
    }
    newNode->data = x;
    newNode->next = NULL;
    if (pQueue->phead == NULL) {
        pQueue->phead = pQueue->ptail = newNode;
    } else {
        pQueue->ptail->next = newNode;
        pQueue->ptail = pQueue->ptail->next;
    }
}

bool isEmpty(Queue* pQueue) {
    assert(pQueue);
    return pQueue->phead == NULL;
}

void Pop_Queue(Queue* pQueue) {
    assert(pQueue);
    if (pQueue->phead == NULL) {
        perror("Fail reason: ");
        exit(0);
    }
    QueueNode* next = pQueue->phead->next;
    free(pQueue->phead);
    pQueue->phead = next;
}

QElemtype GetElemFront(Queue* pQueue) {
    assert(pQueue);
    if (isEmpty(pQueue)) exit(1);
    return pQueue->phead->data;
}

void DestroyQueue(Queue* pQueue) {
    assert(pQueue);
    QueueNode* pcur = pQueue->phead;
    while (pcur != NULL) {
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pQueue->phead = pQueue->ptail = NULL;
}

运行结果示例：