C语言近万字为你讲透树与二叉树

什么是树？

树是一种用来组织数据的非线性数据结构，它由一个根节点和若干个子节点组成，并且每个节点可能有若干个子节点。

什么是二叉树？

二叉树是一种特殊的树，它的每个节点最多只有两个子节点，并且分别称为左子节点和右子节点，左子节点在二叉树中永远排在右子节点的前面。

二叉树的遍历方式

二叉树的遍历方式有三种：

• 前序遍历（preorder traversal）：对于每个节点，先访问该节点，然后依次遍历左子树和右子树。
• 中序遍历（inorder traversal）：对于每个节点，先遍历左子树，然后访问该节点，最后遍历右子树。
• 后序遍历（postorder traversal）：对于每个节点，先遍历左子树和右子树，最后访问该节点。

二叉树的实现方式

二叉树的实现可以通过链表或数组来实现，链表实现方式可以采用链式存储结构，数组实现方式可以采用顺序存储结构。

通过链表来实现二叉树

二叉树的节点结构可以定义为：

typedef struct TreeNode {
    int data;
    struct TreeNode *leftChild;
    struct TreeNode *rightChild;
} TreeNode;

• data：节点的数据，任意数据类型。
• leftChild：指向该节点的左子树。
• rightChild：指向该节点的右子树。

通过数组来实现二叉树

数组实现方式可以采用一维数组来存储二叉树，通过计算数组下标来访问相应节点。假设二叉树中的节点按照层级顺序从上至下、从左至右依次编号，那么对于编号为i的节点，

• 如果i=1，则该节点为树根节点。
• 如果i>1，则该节点的父节点的编号为i/2（向下取整）。
• 如果2i≤n，则该节点的左子节点的编号为2i。
• 如果2i+1≤n，则该节点的右子节点的编号为2i+1。

示例说明

示例1

假设现有以下二叉树：

        5
       / \
      3   7
     / \   \
    1   4   9

该二叉树可以通过链表的方式实现，代码如下：

typedef struct TreeNode {
    int data;
    struct TreeNode *leftChild;
    struct TreeNode *rightChild;
} TreeNode;

void createBinaryTree(TreeNode **root) {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        *root = NULL;
    } else {
        *root = (TreeNode *) malloc(sizeof(TreeNode));
        (*root)->data = data;
        createBinaryTree(&(*root)->leftChild);
        createBinaryTree(&(*root)->rightChild);
    }
}

void preOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderTraversal(root->leftChild);
        preOrderTraversal(root->rightChild);
    }
}

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->leftChild);
        printf("%d ", root->data);
        inOrderTraversal(root->rightChild);
    }
}

void postOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        postOrderTraversal(root->leftChild);
        postOrderTraversal(root->rightChild);
        printf("%d ", root->data);
    }
}

int main() {
    TreeNode *root = NULL;
    createBinaryTree(&root);
    printf("前序遍历：");
    preOrderTraversal(root);
    printf("\n中序遍历：");
    inOrderTraversal(root);
    printf("\n后序遍历：");
    postOrderTraversal(root);
    printf("\n");
    return 0;
}

在执行该程序时，输入数据为：

5
3
1
-1
-1
4
-1
-1
7
-1
9
-1
-1

程序的输出结果为：

前序遍历：5 3 1 4 7 9
中序遍历：1 3 4 5 7 9
后序遍历：1 4 3 9 7 5

示例2

假设现有以下二叉树：

        5
       / \
      3   7
     / \   \
    1   4   9

该二叉树可以通过数组的方式实现，代码如下：

#define MAX_SIZE 100

int binaryTree[MAX_SIZE] = {5, 3, 7, 1, 4, -1, 9};

void preOrderTraversal(int nodeIndex) {
    if (binaryTree[nodeIndex] != -1) {
        printf("%d ", binaryTree[nodeIndex]);
        preOrderTraversal(2 * nodeIndex);
        preOrderTraversal(2 * nodeIndex + 1);
    }
}

void inOrderTraversal(int nodeIndex) {
    if (binaryTree[nodeIndex] != -1) {
        inOrderTraversal(2 * nodeIndex);
        printf("%d ", binaryTree[nodeIndex]);
        inOrderTraversal(2 * nodeIndex + 1);
    }
}

void postOrderTraversal(int nodeIndex) {
    if (binaryTree[nodeIndex] != -1) {
        postOrderTraversal(2 * nodeIndex);
        postOrderTraversal(2 * nodeIndex + 1);
        printf("%d ", binaryTree[nodeIndex]);
    }
}

int main() {
    printf("前序遍历：");
    preOrderTraversal(1);
    printf("\n中序遍历：");
    inOrderTraversal(1);
    printf("\n后序遍历：");
    postOrderTraversal(1);
    printf("\n");
    return 0;
}

程序的输出结果为：

前序遍历：5 3 1 4 7 9
中序遍历：1 3 4 5 7 9
后序遍历：1 4 3 9 7 5

在程序中，数组binaryTree中按照层级顺序存储了二叉树的所有节点，其中-1表示空节点。可以通过计算数组下标来遍历二叉树。