Sekyoro的博客小屋

数据结构noj_3

发表于 更新于 分类于
本文字数： 20k 阅读时长 ≈ 18 分钟

数据结构noj_3

差不多看看就行了

21.

image-20210612110800240

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max 2000
typedef struct Snode{
    int tag;   //标签
    char elem;
    int prio;  //优先级
} Snode; //字符节点

typedef struct MyString{
    Snode data[max];
    int length;
}MyString;  //存储字符串

typedef struct TNode{
    Snode data;
    struct TNode *lchild,*rchild;
}TNode,BiTree,*PTNode;   //二叉树

void Clear(MyString *S)//去除外层多余的括号
{
    int level = 0;
    if(S->data[0].elem == '(' && S->data[S->length - 1].elem == ')'){
        for(int i = 0;i < S->length-1;i++)
        {
            if(S->data[i].elem == '(')
            level++;
            else if(S->data[i].elem == ')')
            level--;

            if(level == 0)
            return;
        }

        for(int i = 1; i < S->length-1;i++)
        {
            S->data[i-1] = S->data[i];
        }
        S->length = S->length - 2;
    }
}

void InitString(MyString *S){
    char c[max];
    int len,baselevel = 0;

    scanf("%s",c);
    len = strlen(c);
    for(int i = 0;i < len;i++)
    {
        S->data[i].elem = c[i];
		if (c[i] == '+' || c[i] == '-')
		{
			S->data[i].tag = 1;
			S->data[i].prio = baselevel + 1;
		}
		else if (c[i] == '*' || c[i] == '/')
		{
			S->data[i].tag = 1;
			S->data[i].prio = baselevel + 2;
		}
		else if (c[i] == '(')
		{
			S->data[i].tag = 0;
			baselevel = baselevel + 2;
		}
		else if (c[i] == ')')
		{
			S->data[i].tag = 0;
			baselevel = baselevel - 2;
		}
		else
		{
			S->data[i].tag = 0;
		}
    }
    S->length = len;
}

int FindMid(MyString *S){ //返回level最小符号的下标
    int pos = 0,min = max;//min 当前最小的level，pos记录下标
    for(int i = 0;i < S->length;i++)
    {
        if(S->data[i].prio <= min && S->data[i].tag == 1)// 优先级相同时，先算前面的，所以将后面的作为中间值划分。
        {
            min = S->data[i].prio;
            pos = i;
        }
    }
    return pos;
}

PTNode CreatTree(MyString *S){
    MyString left,right;
    PTNode T;
    T = (PTNode)malloc(sizeof(TNode));
    int midpos,len;
    len = S->length;
    
    if(len == 1)
    {
        T->data = S->data[len-1];
        T->lchild = NULL;
        T->rchild = NULL;
    }
    else if(len > 1)
    {
        midpos = FindMid(S);
        left.length = midpos;
        for(int i = 0;i < midpos;i++)
        {
            left.data[i] = S->data[i];
        }
        right.length = S->length - midpos - 1;
        for(int i = 0;i < right.length;i++)
        {
            right.data[i] = S->data[i+midpos+1];
        }
        Clear(&left);
        Clear(&right);
        T->data = S->data[midpos];
        T->lchild = (TNode*)malloc(sizeof(TNode));
        T->rchild = (TNode*)malloc(sizeof(TNode));

        T->lchild = CreatTree(&left);
        T->rchild = CreatTree(&right);
    }
    return T;
}

void Last(BiTree* T){
    if(T->lchild == NULL && T->rchild == NULL)
    {
        printf("%c",T->data.elem);
    }
    else
    {
        Last(T->lchild);
        Last(T->rchild);
        printf("%c",T->data.elem);
    }
    
}

int main(){
    MyString s;
    s.length = 0;
    PTNode T;

    InitString(&s);
    Clear(&s);
    T = CreatTree(&s);
    Last(T);
    printf("\n");

    return 0;
}

22.

image-20210612110908312

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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define YES 1
#define NO 0
#define MAX_VERTEX_NUM 100

typedef struct Seqlist
{
    int value;
    struct Seqlist *next;
} Seqlist, *pList;

typedef struct ArcNode
{
    int adj; //权值数据

} ArcNode;

typedef struct AdjMatrix
{
    int vertex[MAX_VERTEX_NUM];                   //顶点向量
    ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵,权值
    int vexnum, arcnum;                           //顶点数与弧数
} AdjMatrix;

//初始化有向图权值
AdjMatrix initial();

void dijkstra(AdjMatrix, int, int[], pList *);

//初始化路径 从v0开始到vi的最短路径序列
//初值为 若v0到vi有弧,则为v0,vi
pList initial_path();

int member(int, pList);
void addtail(pList, int);
// pList addtail(pList,int);
void output(int[], AdjMatrix);

int main(void)
{
    AdjMatrix adj;
    pList s;
    //dist存储目前已经找到的v0到vi当前最短路径长度
    int dist[MAX_VERTEX_NUM];
    //path,若v0到vi有路径则存储,否则为空
    pList *path = (pList *)malloc(sizeof(pList));
    adj = initial();
    dijkstra(adj, 0, dist, path);
    output(dist,adj);
}
AdjMatrix initial()
{
    AdjMatrix adj;
    int vexnum, arcnum;

    scanf("%d %d", &vexnum, &arcnum);
    adj.vexnum = vexnum;
    adj.arcnum = arcnum;

    // for (int i = 0; i < vexnum; i++)
    //     scanf("%d", &adj.vertex[i]); //输入每个节点信息

    for (int i = 0; i < vexnum; i++)
        adj.vertex[i] = i + 1;

    int i, j, weight;

    for (int ix = 0; ix < vexnum; ix++)
    {
        for (int jx = 0; jx < vexnum; jx++)
        {
            if (ix != jx)
                adj.arcs[ix][jx].adj = INT_MAX;
            else
                adj.arcs[ix][jx].adj = 0;
        }
    }

    while (arcnum--)
    {
        scanf("%d %d %d", &i, &j, &weight);
        for (int ix = 0; ix < vexnum; ix++)
        {
            if (adj.vertex[ix] == i)
            {
                for (int jx = 0; jx < vexnum; jx++)
                {
                    if (adj.vertex[jx] == j)
                    {
                        adj.arcs[ix][jx].adj = weight;
                    }
                }
            }
        }
    }
    return adj;
}

void dijkstra(AdjMatrix adj, int v0, int dist[], pList path[])
{
    pList s;
    //初始化 dist 为长度最短的一条的最短路径
    //path为存在路径的序列
    for (int i = 0; i < adj.vexnum; i++)
    {
        path[i] = initial_path();
        dist[i] = adj.arcs[v0][i].adj;
        if (dist[i] < INT_MAX)
        {

            addtail(path[i], adj.vertex[i]);
        }
    }
    s = initial_path();
    // addtail(s, adj.vertex[v0]);
    int k ;
    for (int t = 1; t <= adj.vexnum - 1; t++) //计算v0从第二个到最后一个结点最短路径
    {
        int min = INT_MAX;
        for (int j = 1; j < adj.vexnum; j++)
        {
            if (!member(adj.vertex[j], s) && dist[j] < min) //j不在s中且存在路径
            {
                k = j;
                min = dist[j];
            }
        }

        // if(min == INT_MAX)
        // continue;
        addtail(s, adj.vertex[k]);
        // if(dist[])
        // if ()
        //     printf("1 %d %d\n", k + 1, (dist[k] == INT_MAX) ? -1 : dist[k]);

        for (int i = 0; i < adj.vexnum; i++) //修正dist[i]
        {
            if (!member(adj.vertex[i], s) && adj.arcs[k][i].adj < INT_MAX && (dist[k] + adj.arcs[k][i].adj < dist[i]))

            {
                dist[i] = dist[k] + adj.arcs[k][i].adj;
                path[i] = path[k];
                addtail(path[i], adj.vertex[i]);
            }
        }
    }
}
pList initial_path()
{
    pList l = (pList)malloc(sizeof(Seqlist));
    l->value = 0;
    l->next = NULL;
    return l;
}
void addtail(pList path, int vertex)
{

    // if(path->value == 0)
    // {
    //     path->value = vertex;
    //     path->next = NULL;
    //     return;
    // }
    pList c = (pList)malloc(sizeof(Seqlist));
    c->value = vertex;
    c->next = NULL;
    while (path->next != NULL)
        path = path->next;
    path->next = c;
}
// pList addtail(pList path,int vertex)
// {
//     pList c = (pList)malloc(sizeof(Seqlist));
//     pList l = path;
//     c->value = vertex;
//     c->next = NULL;
//     while(l)
//     l = l->next;
//     l = c;
//     return path;
// }
int member(int vertex, pList path)
{
    while (path)
    {
        if (vertex == path->value)
        {
            return YES;
        }
        path = path->next;
    }
    return NO;
}
void output(int dist[], AdjMatrix adj)
{
    // int temp;
    // for(int i = 1;i<adj.vexnum-1;i++)
    // {
    //     for(int j = 1;j<adj.vexnum - i -1;j++)
    //     {
    //         if(dist[j]>dist[j+1])
    //             {
    //                     temp = dist[j];
    //                     dist[j] = dist[j+1];
    //                     dist[j+1] = temp;
    //             }
    //     }
    // }
    // for(int i = 1;i<adj.vexnum;i++)
    // {
    //     printf("1 %d %d\n",i+1,(dist[i]==INT_MAX)?(-1):dist[i]);
    // }
    // int min = INT_MAX;
    // int max = INT_MAX;
    // int mark = 1;
    // for(int t = 1;t<=adj.vexnum;t++)
    // {
    // for(int i = 1;i<adj.vexnum;i++)
    // {
    //     min = INT_MAX;
    //     if(dist[i]<min&&dist[i]!=0&&dist[i]>=dist[mark])
    //     {
    //         min = dist[i];
    //         mark = i;
    //     }

    // }
    // if(min!=INT_MAX)
    // {
    // printf("1 %d %d\n",adj.vertex[mark],min);
    // dist[mark] = 0;
    // }
    // else
    // printf("1 %d %d\n",adj.vertex[mark],-1);
    // }
    int min;
    int flag;
    int i;
    for (int t = 1; t < adj.vexnum; t++)
    {
        min = INT_MAX;
        for ( i = 1; i < adj.vexnum; i++)
        {
            if (dist[i] < min && dist[i] != 0)
            {
                flag = i;
                min = dist[i];
            }
            // if (dist[i] == INT_MAX)
            // {
            //     flag = i;
            // }
        }
        if (min != INT_MAX)
        {
            printf("1 %d %d\n", adj.vertex[flag], min);
            dist[flag] = 0;
        }
        else
            printf("1 %d %d\n", adj.vertex[i-1], -1);
    }
}

23.

image-20210612110943431

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
#include<stdio.h>
#define N 11

typedef struct 
{
    int key;
    int flag;
    /* data */
}Recordtype;

typedef Recordtype hashtable[N];

int hash(int);
void create(hashtable,int[],int);

int main(void)
{
    int data[8] = {22,41,53,46,30,13,1,67};
    int s = 0;
    hashtable ht;
    create(ht,data,8);
    for(int i = 0;i<N;i++)
        s+=ht[i].flag;
    printf("%d\n",s/8);


}
int hash(int k)
{
    return (3*k)%11;//返回位置

}

void create(hashtable ht,int data[],int len)
{
    for(int i = 0;i<N;i++)
    {
        ht[i].key = 0;
        ht[i].flag = 0;
    }
    int flag = 1;
    int h;
    for(int i = 0;i<len;i++)
    {
        h = hash(data[i]);
        if(ht[h].key==0)
        {
            ht[h].key = data[i];
            ht[h].flag = 1;
        }
        else
        {
            while(ht[h].key!=0)
            {
                h++;
                h = h%11;
                flag++;
            }
            ht[h].key = data[i];
            ht[h].flag = flag;
            flag = 1;
        }
    }

}

24.

image-20210612111013055

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
//24.c

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

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int val;
}Bstnode,*Bstree;

int is_bstree(Bstree);
Bstree create();


int main(void)
{
    Bstree t = (Bstree)malloc(sizeof(Bstnode));
    t = create();    
    if(is_bstree(t))
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

Bstree create()
{
    int elem;
    Bstree p;
    scanf("%d",&elem);
    if(elem!=-1)
    {
       p = (Bstree)malloc(sizeof(Bstnode));
       p->val = elem;
        p->lchild = create();
        p->rchild = create();
    }
    return p;
}

int is_bstree(Bstree t)
{
    if(t==NULL)
    return 1;
        if(t->lchild&&t->rchild)
        {
            if(t->val<t->lchild->val||t->val>t->rchild->val)
                return 0;
            else
                return is_bstree(t->lchild)&&is_bstree(t->rchild);
        }
        else
            if(t->lchild)
            {
                if(t->val<t->lchild->val)
                    return 0;
                else
                    return is_bstree(t->lchild);
            }
         else
            if(t->rchild)
            {
                if(t->val>t->rchild->val)
                    return 0;
                else
                    return is_bstree(t->rchild);
            } 
        return 1;
}
// #include <stdio.h>
// #include <stdlib.h>

// #define FALSE 0
// #define TRUE 1

// typedef struct BinTreeNode{
//     int data;
//     struct BinTreeNode *left;
//     struct BinTreeNode *right;
// }BinTreeNode;

// BinTreeNode *CreatBinTree(){//先序递归输入
// 	int elem;
// 	BinTreeNode *p;
// 	scanf("%d",&elem);
// 	if(elem==-1){
//         return NULL;
// 	}
// 	else{
// 		p = (BinTreeNode*)malloc(sizeof(BinTreeNode));
// 		p->data = elem;
// 		p->left = CreatBinTree();
// 		p->right = CreatBinTree();
// 		return p;
// 	}
// }

// int IsBinarySortTree(BinTreeNode *T){//判断是否为排序树，即(T->left->data)<(T->data)<(T->right->data)
//     if(!T){
//         return TRUE;
//     }
//     else if(T->left&&T->right){
//         if(T->data<T->left->data||T->data>T->right->data){
//             return FALSE;
//         }
//         else{
//             return (IsBinarySortTree(T->left)&&IsBinarySortTree(T->right));
//         }
//     }
//     else if(T->left){
//         if(T->data>T->left->data){
//             return FALSE;
//         }
//         else{
//             return (IsBinarySortTree(T->left));
//         }
//     }
//     else if(T->right){
//         if(T->data<T->right->data){
//             return FALSE;
//         }
//         else{
//             return (IsBinarySortTree(T->right));
//         }
//     }
//     return TRUE;
// }

// void Output(BinTreeNode *T){//中递归输出
//     if(T!=NULL){
//         Output(T->left);
//         printf("%d ",T->data);
//         Output(T->right);
//     }
// }

// int main(){
//     //其实我一般习惯是先给存储结构申请空间，用void函数对存储结构进行操作的，但是这个题在读取输入字符前无法确定是否需要申请空间，于是我选择在函数内申请空间
//     //因为我们无法将指针变量的本身传入函数，因此直接将指针传入函数可能会造成无效的处理
//     //因为在C语言中，所有非数组形式的数据实参均以传值形式调用（对实参做一备份并传递给调用的函数，函数不能修改作为实参实际变量的值，而只能修改传递给它的那份备份）
//     //此时我们通常有如下两种办法：
//     //1.通过return返回，例如 BT *T; T = creat(); ( BT *creat() )
//     //2.使用二级指针，例如 BT *T; creat(&T); ( void creat(BT **T) )
//     BinTreeNode *T;
//     T = CreatBinTree();
//     if(IsBinarySortTree(T)){
//         printf("yes");
//     }
//     else{
//         printf("no");
//     }
// }

25.

image-20210612111120529

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
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int val;
}Bstnode,*Bstree;

Bstree create();//创建  可以利用插入创建 也可以直接创建  
//这里说是先序输入，所以直接创建
void search(Bstree,int,int);//查找
void insert(Bstree*,int);//插入
void delBst(Bstree*,int);//删除
void output(Bstree);//输出  中序

int main(void)
{
    Bstree t = (Bstree)malloc(sizeof(Bstnode));
    t = create();
    int min,max;
    scanf("%d %d",&min,&max);
    search(t,min,max);
    printf("\n");
    int insert_val;
    scanf("%d",&insert_val);
    insert(&t,insert_val);
    output(t);
    printf("\n");
    int del_val;
    scanf("%d",&del_val);
    delBst(&t,del_val);
    output(t);
    printf("\n");
    return 0;
    
}

Bstree create()
{
    Bstree p;
    int n;
    scanf("%d",&n);
    if(n!=-1)
    {
        p = (Bstree)malloc(sizeof(Bstnode));
        p->val = n;
        p->lchild = create();
        p->rchild = create();
    }
    return p;
}

void search(Bstree t,int min,int max)
{
    if(t==NULL) 
        return;
    search(t->lchild,min,max);
    if(t->val>=min&&t->val<=max)
        printf("%d ",t->val);
   search(t->rchild,min,max);
}

void insert(Bstree *t,int num)
{
    Bstree s;
    if(!t)
    {
        s = malloc(sizeof(Bstnode));
        s->val = num;
        s->lchild = s->rchild = NULL;
        *t = s;//注意这里要改变值,所以用了指针
        //通过地址改变值
    }
    else
    if(num<(*t)->val)
    {
        insert(&(*t)->lchild,num);
    }
    else
        insert(&(*t)->rchild,num);
}
void delBst(Bstree *t,int val)//删除
{
                //找到节点
    if((*t)->val==val)
        {
                if((*t)->lchild==NULL&&(*t)->rchild==NULL)//叶子结点
                {
                    (*t) = NULL;
                }

               else
                if((*t)->rchild==NULL)//只有左子树,将左子树置为父节点的左子树
                {
                    (*t) = (*t)->lchild;
                }
               else
                 if((*t)->lchild==NULL)//只有右子树,将右子树置为父节点的右子树
                {
                    (*t) = (*t)->rchild;
                }
                else//待删除节点 左右子树都有
                //找到中序遍历下的上一个点,右子树置为其右子树
                //左子树依旧为父节点左子树
                {
                    Bstree s;
                    s = (*t)->lchild;
                    while(s->rchild)
                    {
                        s = s->rchild;//找到左子树的最右分支叶子节点，将其右节点子树置为右子树
                    }
                    s->rchild = (*t)->rchild;
                    (*t) = (*t)->lchild;
                }
        }
    else
    if(val<(*t)->val)
    {
        delBst(&(*t)->lchild,val);
    }
    else
        delBst(&(*t)->lchild,val);
}

void output(Bstree t)//输出  中序
{
    if(t==NULL)
    return;
    // if(t->lchild)
        output(t->lchild);
        printf("%d ",t->val);
        output(t->rchild);
}
// #include<stdio.h>
// #include<stdlib.h>

// typedef struct BiTNode {
// 	int data;
// 	struct BiTNode* left;
// 	struct BiTNode* right;
// }BiTNode, * BiTree;

// BiTree CreateBiTree();   //创建二叉树
// void SearchAndPrint(BiTree T, int a, int b);//要求1：输出大于a、小于b的关键字
// void InsertBi(BiTree* T, int insert);//插入一个关键字并输出
// void DeleteBi(BiTree* T, int dele);  //删除结点
// void MidPrint(BiTree T); //中序输出

// int main()
// {
// 	BiTree T;
// 	T = CreateBiTree();
// 	int a, b, insert, dele;
// 	scanf("%d%d%d%d", &a, &b, &insert, &dele);
// 	SearchAndPrint(T, a, b);//要求1
// 	printf("\n");
// 	InsertBi(&T, insert);//插入
// 	MidPrint(T);//中序输出
// 	printf("\n");
// 	DeleteBi(&T, insert);//删除insert
// 	DeleteBi(&T, dele);//删除dele
// 	MidPrint(T);//中序输出
// 	return 0;
// }

// BiTree CreateBiTree()
// {   //创建二叉树
// 	int data;
// 	scanf("%d", &data);
// 	if (data == -1) {
// 		return NULL;
// 	}
// 	BiTree tmp;
// 	tmp = (BiTree)malloc(sizeof(BiTNode));
// 	if (!tmp) {
// 		return NULL;
// 	}
// 	tmp->data = data;
// 	tmp->left = CreateBiTree();
// 	tmp->right = CreateBiTree();
// 	return tmp;
// }

// void SearchAndPrint(BiTree T, int a, int b)
// {   //要求1：输出大于a、小于b的关键字
// 	//用中序输出
// 	if (!T) {
// 		return;
// 	}
// 	SearchAndPrint(T->left, a, b);
// 	if (T->data > a && T->data < b) {
// 		printf("%d ", T->data);
// 	}
// 	SearchAndPrint(T->right, a, b);
// }

// void InsertBi(BiTree* T, int insert)
// {   //插入结点
// 	if (!(*T)) {
// 		BiTree tmp;
// 		tmp = (BiTree)malloc(sizeof(BiTNode));
// 		tmp->data = insert;
// 		tmp->left = NULL;
// 		tmp->right = NULL;
// 		*T = tmp;
// 		return;
// 	}
// 	if (insert < (*T)->data) {
// 		InsertBi(&(*T)->left, insert);
// 	}
// 	if (insert > (*T)->data) {
// 		InsertBi(&(*T)->right, insert);
// 	}
// }

// void DeleteBi(BiTree* T, int dele)
// {   //删除结点
// 	if (!(*T)) {
// 		return;
// 	}
// 	DeleteBi(&(*T)->left, dele);
// 	if ((*T)->data == dele) {
// 		if (!(*T)->left) {
// 			//左子树为空
// 			(*T) = (*T)->right;
// 		}
// 		else {//左子树非空
// 			BiTree tmp = (*T)->left;
// 			while (tmp->right) {
// 				tmp = tmp->right;
// 			}
// 			tmp->right = (*T)->right;
// 			(*T) = (*T)->left;
// 		}
// 		return;
// 	}
// 	DeleteBi(&(*T)->right, dele);
// }

// void MidPrint(BiTree T)
// {   //中序输出
// 	if (!T) {
// 		return;
// 	}
// 	MidPrint(T->left);
// 	printf("%d ", T->data);
// 	MidPrint(T->right);
// }

26.

image-20210612111201004

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
//二叉树的合并
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int key;
}Bstnode,*Bstree;

Bstree create();
void combine_tree(Bstree*,Bstree*);
void insert(Bstree*,int);

void output(Bstree);
int main(void)
{
    Bstree t1,t2;
    t1 = create();
    t2 = create();
    combine_tree(&t1,&t2);
    output(t1);
    return 0;

}
Bstree create()
{
    Bstree p;
    int n;
    scanf("%d",&n);
    if(n!=-1)
    {
        p = (Bstree)malloc(sizeof(Bstnode));
        p->key = n;
        p->lchild = create();
        p->rchild = create();
    }
    return p;
}

//中序遍历T2，将T2各个元素插入T1中
void combine_tree(Bstree* m,Bstree* n)
{
    if(*n)
    {
        combine_tree(&(*m),&(*n)->lchild);
        insert(&(*m),(*n)->key);
        combine_tree(&(*m),&(*n)->rchild);
    }

}


void insert(Bstree *t,int num)
{
    Bstree s;
    if(!t)
    {
        s = malloc(sizeof(Bstnode));
        s->key = num;
        s->lchild = s->rchild = NULL;
        *t = s;//注意这里要改变值,所以用了指针
        //通过地址改变值
    }
    else
    if(num<(*t)->key)
    {
        insert(&(*t)->lchild,num);
    }
    else
        insert(&(*t)->rchild,num);
}

void output(Bstree t)//输出  中序
{
    if(t==NULL)
    return;
    // if(t->lchild)
        output(t->lchild);
        printf("%d ",t->key);
        output(t->rchild);
}
// #include<stdio.h>
// #include<stdlib.h>

// typedef struct BiTNode {
// 	int data;
// 	struct BiTNode* left;
// 	struct BiTNode* right;
// }BiTNode, * BiTree;

// BiTree CreateBiTree();   //创建二叉树
// void InsertBi(BiTree* T, int insert);//插入节点
// void CombineBi(BiTree T1, BiTree T2);//合并二叉树T1，T2
// void MidPrint(BiTree T); //中序输出

// int main()
// {
// 	BiTree T1, T2;
// 	T1 = CreateBiTree();
// 	T2 = CreateBiTree();
// 	CombineBi(T1, T2);
// 	MidPrint(T1);
// 	return 0;
// }

// BiTree CreateBiTree()
// {   //创建二叉树
// 	int data;
// 	scanf("%d", &data);
// 	if (data == -1) {
// 		return NULL;
// 	}
// 	BiTree tmp;
// 	tmp = (BiTree)malloc(sizeof(BiTNode));
// 	if (!tmp) {
// 		return NULL;
// 	}
// 	tmp->data = data;
// 	tmp->left = CreateBiTree();
// 	tmp->right = CreateBiTree();
// 	return tmp;
// }

// void InsertBi(BiTree* T, int insert)
// {   //插入结点
// 	if (!(*T)) {
// 		BiTree tmp;
// 		tmp = (BiTree)malloc(sizeof(BiTNode));
// 		tmp->data = insert;
// 		tmp->left = NULL;
// 		tmp->right = NULL;
// 		*T = tmp;
// 		return;
// 	}
// 	if (insert < (*T)->data) {
// 		InsertBi(&(*T)->left, insert);
// 	}
// 	if (insert > (*T)->data) {
// 		InsertBi(&(*T)->right, insert);
// 	}
// }

// void CombineBi(BiTree T1, BiTree T2)
// {   //合并二叉树T1，T2
// 	if (!T2) {
// 		return;
// 	}
// 	CombineBi(T1, T2->left);
// 	InsertBi(&T1, T2->data);
// 	CombineBi(T1, T2->right);
// }

// void MidPrint(BiTree T)
// {   //中序输出
// 	if (!T) {
// 		return;
// 	}
// 	MidPrint(T->left);
// 	printf("%d ", T->data);
// 	MidPrint(T->right);
// }
-------------本文结束感谢您的阅读-------------
相关文章
感谢阅读.

欢迎关注我的其它发布渠道