数据结构之二叉树

发布于：2025-09-10 ⋅ 阅读:(21) ⋅ 点赞:(0)

一，树的基本概念

树是一种非线性的数据结构，数据逻辑中之所以会引入“树”这个东西，是借助了生活中树的“分支”的概念。逻辑数据中的树可用于描述一种类似组织结构的关系。 在一堆数据中包含一个称为”根”的节点，其他的节点再次组成一个新的“树”，树的定义是一种递归的定义。数据逻辑上的树一般习惯“倒着”，即：根在上，分支和叶子在下。

1.1 树的一般结构

1.2 树的相关术语

1） 结点： 树中的元素 及其子树    

2.）孩子/双亲： 一个结点的后继结点叫该结点的孩子，该结点叫孩子的双亲结点。

3. 结点的度：该结点分支的数量    

4. 叶子： 度为0的结点，          

5.  结点的层次：  从根到该结点的层数(根的层次为1)；    

6. 树的高度(深度)：树中结点层次的最大值

二，二叉树的基本概念

二叉树是每个结点最多只有2个两颗子树的一种“树”型结构。

2.1 二叉树的一般结构

2.2 满二叉树

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。

通俗地讲，一棵满二叉树需要满足以下条件：

  • 所有叶子节点都在同一层。

  • 除了叶子节点，每个节点都有两个子节点。

简单来说，满二叉树是一个“完美”的三角形结构，每一层的节点都是满的。

2.3 完全二叉树

在一棵二叉树中，除最后一层外，若其余层都是满的，或者最后一层是满的，或者是最后一层在右边缺少连续若干结点，则此二叉树为完全二叉树

我们可以这样理解：

  • 将节点从上到下、从左到右进行编号。

  • 这棵树的节点编号必须是连续的，中间不能有任何间断。

  • 换句话说，除了最后一层，其他各层节点数都达到最大，并且最后一层的节点都连续集中在左边。

例如这种就不是完全二叉树，因为它最后一层的结点不是都在左边连续。

2.4 满二叉树与完全二叉树之间的关系

1. 满二叉树一定是完全二叉树。
因为满二叉树的节点是满的，从上到下、从左到右编号一定是连续的，所以它完全符合完全二叉树的定义。

2. 完全二叉树不一定是满二叉树。
完全二叉树只要求最后一层的节点是连续靠左排列的，并不要求最后一层是满的。只有当一棵完全二叉树的最后一层也是满的时候，它才是一棵满二叉树。

总的来说核心关系：

  • 满二叉树是完全二叉树的一个特例。

  • 所有的满二叉树都是完全二叉树，但只有一部分完全二叉树是满二叉树。

  • 可以把满二叉树看作是“最完美”的完全二叉树。

2.5 二叉排序树

二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：
二叉排序树或者是空树，或者是满足如下性质的二叉树：
1.若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
2.若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
3.左、右子树本身又各是一棵二叉排序树。

简单概括就是 “左 < 根 < 右”。

一个重要的推论是： 对二叉排序树进行中序遍历（左-根-右），可以得到一个严格递增的有序序列。

这是一个典型的二叉排序树

可以看到，对于任意节点，其左边的所有后代都比它小，右边的所有后代都比它大。

三，二叉树操作

3.1 二叉树的创建

建立图示二叉树的核心代码：

// 定义二叉树节点结构
//    对应右图中的一个小方块，包含数据区和两个指针区
typedef struct TreeNode {
    char data;                 // 节点存储的数据 (A, B, C...)
    struct TreeNode *left;     // 指向左子树的指针
    struct TreeNode *right;    // 指向右子树的指针
} TreeNode;

// 创建新节点的函数 (辅助函数)
//    功能：分配内存并初始化一个新节点
TreeNode* createNode(char data) {
    // 使用 malloc 动态分配一个 TreeNode 大小的内存空间
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = NULL;  // 新节点的左右孩子默认为空 (对应图中的 ^)
    newNode->right = NULL;
    return newNode; // 返回创建好的新节点的地址
}
// 创建根节点 A
    TreeNode* root = createNode('A');

    // 创建第二层节点 B 和 C
    root->left = createNode('B');
    root->right = createNode('C');

    // 创建第三层节点 D, E, F
    // B 是 D 和 E 的父节点
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    // C 是 F 的父节点
    root->right->right = createNode('F');

    // 创建第四层节点 G, H
    // E 是 G 和 H 的父节点
    root->left->right->left = createNode('G');
    root->left->right->right = createNode('H');

3.2 二叉树(BST)的插入

插入操作遵循以下规则：

  1. 从根节点（root）开始：待插入的值 19 与根节点 20 比较。

  2. 19 < 20：因为 19 小于 20，所以我们向左子树移动，来到节点 15。

  3. 19 > 15：因为 19 大于 15，所以我们向右子树移动，来到节点 17。

  4. 19 > 17：因为 19 大于 17，所以我们尝试向 17 的右子树移动。

  5. 找到插入位置：发现节点 17 的右孩子为空（NULL），这就是 19 应该被插入的位置。

  6. 完成插入：创建一个值为 19 的新节点，并将其作为 17 的右孩子。

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

// 1. 定义二叉树节点结构
typedef struct TreeNode {
    int data;                   // 节点存储的数据
    struct TreeNode *left;      // 指向左子树的指针
    struct TreeNode *right;     // 指向右子树的指针
} TreeNode;

// 2. 创建新节点的函数 (辅助函数)
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 3. 核心：实现二叉排序树的插入函数 (递归版本)
TreeNode* insertNode(TreeNode* root, int data) {
    // 基本情况：如果树为空 (找到了插入位置)，则创建新节点并返回
    if (root == NULL) {
        return createNode(data);
    }

    // 递归步骤：根据值的大小决定向左还是向右
    if (data < root->data) {
        // 待插入的值小于当前节点，应插入到左子树
        // 将返回的新子树根节点连接到当前节点的左指针
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        // 待插入的值大于当前节点，应插入到右子树
        // 将返回的新子树根节点连接到当前节点的右指针
        root->right = insertNode(root->right, data);
    }
    // 如果 data == root->data，则什么也不做 (不允许重复值)

    // 返回 (可能未经修改的) 节点指针
    return root;
}

// 4. 中序遍历函数 (用于验证)
//    (左 -> 根 -> 右)
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal(root->left);
    printf("%d ", root->data);
    inOrderTraversal(root->right);
}

// 5. 释放二叉树内存的函数
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// 6. 主函数
int main() {
    TreeNode* root = NULL;

    // 注意：插入顺序会影响树的最终形状，但只要是二叉排序树，中序遍历结果不变
    root = insertNode(root, 20);
    insertNode(root, 15);
    insertNode(root, 25);
    insertNode(root, 10);
    insertNode(root, 17);
    insertNode(root, 28);
    insertNode(root, 16);

    printf("Original Tree (in-order): ");
    inOrderTraversal(root);
    printf("\n");

    // --- 执行插入操作 ---
    int newValue = 19;
    printf("\nInserting new value: %d\n\n", newValue);
    insertNode(root, newValue);

    // --- 验证结果 ---
    printf("Tree after insertion (in-order): ");
    inOrderTraversal(root);
    printf("\n");

    // --- 释放内存 ---
    freeTree(root);

    return 0;
}

运行结果：

3.3 二叉树遍历

1. 前序遍历

前序遍历通俗的说就是从二叉树的根结点出发，先输出根结点数据，然后输出左结点，最后输出右结点的数据。

对于上图的二叉树，从根结点出发，则第一次到达结点A，故输出A; 继续向左访问，第一次访问结点B，故输出B； 按照同样规则，输出D，输出H； 当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I； I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E； 向E左子树，故输出J； 按照同样的访问规则，继续输出C、F、G。

前序遍历输出为：     ABDHIEJCFG

2. 中序遍历

中序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出根结点，最后输出右结点的数据。

对于上图的二叉树，从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H； 到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H； H右子树为空，则返回至D，此时第二次到达D，故输出D； 由D返回至B，第二次到达B，故输出B； 按照同样规则继续访问，输出J、E、A、F、C、G。

中序遍历输出为：     HDIBJEAFCG

3. 后序遍历

后序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出右结点，最后输出根结点的数据。

对于上图的二叉树，从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H； 到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H； H右子树为空，则返回至H，此时第三次到达H，故输出H； 由H返回至D，第二次到达D，不输出D； 继续访问至I，I左右子树均为空，故第三次访问I时，输出I； 返回至D，此时第三次到达D，故输出D； 按照同样规则继续访问，输出J、E、B、F、G、C，A。

后序遍历输出为：HIDJEBFGCA

4. 程序实现前序遍历，中序遍历，后序遍历

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

// 1. 定义二叉树节点结构
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 2. 创建新节点的辅助函数
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 3. 实现前序遍历 (根 -> 左 -> 右)
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);      // 访问根节点
    preOrderTraversal(root->left);  // 递归遍历左子树
    preOrderTraversal(root->right); // 递归遍历右子树
}

// 4. 实现中序遍历 (左 -> 根 -> 右)
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal(root->left);   // 递归遍历左子树
    printf("%c ", root->data);      // 访问根节点
    inOrderTraversal(root->right);  // 递归遍历右子树
}

// 5. 实现后序遍历 (左 -> 右 -> 根)
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal(root->left);  // 递归遍历左子树
    postOrderTraversal(root->right); // 递归遍历右子树
    printf("%c ", root->data);       // 访问根节点
}

// 6. 释放二叉树内存的函数 (使用后序遍历)
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// 7. 主函数：构建树并执行遍历
int main() {
    // --- 手动构建二叉树 ---
    TreeNode* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');

    root->left->left = createNode('D');
    root->left->right = createNode('E');

    root->right->left = createNode('F');
    root->right->right = createNode('G');

    root->left->left->left = createNode('H');
    root->left->left->right = createNode('I');
    
    root->left->right->left = createNode('J');

    printf("Tree created based on the image.\n\n");

    // --- 执行并输出三种遍历的结果 ---
    printf("Pre-order Traversal : ");
    preOrderTraversal(root);
    printf("\n");

    printf("In-order Traversal  : ");
    inOrderTraversal(root);
    printf("\n");

    printf("Post-order Traversal: ");
    postOrderTraversal(root);
    printf("\n\n");

    // --- 释放内存 ---
    freeTree(root);
    printf("Tree memory has been freed.\n");

    return 0;
}

运行结果：

3.4 二叉树的查找

例如查找图中的结点16。

1.从根结点出发，

2.如果比根节点小，那么就去其左子树找

3.如果比根节点大就去其右子树找  

4.找到叶子都没找到，就代表查找失败

所以对于上图查找，查找过程严格遵循二叉排序树的 “左 < 根 < 右” 特性：

  1. 从根节点（root）开始：将目标值 16 与根节点 20 比较。

  2. 16 < 20：因为 16 小于 20，所以查找路径转向左子树，来到节点 15。

  3. 16 > 15：因为 16 大于 15，所以查找路径转向右子树，来到节点 17。

  4. 16 < 17：因为 16 小于 17，所以查找路径转向左子树，来到节点 16。

  5. 16 == 16：目标值与当前节点值相等，查找成功！

示例程序：

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

// 1. 定义二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 2. 创建新节点的函数 (辅助函数)
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入函数，用于构建树
TreeNode* insertNode(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}


// 3. 核心：实现二叉排序树的查找函数 (递归版本)
//    功能：在以 root 为根的树中查找值为 key 的节点
//    返回：如果找到，返回该节点的指针；否则，返回 NULL
TreeNode* searchNode(TreeNode* root, int key) {
    // 基本情况 1：树为空，或者找到了目标值
    if (root == NULL || root->data == key) {
        return root;
    }

    // 递归步骤：根据值的大小决定向左还是向右查找
    if (key < root->data) {
        // 目标值小于当前节点，去左子树查找
        return searchNode(root->left, key);
    } else {
        // 目标值大于当前节点，去右子树查找
        return searchNode(root->right, key);
    }
}

// 4. 释放二叉树内存的函数
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// 5. 主函数
int main() {
    TreeNode* root = NULL;

    // --- 构建图中所示的树 ---
    root = insertNode(root, 20);
    insertNode(root, 15);
    insertNode(root, 25);
    insertNode(root, 10);
    insertNode(root, 17);
    insertNode(root, 28);
    insertNode(root, 16);

    printf("Binary Search Tree has been created.\n\n");

    // --- 执行查找操作 ---
    
    // 示例 1: 查找存在的节点 16
    int key_to_find_1 = 16;
    printf("Searching for %d...\n", key_to_find_1);
    TreeNode* result1 = searchNode(root, key_to_find_1);

    if (result1 != NULL) {
        printf("Found! The value is %d.\n", result1->data);
    } else {
        printf("Value %d not found in the tree.\n", key_to_find_1);
    }

    printf("\n");

    // 示例 2: 查找不存在的节点 99
    int key_to_find_2 = 99;
    printf("Searching for %d...\n", key_to_find_2);
    TreeNode* result2 = searchNode(root, key_to_find_2);

    if (result2 != NULL) {
        printf("Found! The value is %d.\n", result2->data);
    } else {
        printf("Value %d not found in the tree.\n", key_to_find_2);
    }
    
    // --- 释放内存 ---
    freeTree(root);

    return 0;
}

输出结果：

3.5 二叉树的结点删除

删除操作的逻辑分析

在二叉排序树中，删除节点需要分三种情况讨论，以确保删除后仍然满足“左 < 根 < 右”的性质。

  1. 情况一：被删除的节点是叶子节点（没有孩子）

    • 最简单的情况，直接将其父节点的对应指针（左或右）设为 NULL，然后释放该节点即可。

  2. 情况二：被删除的节点只有一个孩子（只有左孩子或只有右孩子）

    • 也比较简单，将其父节点的指针“越过”被删除的节点，直接指向其唯一的孩子，然后释放该节点。

  3. 情况三：被删除的节点有两个孩子（既有左孩子又有右孩子）

    • 这是最复杂的情况，也是图中展示的情况。

    • 问题所在：不能直接删除该节点（如节点 15），否则会造成其左右子树都与父节点断开连接，树的结构就被破坏了。

    • 解决方案：必须在不破坏二叉排序树性质的前提下，找到一个“替身”节点来取代被删除节点的位置。这个“替身”有两个选择：

      1. 前驱节点 (In-order Predecessor)：被删除节点左子树中最大的节点。

      2. 后继节点 (In-order Successor)：被删除节点右子树中最小的节点。

图片选择前驱节点作为“替身”的策略：

  • ① 确定目标：要删除的节点是 15，它有两个孩子 (10 和 19)。

  • ② 寻找替身：

    • 进入 15 的左子树（根为 10）。

    • 在这个子树中寻找值最大的节点。根据二叉排序树的性质，最大值一定在该子树的“最右边”。

    • 查找路径是 10 -> 11。节点 11 就是 15 的前驱节点 (tmp)。

  • ③ 执行替换与删除 :

    1. 将“替身”节点 11 的值复制到要被删除的节点 15 的位置。现在原来的 15 节点存储的值变成了 11。

    2. 此时，问题就转化成了“在左子树中删除原来的替身节点 11”。

    3. 删除节点 11 是一个更简单的情况（叶子节点或只有一个孩子的节点），可以通过递归调用删除函数来完成。

示例程序（删除图中的结点15）：

#include <stdio.h>
#include <stdlib.h> //malloc 和 free

// 1. 定义二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 辅助函数：创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 辅助函数：插入节点以构建树
TreeNode* insertNode(TreeNode* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insertNode(root->left, data);
    else if (data > root->data)
        root->right = insertNode(root->right, data);
    return root;
}

// 辅助函数：寻找子树中最大的节点 (前驱)
TreeNode* findMaxNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->right != NULL) {
        current = current->right;
    }
    return current;
}

// 核心函数：删除二叉排序树中的节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) {
        return root;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        TreeNode* temp = findMaxNode(root->left);
        root->data = temp->data;
        root->left = deleteNode(root->left, temp->data);
    }
    return root;
}

// 中序遍历函数 (用于验证)
void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}


// 采用后序遍历（左 -> 右 -> 根）的顺序来确保安全释放
void freeTree(TreeNode* root) {
    // 递归的基准情况
    if (root == NULL) {
        return;
    }

    // 1. 先释放左子树
    freeTree(root->left);

    // 2. 再释放右子树
    freeTree(root->right);

    // 3. 最后释放根节点
    free(root);
}
// =======================================================

// 主函数
int main() {
    TreeNode* root = NULL;

    // --- 构建树 ---
    root = insertNode(root, 20);
    insertNode(root, 15);
    insertNode(root, 25);
    insertNode(root, 10);
    insertNode(root, 19);
    insertNode(root, 28);
    insertNode(root, 6);
    insertNode(root, 11);

    printf("Original Tree (in-order): ");
    inOrderTraversal(root);
    printf("\n");

    // --- 执行删除操作 ---
    int key_to_delete = 15;
    printf("\nDeleting node: %d\n\n", key_to_delete);
    root = deleteNode(root, key_to_delete);

    // --- 验证结果 ---
    printf("Tree after deletion (in-order): ");
    inOrderTraversal(root);
    printf("\n\n");

    // --- 补充完整的内存释放操作 ---
    printf("Starting to free the entire tree memory...\n");
    freeTree(root);
    root = NULL; // 将根指针置为NULL，防止成为野指针
    printf("All tree memory has been freed successfully.\n");

    return 0;
}

运行结果：

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布