C语言数据结构系列篇：二叉树的概念及满二叉树与完全二叉树

一、二叉树的概念

二叉树是一种特殊的树型结构，它的每个节点最多有两个子节点，称为左子节点和右子节点。二叉树可以为空树，也可以是非空树。二叉树的每个节点保存着某种数据，可以是整数、浮点数、字符串等。

下图是一个简单的二叉树示例：

    1
   / \
  2   3
     / \
    4   5

其中，数字表示节点保存的数据。根节点是1，左子节点是2，右子节点是3，3节点的左子节点是4，右子节点是5。

二、满二叉树

满二叉树是一种特殊的二叉树，它的所有非叶子节点都有两个子节点，并且所有叶子节点都在同一层。也就是说，除了最后一层，其它层数的节点个数都是满的，最后一层的节点全部靠左排列。

下图是一个满二叉树示例：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

该满二叉树共有7个节点，它们的数据分别是1、2、3、4、5、6、7。

三、完全二叉树

完全二叉树也是一种特殊的二叉树，它除了最后一层之外，其它层的节点都是满的，最后一层的节点都靠左排列。与满二叉树不同的是，完全二叉树的节点个数不一定是满的。

下图是一个完全二叉树示例：

        1
      /   \
     2     3
    / \   / 
   4   5 6   

该完全二叉树共有6个节点，它们的数据分别是1、2、3、4、5、6。由于最后一层缺少一个节点，因此它不是满二叉树，而是完全二叉树。

四、示例说明

下面是一个满二叉树的示例程序：

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

typedef struct TreeNode {
    int data;  //节点保存的数据
    struct TreeNode *left;  //左子节点
    struct TreeNode *right;  //右子节点
} TreeNode, *BinaryTree;

//递归创建满二叉树
BinaryTree createFullBinaryTree(int depth) {
    if (depth == 0) {
        return NULL;
    }
    BinaryTree tree = (BinaryTree)malloc(sizeof(TreeNode));
    if (tree == NULL) {
        return NULL;
    }
    tree->data = depth;
    tree->left = createFullBinaryTree(depth - 1);
    tree->right = createFullBinaryTree(depth - 1);
    return tree;
}

//前序遍历二叉树
void preOrderTraversal(BinaryTree tree) {
    if (tree != NULL) {
        printf("%d ", tree->data);
        preOrderTraversal(tree->left);
        preOrderTraversal(tree->right);
    }
}

int main() {
    BinaryTree tree = createFullBinaryTree(3);
    preOrderTraversal(tree);  //输出结果：1 2 4 5 3 6 7
    return 0;
}

这个程序使用递归方式创建了一个深度为3的满二叉树，并进行了前序遍历。前序遍历的输出结果为1 2 4 5 3 6 7，与满二叉树的数据对应。

下面是一个完全二叉树的示例程序：

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

typedef struct TreeNode {
    int data;  //节点保存的数据
    struct TreeNode *left;  //左子节点
    struct TreeNode *right;  //右子节点
} TreeNode, *BinaryTree;

//递归创建完全二叉树
BinaryTree createCompleteBinaryTree(int depth, int current, int *data) {
    if (current > depth || *data < 1) {
        return NULL;
    }
    BinaryTree tree = (BinaryTree)malloc(sizeof(TreeNode));
    if (tree == NULL) {
        return NULL;
    }
    tree->data = *data--;
    tree->left = createCompleteBinaryTree(depth, current + 1, data);
    tree->right = createCompleteBinaryTree(depth, current + 1, data);
    return tree;
}

//前序遍历二叉树
void preOrderTraversal(BinaryTree tree) {
    if (tree != NULL) {
        printf("%d ", tree->data);
        preOrderTraversal(tree->left);
        preOrderTraversal(tree->right);
    }
}

int main() {
    int data[] = {1, 2, 3, 4, 5, 6};
    BinaryTree tree = createCompleteBinaryTree(3, 1, &data[5]);
    preOrderTraversal(tree);  //输出结果：1 2 4 5 3 6
    return 0;
}

这个程序使用递归方式创建了一个深度为3的完全二叉树，并进行了前序遍历。前序遍历的输出结果为1 2 4 5 3 6，与完全二叉树的数据对应。注意，这个程序使用了指向data数组的指针来逆序访问数组元素，在递归过程中动态获取节点的数据。

阅读剩余 66%