二叉树的孩子兄弟表示法_用孩子兄弟表示法表示树

初学者。如果有误请指正，欢迎联系QQ2684162190初学者。

#include<stdio.h>
#include<stdlib.h>
#define MAX_TREE_SIZE 100
typedef struct Node
{
	char date;
	struct Node *lchild,*rchild;
}BiTNode,*BiTree;

	/*根据二叉树的括号表示法（字符串str)建立二叉链表:
	*若ch=‘(‘，则将前面刚创建的结点作为双亲结点进栈，并置k=1,表示其后建立的结点将作为该结点的左孩子；
	*若ch=‘)’，表示栈中结点的左右孩子结点处理完毕，退栈；
	*若ch=‘,’，表示其后创建的结点为右孩子结点；
	*其他，表示要创建一个结点，并根据k值建立它与栈中结点之间的联系。若k=1，表示该结点是栈中结点的左孩子；若k=2，表示该结点是栈中结点的右孩子。如此循环直到str处理完毕。
    
    *算法中使用一个栈st保存双亲结点，top为栈指针，k指定其后处理的结点是栈中结点（双亲）的左孩子(k=1)还是右孩子(k=2)。
	*/
	
	//用栈建立链表。可按照先序，中序后序，建立树 
void CreatBiTree(BiTree &bt)
{
	BiTree st[MAX_TREE_SIZE],p=NULL;
	int top = -1;
	int k,j=0;
	/*
	*			A
	*		B		D
	*		  C   E   F
	**/
	char str[] = "A(B(,C),D(E,C))\0";
	char ch;
	ch = str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
			case '(':
				st[top++] = p;
				k = 1;
				break;
			case ')':
				top--;
				break;
			case ',':
				p = (BiTree)malloc(sizeof(BiTNode));
				p->date = ch;
				p->lchild = p->rchild = NULL;
				if(bt == NULL)
					bt = p;
				else
				{
					switch(k)
					{
						case 1:
							st[top]->lchild = p;
							break;
						case 2:
							st[top]->rchild = p;
							break; 
					}
				}//end of else
		}//end of switch 
		j++;
		ch = str[j];
	}//end of while
}
//先序建立树 
void CreatBiTree1(BiTree bt)
{
	char c;
	scanf("%d",&c);
	if(c == '#')
		bt = NULL;
	else
	{
		if(!(bt = (BiTree)malloc(sizeof(BiTNode))))
			exit(0);
		bt->date = c;
		CreatBiTree1(bt->lchild);
		CreatBiTree1(bt->rchild);
	}
}
//中序建立树 
void CreatBiTree2(BiTree bt)
{
	char c;
	scanf("%d",&c);
	if(c == '#')
		bt = NULL;
	else
	{
		CreatBiTree1(bt->lchild);
		if(!(bt = (BiTree)malloc(sizeof(BiTNode))))
			exit(0);
		bt->date = c;
		CreatBiTree1(bt->rchild);
	}
}
//中序建立树 
void CreatBiTree3(BiTree bt)
{
	char c;
	scanf("%d",&c);
	if(c == '#')
		bt = NULL;
	else
	{
		CreatBiTree1(bt->rchild);
		CreatBiTree1(bt->lchild);
		if(!(bt = (BiTree)malloc(sizeof(BiTNode))))
			exit(0);
		bt->date = c;

	}
}

int main()
{
	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