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)

隨筆檔案(100)

向高手學習

cai0715
RyanWang
wingyiu

搜索

積分與排名

積分 - 29226
排名 - 669

閱讀排行榜

評論排行榜

二叉樹線索化

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

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 閱讀(636) 評論(0) 編輯收藏引用所屬分類: 數據結構

只有注冊用戶登錄后才能發表評論。


相關文章: 矩陣轉置_十字鏈表二叉樹線索化

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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