C语言用括号表示法创建二叉树然后中序输出_给出一棵二叉树的括号表示法,本题要求实现2个函数,根据给出的括号表示法创建该二

​
首先，在用括号表示法创建二叉树之前，我们要先了解二叉树怎么用括号表示法表示，下面我们用两颗二叉树来了解一下：

树1：用括号表示法表示为A(B(D,E),C(F))

树2:用括号表示法表示为1(2(4,5),3(6))

用括号表示法创建二叉树的核心思路：
‘(’ 表示把双亲节点存入栈，然后开辟一个新节点链接在双亲节点的左孩子上
‘,’ 表示开辟一个新节点链接在双亲节点的右孩子上
‘)’ 表示双亲节点链接结束，把双亲节点取出栈
以树1为例，其运行结果如下：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"stack.h"
#define N 50 //二叉树括号表示法的最大长度
typedef char BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
void BTreeInit(BTNode* b)//初始化二叉树
{
	b->left = NULL;
	b->right = NULL;
	b->data = 0;
}
//使用括号表示法输入二叉树并转化为二叉树的链式存储结构
BTreeCreat(BTNode** root, int* pi, char* a)
{
	if (root == NULL)return;
	ST st;//创建一个栈
	QueueInit(&st);//初始化栈
	int k = 1;//k用来判断节点是在左子树还是右子树，当k为1时在左子树，当k为2时在右子树
	(*root)->data = a[(*pi)++];//把根节点1存进去
	BTNode* newroot = *root;//newroof表示新节点的双亲结点
	while (a[(*pi)])
	{
		if (a[*pi] == '(')
		{
			StackPush(&st, newroot);//把双亲节点插入栈
			(*pi)++;
			k = 1;
		}
		if (a[*pi] == ',')
		{
			(*pi)++;
			k = 2;
		}
		if (a[*pi] == ')')
		{
			(*pi)++;
			StackPop(&st);//把双亲节点拿出栈
			continue;
		}
		newroot = (BTNode*)malloc(sizeof(BTNode));//创建一个新节点
		newroot->left = NULL;
		newroot->right = NULL;
		newroot->data = a[*pi];//把数据存进去
		if (k == 1)
		{
			StackTop(&st)->left = newroot;//把新节点链接在双亲节点的左孩子上
		}
		if (k == 2)
		{
			StackTop(&st)->right = newroot;//把新节点链接在双亲节点的右孩子上
		}

		(*pi)++;
	}
	StackDestroy(&st);//销毁栈
}
int main()
{
	BTNode* b= (BTNode*)malloc(sizeof(BTNode));
	char a[N];
	int i = 0;
	printf("input a[N]:");
	scanf("%s", a);
	BTreeInit(b);
	BTreeCreat(&b,&i,a);
	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

下面是栈的实现
stack.h

#pragma once
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
struct BinaryTreeNode;
typedef struct BinaryTreeNode* SLDataType;
typedef struct Stack {
	SLDataType* a;
	int top;//栈顶
	int capacity;//容量
}ST;
void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);//销毁
void StackPush(ST* ps, SLDataType x);//插入
void StackPop(ST* ps);//删除
SLDataType StackTop(ST* ps);//栈顶值
int StackSize(ST* ps);//栈的大小
bool StackEmpty(ST* ps);//判断栈是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

stack.c

#include"stack.h"
void StackInit(ST* ps)//对栈进行初始化
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackPush(ST* ps, SLDataType x)//栈的插入
{
	assert(ps);
	if (ps->top == ps->capacity)//扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)//删除
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
SLDataType StackTop(ST* ps)//查找栈顶
{
	assert(ps);
	return ps -> a[ps->top-1];
}
int StackSize(ST* ps)//栈的大小
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
	return ps->top == 0;
}
void StackDestroy(ST* ps)//栈的销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 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