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
久久久久人妻精品一区
|
国内精品综合久久久40p
|
久久久www免费人成精品
|
亚洲精品乱码久久久久久按摩
|
国产亚洲精久久久久久无码AV
|
久久伊人五月丁香狠狠色
|
97久久超碰国产精品2021
|
久久久久国产日韩精品网站
|
精品久久久久中文字幕日本
|
久久无码AV一区二区三区
|
色综合合久久天天综合绕视看
|
久久亚洲精品成人无码网站
|
久久久久亚洲av无码专区
|
久久笫一福利免费导航
|
久久久久亚洲精品天堂久久久久久
|
精品999久久久久久中文字幕
|
久久精品国产2020
|
亚洲午夜久久久久久久久久
|
国产精品久久久久免费a∨
|
狠狠色丁香婷婷久久综合
|
看全色黄大色大片免费久久久
|
国产精久久一区二区三区
|
日韩精品无码久久久久久
|
久久精品中文字幕久久
|
久久久噜噜噜久久
|
日韩精品无码久久久久久
|
久久99精品久久只有精品
|
色欲综合久久中文字幕网
|
国产精品久久久久影院色
|
精品久久久久久无码中文字幕
|
亚洲狠狠婷婷综合久久蜜芽
|
久久国产视屏
|
久久99国产精品久久99
|
亚洲精品成人久久久
|
久久国产乱子伦精品免费午夜
|
亚洲精品无码久久一线
|
欧洲国产伦久久久久久久
|
精品乱码久久久久久夜夜嗨
|
久久久老熟女一区二区三区
|
久久久久久久久波多野高潮
|
香蕉99久久国产综合精品宅男自
|