2012.02.16
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（1）利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和遞歸構(gòu)建二叉樹(shù)
書(shū)上是用循環(huán)實(shí)現(xiàn)，我寫(xiě)了用遞歸實(shí)現(xiàn)，代碼如下：
1
#include <stdio.h>
2
#include <malloc.h>
3
#define
MaxSize 100
4
typedef
char
ElemType;
5
typedef
struct
node
6
{
7
ElemType data;
//
數(shù)據(jù)元素
8
struct
node *lchild;
//
指向左孩子結(jié)點(diǎn)
9
struct
node *rchild;
//
指向右孩子結(jié)點(diǎn)
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;
//
建立的二叉樹(shù)初始時(shí)為空
18
ch=str[j];
19
while
(ch!=
'
\0
'
)
//
str未掃描完時(shí)循環(huán)
20
{
21
switch
(ch)
22
{
23
case
'
(
'
:
24
top++;St[top]=p;k=
1
;
25
break
;
//
為左孩子結(jié)點(diǎn)
26
case
'
)
'
:
27
top--;
28
break
;
29
case
'
,
'
:
30
k=
2
;
31
break
;
//
為孩子結(jié)點(diǎn)右結(jié)點(diǎn)
32
default
:p=(BTNode *)malloc(
sizeof
(BTNode));
33
p->data=ch;p->lchild=p->rchild=NULL;
34
if
(b==NULL)
//
*p為二叉樹(shù)的根結(jié)點(diǎn)
35
b=p;
36
else
//
已建立二叉樹(shù)根結(jié)點(diǎn)
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)
//
風(fēng)箏寫(xiě)的
51
{
52
BTNode * root=NULL, *p;
53
int
hasson=
0
;
//
判斷此結(jié)點(diǎn)有沒(méi)有子結(jié)點(diǎn)
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
'
(
'
:
//
如果是'('：說(shuō)明有子結(jié)點(diǎn)
63
hasson=
1
;
64
str++;
65
p = CreateBTNode2(str);
66
if
(p->data !=
'
\0
'
)
//
如果子結(jié)點(diǎn)不為空，則添加，否則釋放
67
{
68
root->lchild = p;
69
}
70
else
71
{
72
free(p);
73
}
74
break
;
75
case
'
)
'
:
//
如果是')'：說(shuō)明結(jié)點(diǎn)結(jié)束，如果當(dāng)前結(jié)點(diǎn)有子結(jié)點(diǎn)，
76
//
則')'屬于此結(jié)點(diǎn)，str++跳到下一個(gè)，否則')'屬于父結(jié)點(diǎn)，應(yīng)由父結(jié)點(diǎn)進(jìn)行操作
77
if
(hasson ==
1
)
78
{
79
str++;
80
}
81
return
root;
82
case
'
,
'
:
//
如果是','：說(shuō)明有右子結(jié)點(diǎn)，如果當(dāng)前結(jié)點(diǎn)有子結(jié)點(diǎn)，
83
//
則','屬于此結(jié)點(diǎn)，否則','屬于父結(jié)點(diǎn)，應(yīng)由父結(jié)點(diǎn)進(jìn)行操作
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
:
//
是一個(gè)新節(jié)點(diǎn)，需要遞歸取值
103
{
104
str++;
105
root->data = ch;
106
}
107
}
108
ch = *str;
109
}
110
return
root;
111
}
112
113
//
以下主函數(shù)用做調(diào)試
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個(gè)多小時(shí)，⊙﹏⊙b汗。。。
特記錄在此，以便以后查看。
風(fēng)箏數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（1）利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和遞歸構(gòu)建二叉樹(shù)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
