「二叉树-链式结构」C语言实现

文章目录
  1. 示意图
  2. 结构定义
  3. 源码

示意图

待补充。。。

结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*------------------------- 二叉树链式结构定义 ------------------------*/

typedef char TElemType;

// 二叉链表节点
typedef struct biTNode {
    TElemType data;
    struct biTNode * pLChild;
    struct biTNode * pRChild;
} BiTNode, *pBiTNode;

// 定义二叉树结构
// 二叉树只要有一个头指针即可确定，与链表定义相同
typedef pBiTNode LinkBiTree;

/*------------------------- 二叉树链式结构定义 ------------------------*/

源码

采用模块化实现二叉树的链式结构，其中需要用到队列，共分为5个文件，分别如下：

  1. 主函数：main.c 文件
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
/*
 * 功能: 队列-链式结构
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-09-16
 */

#include <stdio.h>

#include "linkBiTree.h"


int main(void)
{
    LinkBiTree T;

    InitBiTree(&T);

    printf("请按前序输入二叉树（如：abdg###e##c#f##，a 为根节点，b 为左子树，# 为空节点）：\n");  // abdg###e##c#f##
    CreatBiTree(&T);
    while ( getchar() != '\n');  // 消除回车字符

    printf("前序遍历二叉树：");
    PreOrderTraverse(T);
    printf("\n");

    printf("中序遍历二叉树：");
    InOrderTraverse(T);
    printf("\n");

    printf("后序遍历二叉树：");
    PostOrderTraverse(T);
    printf("\n");

    printf("层序遍历二叉树：");
    LevelOrderTraverse(T);
    
    printf("二叉树的根为：%c\n", Root(T));

    printf("二叉树的深度为：%d\n", BiTreeDepth(T));

    TElemType e;
    printf("请输入一个节点的值：");
    scanf("%c", &e);
    while ( getchar() != '\n');  // 消除回车字符
    printf("节点的值为 %c\n", e);

    pBiTNode p = Point(T, e);
    printf("指向该节点的指针是：%p\n", p);
    printf("该指针所指节点的值是：%c\n", Value(p));
    printf("该节点的父节点值是：%c\n", Parent(T, e));
    printf("该节点的左孩子值是：%c\n", LeftChild(T, e));
    printf("该节点的右孩子值是：%c\n", RightChild(T, e));
    printf("该节点的左兄弟值是：%c\n", LeftSibling(T, e));
    printf("该节点的右兄弟值是：%c\n", RightSibling(T, e));

    printf("欲改变此节点的值，请输入新值：");
    scanf("%c", &e);
    while ( getchar() != '\n');  // 消除回车字符
    Assign(p, e);

    printf("前序遍历二叉树：");
    PreOrderTraverse(T);
    printf("\n");

    return 0;
}
  1. 链式二叉树结构定义及对外函数声明：linBITree.h 文件
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
#ifndef _LINKBITREE_H_
#define _LINKBITREE_H_

#include <stdbool.h>

#define Nil '#'

/*------------------------- 二叉树链式结构定义 ------------------------*/

typedef char TElemType;

// 二叉链表节点
typedef struct biTNode {
    TElemType data;
    struct biTNode * pLChild;
    struct biTNode * pRChild;
} BiTNode, *pBiTNode;

// 定义二叉树结构
// 二叉树只要有一个头指针即可确定，与链表定义相同
typedef pBiTNode LinkBiTree;

/*------------------------- 二叉树链式结构定义 ------------------------*/



extern void InitBiTree(LinkBiTree * T);
extern void CreatBiTree(LinkBiTree * T);

extern void PreOrderTraverse(LinkBiTree T);
extern void InOrderTraverse(LinkBiTree T);                      // 递归
extern void InOrderTraverse_stack(LinkBiTree T);                // 借助栈
extern void PostOrderTraverse(LinkBiTree T);
extern void LevelOrderTraverse(LinkBiTree T);                   // 借助队列

extern bool BiTreeIsEmpty(LinkBiTree T);

extern TElemType Root(LinkBiTree T);
extern int BiTreeDepth(LinkBiTree T);
extern TElemType Value(pBiTNode p);
extern void Assign(pBiTNode p, TElemType elem);
extern pBiTNode Point(LinkBiTree T, TElemType elem);            // 借助队列
extern TElemType Parent(LinkBiTree T, TElemType elem);          // 借助队列
extern TElemType LeftChild(LinkBiTree T, TElemType elem);       // 借助 Point()
extern TElemType RightChild(LinkBiTree T, TElemType elem);      // 借助 Point()
extern TElemType LeftSibling(LinkBiTree T, TElemType elem);     // 借助 Parent() 和 Point
extern TElemType RightSibling(LinkBiTree T, TElemType elem);    // 借助 Point()

extern void DestoryBiTree(LinkBiTree T);


#endif
  1. 链式二叉树相关函数定义：linBITree.c 文件
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
/*
 * 功能: 二叉树-二叉链表
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-09-19
 */


// 注意：非递归方式遍历尚未实现，后续补充


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

#include "linkBiTree.h"
#include "linkQueue.h"


// 初始化
// 会改变头指针的值，故采用 *pT
void InitBiTree(LinkBiTree * pT)
{
    // 构造空二叉树
    *pT = NULL;
}

// 创建二叉树
void CreatBiTree(LinkBiTree * pT)  // pT实际上是二级指针，指向根节点的指针的指针
{
    TElemType ch;
    
    scanf("%c", &ch);
    if ( Nil == ch ) {  //节点值为空
        *pT = NULL;  // *pT是指向根节点的指针
    } 
    else {  // 节点值不为空，创建根节点
       *pT = (pBiTNode)malloc(sizeof(BiTNode));
        if ( NULL == *pT ) {
            printf("内存分配失败！");
            exit(-1);
        }

        (*pT)->data = ch;
        // CreatBiTree((*pT)->pLChild);  // 这里错了！  (*pT)->pLChild仅为一级指针，而非二级指针
        // CreatBiTree((*pT)->pRChild);

        CreatBiTree(&(*pT)->pLChild);  // 要加一个取地址符&，即变为指向左子树根节点的指针的指针，二级指针
        CreatBiTree(&(*pT)->pRChild);
    }
}

// 前序遍历二叉树
// 递归实现
void PreOrderTraverse(LinkBiTree T)
{
    if ( T != NULL ) {
        printf("%c ", T->data);
        PreOrderTraverse(T->pLChild);
        PreOrderTraverse(T->pRChild);
    }
}

// 中序遍历二叉树
void InOrderTraverse(LinkBiTree T)
{
    if ( T != NULL ) {
        InOrderTraverse(T->pLChild);
        printf("%c ", T->data);
        InOrderTraverse(T->pRChild);
    }
}

// 中序遍历
// 非递归算法，利用栈实现
void InOrderTraverse_stack(LinkBiTree T)
{

}

// 后序遍历二叉树
void PostOrderTraverse(LinkBiTree T)
{
    if ( T != NULL ) {
        PostOrderTraverse(T->pLChild);
        PostOrderTraverse(T->pRChild);
        printf("%c ", T->data);
    }
}

// 层序遍历
// 借助队列实现
void LevelOrderTraverse(LinkBiTree T)
{
    LinkQueue q;
    QElemType a;

    if ( T != NULL ) {
        InitQueue(&q);  // 容易忘记初始化
        EnQueue(&q, T);
        while ( !QueueIsEmpty(&q) ) {
            DeQueue(&q, &a);               // 出队
            printf("%c ", a->data);

            if ( a->pLChild ) {
                EnQueue(&q, a->pLChild);  // 左孩子入队
            }
            if ( a->pRChild ) {
                EnQueue(&q, a->pRChild);  // 右孩子入队
            }
        }
        printf("\n");
        DestoryQueue(&q);  // 记得释放队列内存
    }
}

// 是否为空
bool BiTreeIsEmpty(LinkBiTree T)
{
    return (NULL == T);
}

// 获取根节点
TElemType Root(LinkBiTree T)
{
    if ( BiTreeIsEmpty(T) ) {
        return Nil;
    }
    else {
        return T->data;
    }
}

// 树深度
// 递归求得，好好思考一番
int BiTreeDepth(LinkBiTree T)
{
    int i, j;

    if ( NULL == T ) {
        return 0;
    }
    else {
        i = BiTreeDepth(T->pLChild);
        j = BiTreeDepth(T->pRChild);
        return i>j ? i+1 : j+1;
    }
} 

// 返回二叉树中元素值为 elem 的节点的指针
// 这个函数特别重要，后面的找孩子节点、找兄弟节点等功能都要基于该函数
// 遍历方法实现
// pBiTNode Point(LinkBiTree T, TElemType elem)
// {
//     if ( T != NULL ) {
//         if ( elem == T->data ) {
//             return T;
//         }

//         Point(T->pLChild, elem);  // 有问题，在这个递归里找到 elem 了，但是仍然会继续执行下面的 Point(T->pRChild, elem); 无法及时结束递归
//         Point(T->pRChild, elem);
//     }
// }   


// 返回二叉树中元素值为 elem 的节点的指针
// 递归问题无法解决的话，或者借助队列实现该函数，但是将自己编写的链式队列融合进来又是一个问题
pBiTNode Point(LinkBiTree T, TElemType elem)
{
    LinkQueue q;
    QElemType a;  // typedef pBiTreeNode QElemType;  已经将二叉树的节点指针作为队列元素

    if ( T != NULL ) {
        InitQueue(&q);   // 初始化队列，为头节点分配内存空间
        EnQueue(&q, T);  // 将根节点入队
        while ( !QueueIsEmpty(&q) ) {  
            DeQueue(&q, &a);  // 只要队列非空，则出队
            if ( elem == a->data ) {  
                DestoryQueue(&q);  // 结束函数前将队列内存释放，否则会造成内存泄漏
                return a;  // 找到了 elem，则返回指向其节点的指针，结束函数
            }
            else {   // 如果在根节点未找到，则继续将左右孩子节点入队
                if ( a->pLChild != NULL ) {  // 左孩子非空，入队
                    EnQueue(&q, a->pLChild);
                }
                if ( a->pRChild != NULL ) {  // 右孩子非空，入队
                    EnQueue(&q, a->pRChild);
                }
            }
            
        }
        // while() 中未找到 elem，表明二叉树中没有要找的元素
        // 那么要将队列的头节点所占空间释放掉
        DestoryQueue(&q);
    } 

    return NULL;  // 若 T 为空，则返回 NULL；或者 T 非空但是在 T 树中未找到 elem，则返回 NULL 
}


// 返回指针 p 所指向的节点的值
TElemType Value(pBiTNode p)
{
    if ( p != NULL ) {
        return p->data;
    }
    else {
        return Nil;
    }
}

// 给 p 所指向的节点赋值
void Assign(pBiTNode p, TElemType elem)
{
    if ( p != NULL ) {
        p->data = elem;
    }
    else {
        printf("节点为空，赋值失败！\n");
    }
}

// 找父节点
// 类似 Point()，只是 Parent() 返回的是其父节点的 data
TElemType Parent(LinkBiTree T, TElemType elem)
{
    LinkQueue q;
    QElemType a;

    if ( T != NULL ) {
        InitQueue(&q);
        EnQueue(&q, T);
        while ( !QueueIsEmpty(&q) ) {
            DeQueue(&q, &a);
            // if ( a->pLChild->data == elem || a->pRChild->data == elem ) {  // 这里要注意，少了左右孩子空判断
            if ( a->pLChild && a->pLChild->data == elem || a->pRChild && a->pRChild->data == elem ) {
                DestoryQueue(&q);
                return a->data;
            }
            else {
                if ( a->pLChild != NULL ) {
                    EnQueue(&q, a->pLChild);
                }
                if ( a->pRChild != NULL ) {
                    EnQueue(&q, a->pRChild);
                }
            }
        }
        DestoryQueue(&q);
    }
    return Nil;
}

// 找左孩子
// 借助 Point
TElemType LeftChild(LinkBiTree T, TElemType elem)
{
    if ( T != NULL ) {
        pBiTNode p = Point(T, elem);  // 首先找到指向该节点的指针
        if ( p != NULL && p->pLChild != NULL ) {   
            return p->pLChild->data;
        }
    }
    return Nil;
}

// 找右孩子
TElemType RightChild(LinkBiTree T, TElemType elem)
{
    if ( T != NULL ) {
        pBiTNode p = Point(T, elem);
        if ( p != NULL && p->pRChild != NULL ) {
            return p->pRChild->data;
        }
    }
    return Nil;
}

// 找左兄弟
// 借助 Parent
TElemType LeftSibling(LinkBiTree T, TElemType elem)
{
    if ( T != NULL ) {
        TElemType a = Parent(T, elem);  // 找到其父节点
        if ( a != Nil ) {  
            pBiTNode p = Point(T, a);   // 再找到父节点的指针
            if ( p->pLChild != NULL && p->pRChild != NULL && p->pRChild->data == elem) {  // 假设左右孩子的值均不相同
                return p->pLChild->data;
            }
        }
    }
    return Nil;
}

// 找右兄弟
TElemType RightSibling(LinkBiTree T, TElemType elem)
{
    if ( T != NULL ) {
        TElemType a = Parent(T, elem);
        if ( a != Nil ) {
            pBiTNode p = Point(T, a);
            if ( p->pLChild != NULL && p->pRChild != NULL && p->pLChild->data == elem) {
                return p->pRChild->data;
            }
        }
    }
    return Nil;
}

// 销毁
void DestoryBiTree(LinkBiTree T)
{
    if ( T != NULL ) {
        DestoryBiTree(T->pLChild);
        DestoryBiTree(T->pRChild);
        free(T);
        T = NULL;
    }
}
  1. 链式队列头文件：linkQueue.h 文件
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
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_

#include <stdbool.h>
#include "linkBiTree.h"


/*------------------------- 链式队列结构定义 ------------------------*/

typedef pBiTNode QElemType;  // 二叉树的节点指针作为队列元素

// 定义链式节点的数据类型
typedef struct qNode {
    QElemType data;
    struct qNode * pNext;
} QNode, *pQNode;

// 利用链式节点构造链式队列的数据类型
typedef struct linkqueue {
    pQNode pFront;
    pQNode pRear;
} LinkQueue, *pLinkQueue;

// 链式队列示意图：https://img.arctee.cn/one/202209162337604.png

/*------------------------- 链式队列结构定义 ------------------------*/



extern void InitQueue(pLinkQueue Q);
extern bool EnQueue(pLinkQueue Q, QElemType elem);
extern void Traverse(pLinkQueue Q);
extern bool QueueIsEmpty(pLinkQueue Q);
extern bool DeQueue(pLinkQueue Q, QElemType * pElem);
extern void DestoryQueue(pLinkQueue Q);
extern void ClearQueue(pLinkQueue Q);


#endif
  1. 链式队列函数实现：linBITree.c 文件
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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "linkQueue.h"


// 初始化
void InitQueue(pLinkQueue Q)
{
    // 创建头节点
    pQNode pHead = (pQNode)malloc(sizeof(QNode));
    if ( NULL == pHead ) {
        printf("内存分配失败！");
        exit(-1);
    }
    pHead->pNext = NULL;

    // 头指针、尾指针均指向头节点
    Q->pFront = Q->pRear = pHead;
}

// 入队
bool EnQueue(pLinkQueue Q, QElemType elem)
{
    // 创建新节点
    pQNode pNew = (pQNode)malloc(sizeof(QNode));
    if ( NULL == pNew ) {
        printf("内存分配失败，无法入队！");
        return false;
    }
    pNew->data = elem;
    pNew->pNext = NULL;

    // 将新节点连接到队列尾部，然后将尾指针指向新节点
    Q->pRear->pNext = pNew;
    Q->pRear = pNew;

    return true;
}

// 遍历队列
void Traverse(pLinkQueue Q)
{
    pQNode p = Q->pFront;  

    while ( p != Q->pRear ) {
        // 头指针的后驱节点才是第一个有效数据
        printf("%d ", p->pNext->data);
        p = p->pNext;
    }
    printf("\n");
}

// 是否为空
bool QueueIsEmpty(pLinkQueue Q)
{
    return (Q->pFront == Q->pRear );
}

// 出队
bool DeQueue(pLinkQueue Q, QElemType * pElem)
{
    if ( QueueIsEmpty(Q) ) {
        printf("队列为空，出队失败！");
        return false;
    }

    pQNode p = Q->pFront;

    *pElem = p->pNext->data;
    Q->pFront = p->pNext;  // 将头指针往后移动一位

    free(p);
    p = NULL;

    return true;
}

// 销毁队列
void DestoryQueue(pLinkQueue Q)
{
    pQNode p = Q->pFront;


    while( p != NULL ) {
        Q->pFront = p->pNext;
        free(p);
        p = Q->pFront;
    }
}

// 清空队列
// 保留头节点
void ClearQueue(pLinkQueue Q)
{
    DestoryQueue(Q);
    InitQueue(Q);
}