括号表示法字符串构造二叉树_6-9 括号表示法构造二叉树

原理如上图，下面的是简述：
当遇到字母的时候，直接入栈，而遇到“）”的时候出栈，其他的字符时做左右子树的标记，代码实现过程如下：

#include<iostream>
using namespace std;
#define MaxSize 100

struct BTnode {  //节点的数据类型
	char data;
	BTnode *lnode, *rnode;
};
void Create(BTnode* &root, char *str) {  //创建二叉树
	BTnode *St[MaxSize], *p = root = NULL;
	int k = 0, j = 0, top = -1;
	char ch = str[j];
	while (ch != '\0') {
		switch (ch)
		{
		case '(': St[++top] = p; k = 1; break;
		case ')': top--; break;
		case ',': k = 2; break;
		default:
			p = new BTnode;
			p->data = ch;
			p->lnode = p->rnode = NULL;
			if (root == NULL) root = p;
			else k == 1 ? St[top]->lnode = p : St[top]->rnode = p;
		}
		ch = str[++j];
	}
}
BTnode* Findnode(BTnode *root, char ch) {  //查找某个节点
	if (root == NULL) return NULL;
	if (root->data == ch) return root;
	BTnode *p = Findnode(root->lnode, ch);
	return p != NULL ? p : Findnode(root->rnode, ch);
}

void Display(BTnode *root) { //输出整棵二叉树
	if (root != NULL) printf("%c", root->data);
	if (root->lnode != NULL || root->rnode != NULL) {
		printf("(");
		if (root->lnode != NULL) Display(root->lnode);
		if (root->rnode != NULL) {
			printf(",");
			Display(root->rnode);
		}
		printf(")");
	}
}
int main() {

	BTnode *root = NULL;
	char* str = "A(B(D(,G)),C(E,F))";
	Create(root, str);
	Display(root);
	printf("\n");

	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