数据结构--二叉树--C语言_数据结构二叉树c语言

该程序是完全照搬视频中的代码。链接: https://www.bilibili.com/video/BV18p4y167Md?p=108.

典型的存储方式就两种，要么是顺序存储（利用数组这种机制），要么是链式存储（利用链表这种机制）。

基于二叉树区别于其他树的结构，且其最多只有两个孩子结点等特性，二叉树可以用顺序存储来实现，但这种顺序存储在空间利用率上会有一定的缺陷。

n层二叉树（或者说深度为 n 的二叉树）最多有2ⁿ - 1个结点。

使用顺序存储（利用数组）来实现满二叉树和完全二叉树是非常适合的，斜二叉树就不合适了。

实现二叉树的最基本的思想就是 “ 递归 ”

这里创建二叉树的规则如下：

与当前结点的 id 的值进行比较，若比当前结点小，就作为当前结点的左子树，如果比当前结点大，就作为当前结点的右子树。如果当前结点已经有了左子树或者右子树，就继续与它的左子树或者右子树进行比较，然后进行创建。

具体实现是：

在程序中，我们会事先把每个要创建的结点的 id 都定义在一个数组中。当然，由于第一个 id 之前没有其他的 id，无法比较，所以我们就直接把它作为根节点。当创建第二个结点的时候，就让它与根节点进行比较，然后依此进行。

示例如下：

程序中在二叉树中插入第一个结点的示意图如下：

这个程序实现了三个功能：
1、在二叉树中插入结点
2、根据 id 来查找结点
3、采用 “左倒” 的方式将二叉树给绘制出来。

程序代码如下：

目前，对于递归的思想，没有理解的很透彻

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

#define NAMESIZE 32

struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};

/*
  二叉链表的基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了
存放与数据信息之外，还要设置指示左右孩子的指针。
*/
//二叉链表的缺点--不能够通过孩子结点来找到它的双亲
struct node_st
{
    //数据域
    struct score_st data;
    //指针域
    struct node_st *lchild,*rchild;
};

//待插入的数据 -- 要遵循一定的原则
//注意第一个参数是一个二级指针
int insert(struct node_st **root,struct score_st *data)
{
    struct node_st *node;

    //当第一个结点插入进来
    if(*root == NULL)
    {
        node = malloc(sizeof(*node));
        if(node == NULL)
            return -1;
        node->data = *data;
        node->lchild = NULL;
        node->rchild = NULL;

        *root = node ;		
		return 0;
    }
    //将要插入的这个结点的id与当前结点的id进行比较，
    //如果相等或者更小的话，就插入到左子树，
    //否则就插入到右子树。
    if(data->id <= (*root)->data.id)//'.'用于结构体变量访问成员,->用于结构体指针访问成员
        return insert(&(*root)->lchild,data);
    return insert(&(*root)->rchild,data);
}

void print_s(struct score_st *data)
{
    printf("%d %s %d %d.\n",data->id,data->name,data->math,data->chinese);
}

struct score_st *find(struct node_st *root,int id)
{
    if(root == NULL)
        return NULL;
    if(id == root->data.id)
        return &root->data;
    if(id < root->data.id)
        return find(root->lchild,id);
    else
        return find(root->rchild,id);
}

//struct node_st *root -- 当前结点
//level -- 当前结点所在的层数
void draw_(struct node_st *root,int level)
{
    int i;
    //如果当前结点为叶子结点
    if(root == NULL)
        return;
    //父结点的右子树 -- 右子树位于它的父结点的下一层
    draw_(root->rchild,level+1);

    for(i=0;i<level;i++)
        printf("    ");
    //父结点
    print_s(&root->data);
//左子树 -- 左子树位于它的父结点的下一层
    draw_(root->lchild,level+1);
}

void draw(struct node_st *root)
{
    //画图采用向左倒的方式
/*                     C
        A     左倒    /
       / \    --->   A
      B   C           \
                       B
*/
// 画出这样的一棵树需要有两个要素：1、要分清楚当前结点的左右子树
//                                 2、还要进行计数,得到当前数的度(层数),方便计算出空格数

    draw_(root,0);//从这棵树的第一层,即根节点开始
}

int main()
{
    int i;
    int arr[] = {1,2,3,7,6,5,9,8,4};
    //一说到链式存储,就要反应到要不要有头结点
    //这里,头结点没有什么必要。
    //创建一颗空树
    struct node_st *tree = NULL;
    //我要想调用insert的话,首先把每个结点的数据结构给做出来
    struct score_st tmp,*find_result;

    //我们要使用insert函数将这棵树给构建起来
    for(i=0;i < sizeof(arr)/sizeof(*arr);i++)
    {
        tmp.id = arr[i];

        snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);

        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        //这棵数由于是不带头结点的,所以起始位置会变化,所以应该传入的是这棵树的地址过去.
        insert(&tree,&tmp);
    }

    //把这棵树给绘制出来
    draw(tree);

    //这里将查找的测试代码给注释了
    #if 0
    //我要来查找有没有id为2的那个人
    int tmpid = 2;
    //我希望在这棵树中查找一个指定的id
    find_result = find(tree,tmpid);
    if(find_result == NULL)
        printf("Can not find the id %d . \n",tmpid);
    else
        print_s(find_result);

    return 0;
    #endif
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

对于该程序的递归调用参考
https://www.bilibili.com/video/BV1ze411x7x8.