数据结构——二叉树基础结构篇（C语言）

2023-06-30

null root 遍历

引言现在是北京时间2023年6月13日9点11分。从决定要开始减脂之后，饥饿总是伴随着我。一觉起来肚子咕咕叫，我还是想先把文章发了再吃第一餐。燕麦加蛋白粉几乎伴随了我大学的第一年早饭。昨天练了一个小时背，练背后还做了45分钟有氧。空腹训练没有影响我的训练状态。这一点我还是比较舒服的。坚持锻炼是一个不

引言

现在是北京时间2023年6月13日9点11分。从决定要开始减脂之后，饥饿总是伴随着我。一觉起来肚子咕咕叫，我还是想先把文章发了再吃第一餐。燕麦加蛋白粉几乎伴随了我大学的第一年早饭。昨天练了一个小时背，练背后还做了45分钟有氧。空腹训练没有影响我的训练状态。这一点我还是比较舒服的。坚持锻炼是一个不错的习惯也恳请你务必多多锻炼自己的身体，身体就是自己最宝贵的财富。

前言

本篇文章讲解的主要是二叉树的结构以及操作，对于学习二叉树来说先了解它的使用，再回过头去学习它的底层原理等效果会更好。所以，我就简单模拟实现了一个简单二叉树，等结构和用法都了解的差不多了再研究二叉树真正创建的方式。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
    
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    node->data = x;
    node->left = NULL;
    node->right = NULL;

    return node;
}

BTNode* CreatTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);


    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    node3->right = node7;

    return node1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

简单回顾

这里简单回顾一下二叉树的概念。二叉树又分为空二叉树和非空二叉数两种。非空二叉树有两个部分构成：根和子树，子树又可以分成根和子树。

二叉树的遍历

二叉树的遍历大致分为四种，前序遍历、中序遍历、后序遍历、层序遍历。下面我们就了解一下各种的遍历方式。

前序遍历

实现思路大致如下，采取递归的思想进行遍历。递归的结束条件为遍历的结点为空就结束。

void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    printf("%d ",root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

中序遍历

与前序遍历的的代码逻辑大致一样，只是访问根的顺序时机不同。本质上还是一样的思想。

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

后序遍历

void PosOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    PosOrder(root->left);
    PosOrder(root->right);
    printf("%d ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
12

求树结点总数

求节点的总个数的思路就是用分治的思想。只要节点不为NULL就表示有一个结点，然后将左右子树的结点总数的和加上1（1即根结点）就能求出当前结点的总数。二叉树是可以不断地拆分成根和左右子树的，其实递归的核心就是处理一个个与原问题类似的子问题。

int TreeSize(BTNode* root)
{
    return root == NULL ?
            0 :
            TreeSize(root->left)
            +TreeSize(root->right)
            +1;
}
1
2
3
4
5
6
7
8

求树的高度

求树的高度也可以采取分治的思路。如果说上面的求结点总数是校长求全校的人数，那么求树的高度其实就是找全校最高的人。实现思路如下，找左右子树中较大的那个加上根节点的高度就是树的高度。

int TreeHeight(BTNode* root)
{
    if(root == NULL)
        return 0;
    
    int lh =TreeHeight(root->left);
    int rh =TreeHeight(root->right);
    
    return lh > rh ? lh+1 : rh+1;
}
1
2
3
4
5
6
7
8
9
10

求第k层节点个数

求第k层的结点个数本质就是求左子树第k-1个结点个数+右子树第k-1层结点个数的和。

int TreeKLevel(BTNode* root, int k)
{
    if(root == NULL)
        return 0;
    if(k == 1)
        return 1;
    int lk = TreeKLevel(root->left, k-1);
    int rk = TreeKLevel(root->right, k-1);
    
    return lk+rk;
    
}
1
2
3
4
5
6
7
8
9
10
11
12

单值二叉树问题

本题的解题的思路有很多，如遍历、分治等。当然这里比较推荐实用分治的思想来进行解决这种二叉树的很多问题中，遍历的结局思路是不如分治的。下面就简单的介绍一下思路。首先，要将结点为空的情况考虑进去。其次，判断左右子结点是否存在且值不相等的情况。最后，分治递归进行比较判断，只要有一个不相等整体就是不为等值二叉树。

二叉树的查找

二叉树的查找接口，它的作用不仅仅是查找到该结点，还可以作为获取想要修改结点的地址的一个方式。实现思路主要是以递归的思想进行遍历整棵树。如果结点的值==val，那就返回这个结点的地址。

BTNode* BTFind(BTNode* root, int x)
{
    if(root == NULL)
    {
        return NULL;
    }
    //判断
    if(root->data == x)
        return root;
    //NULL不返回，找到了才返回
    BTNode* lret = BTFind(root->left, x);
    if(lret)
        return lret;
    BTNode* rret = BTFind(root->right, x);
    if(rret)
        return rret;
    //走到此处表示没有找到结点
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19