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汗。。。
特記錄在此，以便以后查看。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
