二叉树操作大全（C实现）_用c语言二叉树实现一个函数,对0,100对任意分数

以下代码包括：辅助栈（链栈）、辅助队列（顺序存储循环队列）、二叉树的两种先序建立、先序中序后序遍历（递归）、中序遍历非递归方法、层次遍历。注释充分，逻辑清晰，代码可读性强。

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

typedef char BiElemType;
typedef struct BTNode{
    BiElemType data;  //数据域
    struct BTNode * pLchild;
    struct BTNode * pRchild;
}BTNode, * BiTree;

//======================辅助栈的实现========================
typedef struct Node{
    BiTree data;
    struct Node * next;
}NODE, * PNODE;

typedef struct Stack{
    PNODE pTop;   //栈顶
    PNODE pBottom;//栈底
}STACK, * PSTACK;

void init_S(PSTACK pS){//链栈的初始化
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL)
    {
        printf("内存分配失败！\n");
    }
    pS->pBottom = pHead;  //初始栈顶栈底都指向头节点
    pS->pTop = pHead;
    pS->pTop->next = NULL;

}

void push(PSTACK pS, BiTree val){ //原则：先入栈后变动栈顶指针
    PNODE pnew = (PNODE)malloc(sizeof(NODE));
    pnew->data = val;
    pnew->next = pS->pTop; //将新节点接在原栈顶上方
    pS->pTop = pnew;  //栈顶指针变动至最新位置
    return;
}

void traverse(PSTACK pS){
    PNODE p = pS->pTop;  //遍历指针获取到栈顶
    while(p != pS->pBottom){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return;
}

//出栈一次，并将元素输出在val中
bool pop(PSTACK pS, BiTree * p){  //这里用到了二级指针
    if(pS->pBottom == pS->pTop){  //栈空报错
        return false;
    }
    *p = pS->pTop->data;  //保存删去的值
    PNODE q = pS->pTop;
    pS->pTop = q->next;  //移动栈顶指针
    free(q);
    return true;
}

bool is_empty(PSTACK S){
    if(S->pBottom == S->pTop){  //栈空
        return true;
    }else{
        return false;
    }
}

//======================辅助队列的实现========================
#define MAX_SIZE 6   //宏定义  数组长度为6，最多能保存5个元素

typedef struct Queue
{
    BiTree * pBase;  //数组的首地址
    int front;
    int rear;
}QUEUE;

void init_Q(QUEUE * pQ){ //初始化一个长度为6的队列
    pQ->pBase = (int *)malloc(sizeof(int) * MAX_SIZE);
    pQ->front = 0;
    pQ->rear = 0;
}

//判断队列是否为空（引入一个空单元作为牺牲）
bool is_full(QUEUE * pQ){
    if((pQ->rear + 1) % MAX_SIZE == pQ->front){
        printf("该循环队列已满！\n");
        return true;
    }
    return false;
}

bool q_empty(QUEUE * pQ){
    if(pQ->rear == pQ->front){
        return true;
    }else{
        return false;
    }
}

bool en_queue(QUEUE * pQ, PNODE val){  //入队：入队一个元素，队尾向后移动一下
    if(is_full(pQ)){
        printf("队列已满，无法添加元素！\n");
        return false;
    }else{
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear + 1) % MAX_SIZE;
        return true;
    }
}

bool de_queue(QUEUE * pQ, PNODE * val){
    if(pQ->front == pQ->rear){
        printf("该队列为空，无法出队！\n");
        return false;
    }else{
        *val = pQ->pBase[pQ->front];
        pQ->front = (pQ->front + 1) % MAX_SIZE;
        return true;
    }
}

//==============================二叉树功能实现=============================================
/*
使用二级指针的原因：
1.若要通过函数B修改函数A中的某个变量a。需要获得变量a的地址，如果
a是普通变量，需要获得一级指针。如果a是指针，需要获得二级指针。
2.root需要指向一个新插入的节点，也就是需要修改root的值。所以 应该传入指向root的地址。
3.如果仅使用一级指针，那么只能改变形参的内存，如，root = malloc(sizeof(struct TreeNode)); 
这个root和函数外的实参的内存空间不同，所以修改它并不会对实参的内存造成影响，
所以必须把它做为返回值返回去，否则函数外就没法获得这个变化的值。
*/

/*
A.先序建立二叉树（无返回值版本）
需要在main函数中定义一个根节点
注意这是个二叉树节点的指针类型;然后将这个参数
传递给一个CreateBTree函数;在该函数中递归创建二叉树
*/
void CreateBTree(BiTree * root){  //二级指针(BiTree本身就是指针)
    char c;
    scanf("%c", &c);  //接受一个字符
    if(c == '#'){  //遇到#
        *root = NULL;  //将此节点置为空
    }else{  //从函数外部接受root(二级指针的形式)并在函数内部进行修改
        (*root) = (BiTree)malloc(sizeof(BTNode));  //创建一个新的节点
        (*root)->data = c;
        CreateBTree(&(*root)->pLchild);   //沿左子树继续创建
        CreateBTree(&(*root)->pRchild);   //沿右子树继续创建
    }
    
}

/*
B.先序建立二叉树（有返回值版）
可以直接在CreatBiTree函数中创建二叉树，并返回二叉树的根指针
*/
BiTree CreateBTree2(){
    char c;
    BiTree root = NULL;  //在函数内部创建root
    scanf("%c", &c);  //接受一个字符
    if(c == '#'){  //遇到#
        root = NULL;  //将此节点置为空
        return NULL; //必须return NULL
    }else{
        root = (BiTree)malloc(sizeof(BTNode));  //创建一个新的节点
        root->data = c;
        root->pLchild = CreateBTree2();   //沿左子树继续创建
        root->pRchild = CreateBTree2();   //沿右子树继续创建
        return root;
    }
}

//先序遍历二叉树
void PreOrderTraverse(BiTree root){
    if(root != NULL){
        printf("%c", root->data);
        PreOrderTraverse(root->pLchild);
        PreOrderTraverse(root->pRchild);
    }
}

//中序遍历
void InOrderTraverse(BiTree root){
    if(root != NULL){
        InOrderTraverse(root->pLchild);
        printf("%c", root->data);
        InOrderTraverse(root->pRchild);
    }
}

//中序遍历非递归方法（借助栈完成）
void InOrderTraverse2(BiTree root){
    STACK S;  //STACK等价于 struct Stack
    init_S(&S);
    BiTree t = root;
    while(!is_empty(&S) || t != NULL){
        if(t){  //若当前节点不为空则将其入栈,继续向左子树遍历
            push(&S, t);  //入栈的是整个树节点，并非字符
            t = t->pLchild;
        }else{  //若左子树为空，出栈并访问，然后访问其右子树
            pop(&S, &t);
            printf("%c", t->data);
            t = t->pRchild;
        }
    }
}

//后序遍历
void PostOrderTraverse(BiTree root){
    if(root != NULL){
        PostOrderTraverse(root->pLchild);
        PostOrderTraverse(root->pRchild);
        printf("%c", root->data);
    }
}

//层次遍历
void LevelOrder(BiTree root){
    QUEUE Q;  //实例化一个队列
    init_Q(&Q);
    en_queue(&Q, root);  //将根节点入队
    BiTree val;  //保存出队元素
    while(!q_empty(&Q)){
        de_queue(&Q, &val);
        printf("%c", val->data);
        if(val->pLchild != NULL){
            en_queue(&Q, val->pLchild);
        }
        if(val->pRchild != NULL){
            en_queue(&Q, val->pRchild);
        }
    }
}

int main(){
    //A.二级指针构造方式
    // BiTree root = NULL;
    // CreateBTree(&root);
    // PreOrderTraverse(root);
    //B.一级指针构造方式
    BiTree root = CreateBTree2();
    printf("先序遍历二叉树\n");
    PreOrderTraverse(root);
    printf("\n");
    printf("中序遍历二叉树\n");
    InOrderTraverse(root);
    printf("\n");
    printf("后序遍历二叉树\n");
    PostOrderTraverse(root);
    printf("\n");
    printf("非递归中序遍历二叉树\n");
    InOrderTraverse2(root);
    printf("\n层次遍历二叉树\n");
    LevelOrder(root);
    return 0;
}
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

程序运行：