wyiu
Follow.

C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理

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)

隨筆分類(lèi)(84)

隨筆檔案(100)

向高手學(xué)習(xí)

cai0715
RyanWang
wingyiu

搜索

積分與排名

積分 - 29226
排名 - 669

閱讀排行榜

評(píng)論排行榜

二叉樹(shù)線索化

輸入二叉樹(shù)先序，建樹(shù)，然后中序線索化，遍歷輸出

1

#include<iostream>
2

using namespace std;
3

4

enum PointerTag
5

{
6

Link,Thread //枚舉值Link和Thread分別為0，1
7

};
8

9

struct BiThrNode //線索二叉樹(shù)的結(jié)點(diǎn)類(lèi)型
10

{
11

char data;
12

PointerTag LTag; //左標(biāo)志
13

PointerTag RTag; //右標(biāo)志
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);//先序建立樹(shù)
24

void InOrderTraverse_Thr(BiThrTree T);//中序遍歷線索樹(shù)
25

26

int main()
27

{
28

BiThrTree T,Thrt;
29

printf("輸入先序序列('#'表示空節(jié)點(diǎn))建立二叉樹(shù)：\n");
30

PreOrderCreatBiTree(T);//先序建立樹(shù)
31

InOrderThreading(Thrt,T);//中序線索化
32

printf("中序線索化，中序遍歷得中綴式：\n");
33

InOrderTraverse_Thr(Thrt);//中序遍歷線索樹(shù)
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

{//該節(jié)點(diǎn)非空返回true，雙親節(jié)點(diǎn)對(duì)應(yīng)標(biāo)志Link，空時(shí)返回false，雙親節(jié)點(diǎn)對(duì)應(yīng)標(biāo)志應(yīng)為T(mén)hread

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; //左孩子存在則左標(biāo)志為L(zhǎng)ink
79

else T->LTag=Thread;
80

if(PreOrderCreatBiTree(T->rchild)) T->RTag=Link; //右孩子存在則右標(biāo)志為L(zhǎng)ink
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 閱讀(636) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 矩陣轉(zhuǎn)置_十字鏈表二叉樹(shù)線索化

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品