wyiu
Follow.
C++博客
::
首頁
::
新隨筆
::
聯系
::
聚合
::
管理
posts - 100, comments - 15, trackbacks - 0
<
2009年5月
>
日
一
二
三
四
五
六
26
27
28
29
30
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
1
2
3
4
5
6
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(1)
給我留言
查看公開留言
查看私人留言
隨筆分類
(84)
Design Pattern(1)
POJ(67)
常用模板和函數(3)
數據結構(2)
數值分析(3)
算法(8)
隨筆檔案
(100)
2010年10月 (8)
2010年3月 (11)
2009年10月 (16)
2009年9月 (1)
2009年8月 (1)
2009年7月 (20)
2009年5月 (16)
2009年4月 (27)
向高手學習
cai0715
RyanWang
wingyiu
搜索
積分與排名
積分 - 28280
排名 - 675
最新評論
1.?re: poj 3368 rmq(st)
有錯誤~~
index[] 可能會以負數為下標~
--tongjiantao
2.?re: pku poj 3009
@BOAT
行列搞錯了吧?
--yaoyaozii
3.?re: pku poj 3009
@ww
郁悶啊。。我怎么也是3 啊。。。郁悶!!!
--BOAT
4.?re: pku poj 3009 [未登錄]
excit就是這個游戲
--X
5.?re: pku2777
這個只能用c++交嗎?用G++交的結果很神奇喔,居然CE。。
--share4
閱讀排行榜
1.?POJ 線段樹題(2000)
2.?pku poj 3009 (1015)
3.?矩陣轉置_十字鏈表(960)
4.?全主元高斯消元法(806)
5.?關于“逆序數”[轉](777)
評論排行榜
1.?pku poj 3009 (10)
2.?pku 1019 poj(2)
3.?pku2777(1)
4.?pku 2151(1)
5.?poj 3368 rmq(st)(1)
二叉樹線索化
輸入二叉樹
先序
,建樹,然后
中序線索化
,遍歷輸出
1
#include
<
iostream
>
2
using
namespace
std;
3
4
enum
PointerTag
5
{
6
Link,Thread
//
枚舉值Link和Thread分別為0,1
7
}
;
8
9
struct
BiThrNode
//
線索二叉樹的結點類型
10
{
11
char
data;
12
PointerTag LTag;
//
左標志
13
PointerTag RTag;
//
右標志
14
BiThrNode
*
lchild;
//
左孩子指針
15
BiThrNode
*
rchild;
//
右孩子指針
16
}
;
17
18
typedef BiThrNode
*
BiThrTree;
19
BiThrNode
*
pre
=
NULL;
//
全局量
20
21
void
InOrderThreading(BiThrTree
&
Thrt,BiThrTree T);
//
線索化
22
void
InThreading(BiThrTree p);
//
中序遍歷線索化
23
bool
PreOrderCreatBiTree(BiThrTree
&
T);
//
先序建立樹
24
void
InOrderTraverse_Thr(BiThrTree T);
//
中序遍歷線索樹
25
26
int
main()
27
{
28
BiThrTree T,Thrt;
29
printf(
"
輸入先序序列('#'表示空節點)建立二叉樹:\n
"
);
30
PreOrderCreatBiTree(T);
//
先序建立樹
31
InOrderThreading(Thrt,T);
//
中序線索化
32
printf(
"
中序線索化,中序遍歷得中綴式:\n
"
);
33
InOrderTraverse_Thr(Thrt);
//
中序遍歷線索樹
34
printf(
"
\n
"
);
35
return
0
;
36
}
37
38
void
InOrderThreading(BiThrTree
&
Thrt,BiThrTree T)
39
{
40
Thrt
=
new
BiThrNode;
41
Thrt
->
LTag
=
Link;
42
Thrt
->
RTag
=
Thread;
43
Thrt
->
rchild
=
Thrt;
44
if
(
!
T) Thrt
->
lchild
=
Thrt;
45
else
{
46
Thrt
->
lchild
=
T;
47
pre
=
Thrt;
48
InThreading(T);
49
pre
->
rchild
=
Thrt;
50
pre
->
RTag
=
Thread;
51
Thrt
->
rchild
=
pre;
52
}
53
}
54
55
void
InThreading(BiThrTree p)
56
{
57
if
(p)
58
{
59
InThreading(p
->
lchild);
60
if
(
!
p
->
lchild)
{ p
->
LTag
=
Thread; p
->
lchild
=
pre;}
61
if
(
!
pre
->
rchild)
{ pre
->
RTag
=
Thread; pre
->
rchild
=
p; }
62
pre
=
p;
63
InThreading(p
->
rchild);
64
}
65
}
66
67
bool
PreOrderCreatBiTree(BiThrTree
&
T)
68
{
//
該節點非空返回true,雙親節點對應標志Link,空時返回false,雙親節點對應標志應為Thread
69
char
ch;
70
scanf(
"
%c
"
,
&
ch);
71
if
(ch
==
'
#
'
)
72
{
73
T
=
NULL;
74
return
false
;
75
}
else
{
76
T
=
new
BiThrNode;
77
T
->
data
=
ch;
78
if
(PreOrderCreatBiTree(T
->
lchild)) T
->
LTag
=
Link;
//
左孩子存在則左標志為Link
79
else
T
->
LTag
=
Thread;
80
if
(PreOrderCreatBiTree(T
->
rchild)) T
->
RTag
=
Link;
//
右孩子存在則右標志為Link
81
else
T
->
RTag
=
Thread;
82
}
83
return
true
;
84
}
85
86
87
void
InOrderTraverse_Thr(BiThrTree T)
88
{
89
BiThrNode
*
p;
90
p
=
T
->
lchild;
91
while
(p
!=
T)
92
{
93
while
(p
->
LTag
==
Link) p
=
p
->
lchild;
94
printf(
"
%c
"
,p
->
data);
95
while
(p
->
RTag
==
Thread
&&
p
->
rchild
!=
T)
//
if(p->RTag==Thread && p->rchild!=T)
96
{
97
p
=
p
->
rchild;
98
printf(
"
%c
"
,p
->
data);
99
}
100
p
=
p
->
rchild;
101
}
102
}
posted on 2009-05-13 17:00
wyiu
閱讀(626)
評論(0)
編輯
收藏
引用
所屬分類:
數據結構
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
相關文章:
矩陣轉置_十字鏈表
二叉樹線索化
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Powered by:
C++博客
Copyright ©2025 wyiu
久久免费视频网站
|
国产麻豆精品久久一二三
|
欧美激情精品久久久久久久
|
久久伊人五月天论坛
|
无码国内精品久久人妻
|
久久99免费视频
|
久久婷婷国产剧情内射白浆
|
99国产欧美久久久精品蜜芽
|
亚洲欧美国产日韩综合久久
|
亚洲AV无码一区东京热久久
|
日韩精品久久久肉伦网站
|
亚洲精品高清久久
|
亚洲精品乱码久久久久久按摩
|
99久久综合狠狠综合久久
|
人人狠狠综合久久88成人
|
久久有码中文字幕
|
中文字幕亚洲综合久久2
|
人妻无码αv中文字幕久久琪琪布
|
欧美午夜精品久久久久久浪潮
|
成人久久精品一区二区三区
|
久久婷婷五月综合成人D啪
|
久久精品成人影院
|
久久夜色精品国产亚洲
|
麻豆AV一区二区三区久久
|
久久亚洲精品无码aⅴ大香
|
久久精品无码一区二区三区日韩
|
九九久久精品国产
|
精品国产福利久久久
|
久久精品www人人爽人人
|
无码精品久久久天天影视
|
四虎国产精品成人免费久久
|
久久最新免费视频
|
中文字幕精品久久久久人妻
|
一级做a爰片久久毛片免费陪
|
欧美成a人片免费看久久
|
免费一级欧美大片久久网
|
亚州日韩精品专区久久久
|
亚洲国产成人精品久久久国产成人一区二区三区综
|
亚洲人成无码久久电影网站
|
伊人 久久 精品
|
精品熟女少妇av免费久久
|