2012.02.16
数据结构学习笔记（1）利用链式存储结构和递归构建二叉树
书上是用循环实现，我写了用递归实现，代码如下：
1
#include <stdio.h>
2
#include <malloc.h>
3
#define
MaxSize 100
4
typedef
char
ElemType;
5
typedef
struct
node
6
{
7
ElemType data;
//
数据元素
8
struct
node *lchild;
//
指向左孩子结点
9
struct
node *rchild;
//
指向右孩子结点
10
} BTNode;
11
12
void
CreateBTNode(BTNode * &b,
char
*str)
13
{
14
BTNode *St[MaxSize],*p=NULL;
15
int
top=-
1
,k,j=
0
;
16
char
ch;
17
b=NULL;
//
建立的二叉树初始时为空
18
ch=str[j];
19
while
(ch!=
'
\0
'
)
//
str未扫描完时循环
20
{
21
switch
(ch)
22
{
23
case
'
(
'
:
24
top++;St[top]=p;k=
1
;
25
break
;
//
为左孩子结点
26
case
'
)
'
:
27
top--;
28
break
;
29
case
'
,
'
:
30
k=
2
;
31
break
;
//
为孩子结点右结点
32
default
:p=(BTNode *)malloc(
sizeof
(BTNode));
33
p->data=ch;p->lchild=p->rchild=NULL;
34
if
(b==NULL)
//
*p为二叉树的根结点
35
b=p;
36
else
//
已建立二叉树根结点
37
{
38
switch
(k)
39
{
40
case
1
:St[top]->lchild=p;
break
;
41
case
2
:St[top]->rchild=p;
break
;
42
}
43
}
44
}
45
j++;
46
ch=str[j];
47
}
48
}
49
50
BTNode * CreateBTNode2(
char
* &str)
//
风筝写的
51
{
52
BTNode * root=NULL, *p;
53
int
hasson=
0
;
//
判断此结点有没有子结点
54
char
ch = *str;
55
root = (BTNode *)malloc(
sizeof
(BTNode));
56
root->data=
'
\0
'
;
57
root->lchild = root->rchild = NULL;
58
while
(ch !=
'
\0
'
)
59
{
60
switch
(ch)
61
{
62
case
'
(
'
:
//
如果是'('：说明有子结点
63
hasson=
1
;
64
str++;
65
p = CreateBTNode2(str);
66
if
(p->data !=
'
\0
'
)
//
如果子结点不为空，则添加，否则释放
67
{
68
root->lchild = p;
69
}
70
else
71
{
72
free(p);
73
}
74
break
;
75
case
'
)
'
:
//
如果是')'：说明结点结束，如果当前结点有子结点，
76
//
则')'属于此结点，str++跳到下一个，否则')'属于父结点，应由父结点进行操作
77
if
(hasson ==
1
)
78
{
79
str++;
80
}
81
return
root;
82
case
'
,
'
:
//
如果是','：说明有右子结点，如果当前结点有子结点，
83
//
则','属于此结点，否则','属于父结点，应由父结点进行操作
84
if
(hasson ==
1
)
85
{
86
str++;
87
p = CreateBTNode2(str);
88
if
(p->data !=
'
\0
'
)
89
{
90
root->rchild = p;
91
}
92
else
93
{
94
free(p);
95
}
96
}
97
else
98
{
99
return
root;
100
}
101
break
;
102
default
:
//
是一个新节点，需要递归取值
103
{
104
str++;
105
root->data = ch;
106
}
107
}
108
ch = *str;
109
}
110
return
root;
111
}
112
113
//
以下主函数用做调试
114
void
main()
115
{
116
BTNode *b,*p=NULL;
117
char
* str =
"
A(B(D,),C(,F))
"
;
118
CreateBTNode(b,str);
119
p = CreateBTNode2(str);
120
int
tmp;
121
scanf(
"
%d
"
, tmp);
122
}
编了好久，3个多小时，⊙﹏⊙b汗。。。
特记录在此，以便以后查看。
