《數(shù)據(jù)結(jié)構(gòu)用C語言描述》第六篇.jsp

第六章樹和二叉樹樹的概念和基本術(shù)語二叉樹二叉樹遍歷二叉樹的計數(shù)樹與森林哈夫曼樹樹的概念和基本術(shù)語樹的定義樹是由n

(n 0)個結(jié)點的有限集合。如果n

=

0，稱為空樹；如果n

>

0，則有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)；當(dāng)n>1，除根以外的其它結(jié)點劃分為m

(m>0)個互不相交的有限集T1,T2

,…,Tm，其中每個集合本身又是一棵樹，并且稱為

根的子樹(SubTree)。ABKL例如A只有根結(jié)點的樹C

DE

F

G

H

I

JM有13個結(jié)點的樹其中：A是根；其余結(jié)點分成三個互不相交的子集，

T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹樹的基本術(shù)語1層2層4層3層height=

4DMAB

CE

F

G

H

I

JK

L·

結(jié)點·

結(jié)點的度·

葉結(jié)點·

分支結(jié)點·

子女

·

祖先·

雙親

·

子孫·

兄弟

·

結(jié)點層次·

樹的深度·

樹的度·

森林二叉樹(Binary

Tree)定義五種形態(tài)一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。LLRR特點每個結(jié)點至多只有兩棵子樹（二叉樹中不存在度大于2的結(jié)點）在二叉樹的第i

層上至多有2i－1個結(jié)點。(i1)[證明用歸納法]證明：當(dāng)i=1時，只有根結(jié)點，2

i-1=20=1。假設(shè)對所有j，i>j

1，命題成立，即第j層上至多有2

j-1

個結(jié)點。由歸納假設(shè)第i-1層上至多有2i－2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2*

2i－2=2

i-1。性質(zhì)性質(zhì)1性質(zhì)2

深度為k

的二叉樹至多有

2

k-1個結(jié)點(k 1)。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為＝20

+

21

+

…

+

2

k-1

=

2

k-1＝性質(zhì)3

對任何一棵二叉樹T,

如果其葉結(jié)點數(shù)為n0,

度為2的結(jié)點數(shù)為n2,則n0＝n2＋1.證明：若度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，n

=

n0

+

n1

+

n2

e

=

2n2

+

n1

=

n

-

1因此，有

2n2

+

n1

=

n0

+

n1

+

n2

-

1n2

=

n0

-

1

n0

=

n2

+

1兩種特殊形態(tài)的二叉樹62定義1

滿二叉樹(Full

Binary

Tree)一棵深度為k且有2

k-1個結(jié)點的二叉樹稱為滿二叉樹。175438

9

10

11

12

13

14

15滿二叉樹2154367216543非完全二叉樹定義2

完全二叉樹(Complete

Binary

Tree)若設(shè)二叉樹的高度為h，則共有h層。除第h

層外，其它各層(0

h-1)

的結(jié)點數(shù)都達(dá)到最大個數(shù)，第h

層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。62175438 9

10

11

12完全二叉樹0)個結(jié)點的完全二叉樹＋1性質(zhì)4

具有n

(n的深度為

log2(n)證明：設(shè)完全二叉樹的深度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義有n

<

2h2h－1

-1<n 2h-1或2h－1取對數(shù)h－1<log2nh，又h是整數(shù)，因此有h

=

log2(n)

＋1性質(zhì)5

如將一棵有n個結(jié)點的完全二叉樹自頂向

下，同一層自左向右連續(xù)給結(jié)點編號1,2,…,n，則有以下關(guān)系：若i=1,則i無雙親若i

>

0,

則i

的雙親為 i

/2若2*i<=n,則i的左子女為2*i，若2*i+1<=n,則i的右子女為2*i+1■若結(jié)點編號i為奇數(shù)，且i!=1,則左兄弟結(jié)點i-1.■若結(jié)點編號i為偶數(shù)，且小于n,則右兄弟結(jié)點為i+1.■結(jié)點i

所在層次為

log2(i+1)182345679

10二叉樹的存儲結(jié)構(gòu)1

2

3

4

0

5

6

7

8

0

0

910一般二叉樹的順序表示8

9

101

2

3

4

5

6

7

8

910完全二叉樹的順序表示1236547

8

9·順序表示12

34

5

6

7190·鏈表表示datalChildrChild二叉鏈表lChild

data

rChild含兩個指針域的結(jié)點結(jié)構(gòu)lChild

data

parent

rChild含三個指針域的結(jié)點結(jié)構(gòu)parentdatalChildrChild三叉鏈表二叉樹鏈表表示的示例BBBCCC

DDDFErootArootArootAE

F二叉樹E

F二叉鏈表三叉鏈表三叉鏈表的靜態(tài)結(jié)構(gòu)ABC

DE

Frootdataparentlchildrchi0A-11-11B0232C1-1-13D1454

E5

F33-1-1-1-1typedefchar

datatype;//結(jié)點數(shù)據(jù)類型//結(jié)點定義typedef

struct

node

{datatype

data;struct

node

*

lChild,

*

rchild;}

bitree;typedef

bitree

*

bitree;//根指針二叉鏈表的定義介紹按完全二叉樹的層次順序，依次輸入結(jié)點信息建立二叉樹的算法。算法的基本思想：1、依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點。2、若新結(jié)點是第一個結(jié)點，則令其為根結(jié)點；否則作為孩子連接到其雙親結(jié)點上。3、重復(fù)上述過程，至到輸入結(jié)束信息為止。二叉樹的生成為此，設(shè)置一個指針類型的數(shù)組隊列，保存已輸入結(jié)點的地址。1、先輸入的結(jié)點的孩子必定比后輸入的結(jié)點的孩子先進(jìn)隊列，因此可利用隊頭指針front指向當(dāng)前必須與其孩子結(jié)點建立連接的雙親結(jié)點，利用隊尾指針

rear指向當(dāng)前輸入的結(jié)點。2、若rear為偶數(shù)，作為左孩子與雙親連接，否則作為右孩子與雙親連接。3、若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須連接。4、若雙親結(jié)點與其兩個孩子連接完畢，則做出隊操作，使頭指針指向下一個等待連接的雙親結(jié)點。bitree

*Q[maxsize];bitree

*CREATREE(

){

char

ch

;

int front

, rear

;bitree

*root

,

*s

;root

=

null

; front

=

1

;

rear

=

0

;ch

=

getchar(

)

;while

(

ch

!=

‘

#

’

){

s

=

null

;if

(

ch

!=

‘

@

’

){

s

=

malloc(sizeof(bitree));s.data

=

ch

;

s.lchild

=

null

;s,rchild

=rear

+

+

; Q[rear]

=

s

;if

(rear

==

1

)

root

=

s

;else{

if

(

s

&&

Q[front]

)if

(rear%2==0

)

Q[front].lchild

=

s

;else

Q[front].rchild

=

s

;front

+

+

;if

(

rear%2==1

)}ch

=

getchar

(

)

;}return

root

;}二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。設(shè)訪問根結(jié)點記作D

遍歷根的左子樹記作L遍歷根的右子樹記作R則可能的遍歷次序有前序

DLR中序

LDR后序

LRDDLR中序遍歷(Inorder

Traversal)--/*·

中序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；+訪問根結(jié)點(D)；中序遍歷右子樹(R)。ab遍歷結(jié)果a

+

b

*

c

-

d

-

e

/

fcdef·中序遍歷二叉樹的遞歸算法voidInOrder

(

bitree

*t){if

(

t

!=

NULL

){InOrder

(

t->lchild

);printf(“\t%c\n”,

t->data);InOrder

(

t->rchild

);}}否則訪問根結(jié)點(D)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果-

+

a

*

b

-

c

d

/

ef前序遍歷(Preorder

Traversal)·

前序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；--/+*abcdef·前序遍歷二叉樹的遞歸算法void

PreOrder

(

bitree

*t

){if

(

t

!=

NULL

){printf(“\t%c\n”,t->data);PreOrder

(

t->lchild

);PreOrder

(

t->rchild

);}}后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(D)。遍歷結(jié)果a

b

c

d

-

*

+

e

f

/

-后序遍歷(PostorderTraversal)·

后序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則--/+abcde*

f·后序遍歷二叉樹的遞歸算法：void

PostOrder

(

bitree

*

t

){if

(

t

!=

NULL

){PostOrder

(

t->lchild

);PostOrder

(

t->rchild

);printf(“\t%c\n”,t->data);}}return1

+

Count

(

T->lchild

)+

Count

(

T->rchild

);}1.

計算二叉樹結(jié)點個數(shù)(遞歸算法)int

Count

(

bitree

*T

){if

(

T

==

NULL

)

return

0;elseint

Leaf_Count(Bitree

*T){//求二叉樹中葉子結(jié)點的數(shù)目if(!T)

return

0;

//空樹沒有葉子else

if(!T->lchild&&!T->rchild)return

1;

//葉子結(jié)點else

returnLeaf_Count(T.lchild)+Leaf_Count(T.rchild//左子樹的葉子數(shù)加上右子樹的葉子數(shù)}2.

求二叉樹中葉子結(jié)點的個數(shù)int

Height

(

bitree

*

T

){

int

m,

n

;if

(

T

==

NULL

)

return

-1;else{

m

=

Height

(

T->lchild

);n

=

Height

(

T->rchild

);return

(m

>

n)

?

m+1

:

n+1;}}3.

求二叉樹高度(遞歸算法)4.

復(fù)制二叉樹(遞歸算法)int

Copy(

bitree

*

T

){

if

(

T

==

NULL

)

return

-1;bitree

*

temp;Temp->data=T->data;Temp->

lchild

=

Copy(

T->lchild

);Temp->

rchild

=Copy(T->rchild

);return

temp;}5.

判斷二叉樹等價(遞歸算法)int

Equal(

bitree

*a,

bitree

*b){

if

(

a

==

NULL

&&

b

==

NULL

)return

1

;if

(

a

!==

NULL

&&

b

!==

NULL&&

a->data==b->data&&

equal(

a->lchild,

b->lchild)&&

equal(

a->rchild,

b->rchild)

)return

1;else

return

0;//a和b的子樹不等同}中序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)baabcdedaa

b入棧ab退棧訪問d入棧ad退棧訪問ce

退棧訪問棧空a退棧訪問ecc

e

入棧c

退棧訪問void

InOrder

(

bitree

*T

){ stack*S;

SETNULL(

S

);

//遞歸工作棧bitree

*p

=

T;

//初始化while

(

p

!=

NULL

||

!Empty(S)

){

if(

p

!=

NULL

){

Push(S,

p);

p

=

p->lchild;

}if

(

!Empty(S)

){

Pop(S,

p);//棧非空//退棧//訪問根printf(“%c\n”,

p->data

);p

=

p->rchild;}//if}//whilereturn

ok;}abcde前序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)bcdeadccc訪問訪問退棧退棧訪問abdce進(jìn)棧進(jìn)棧訪問訪問左進(jìn)cddc空左進(jìn)左進(jìn)左進(jìn)左進(jìn)退棧b空空e結(jié)束void

PreOrder(

bitree

*T

){

stack

*S;

SETNULL(S);//遞歸工作棧bitree

*

p

=

T;

Push

(S,

NULL);while

(

p

!=

NULL

){

printf

(“%c\n”,

p->data

);if

(

p->rchild

!=

NULL

)Push

(

S,

p->rchild

);if

(p->lchild

!=

NULL

)p

=

p->lchild;else

Pop(

S,

p

);}}a//進(jìn)左子樹bcde·后序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)后序遍歷時使用的棧的結(jié)點定義typedef

struct

{bitree

*ptr;//結(jié)點指針enum

tag{L,R};

//該結(jié)點退棧標(biāo)記}

StackNode;

ptr

tag{L,R}根結(jié)點的tag

=

L，表示從左子樹退出,

訪問右子樹。tag

=

R, 表示從右子樹退出,

訪問根?！oid

PostOrder

(

BinTree

T

)

{stack

S;

InitStack(&S);

StackNode

w;bitree

*

p

=

T;do

{while

(

p

!=

NULL

)

{//向左子樹走w.ptr

=

p;

w.tag

=

L;

Push

(&S,w);p

=

p->lchild;}int

continue=1;

//繼續(xù)循環(huán)標(biāo)記while

(

continue

&&

!StackEmpty(&S)

)

{Pop

(&S,

w);

p

=

w.ptr;switch

(

w.tag

)

{

//判斷棧頂tag標(biāo)記case

L

:

w.tag

=

R;

Push

(&S,

w);continue

=

0;p

=

p->rchild;

break;case

R

:

cout

<<p->data

<<

endl;}}}

while

(

p

!=

NULL

||

!StackEmpty(&S)

);cout

<<

endl;}練習(xí):交換二叉樹各結(jié)點的左、右子樹(遞歸算法)void

unknown

(

bitree

*

T

){

bitree

*p

=

T,

*temp;if

(

p

!=

NULL

){

temp

=

p->lchild;p->lchild

=

p->rchild;p->rchild

=

temp;unknown

(p->lchild

);unknown

(

p->rchild

);}}·不用棧消去遞歸算法中的第二個遞歸語句void

unknown

(

bitree

*

T

){

bitree

*p

=

T,

*temp;while

(

p

!=

NULL

){

temp

=

p->lchild;p->lchild

=

p->rchild;p->rchild

=

temp;unknown

(p->lchild

);p

=

p->rchild;}}使用棧消去遞歸算法中的兩個遞歸語句void

unknown(bitree

*

T){

bitree

*p,

*temp;stack

*S;

SETNULL

(S);if

(

T

!=

NULL

){

push(S,

T);while

(

!

Empty(S)

){Pop(S,p);//棧中退出一個結(jié)點

temp=p->lchild;//交換子女

p->lchild=p->rchild;p->rchild

=

temp;if

(

p->rchild

!=

NULL

)push

(S,

p->rchild

);if

(p->lchild

!=

NULL

)push

(S,p->lchild

);}}}ltag=0,ltag=1,rtag=0,rtag=1,lchild為左子女指針lchild為前驅(qū)線索rchild為右子女指針rchild為后繼指針lchildrchilddataltagrtag·線索二叉樹(Threaded

Binary

Tree)結(jié)點結(jié)構(gòu)下面給出線索鏈表的形式說明：typedef

int

datatype

;typedef

struct

node{

int

ltag

,

rtag

;datatype

data

;struct

node

*lchild

,

*rchild

;}bithptr

;bithptr

*pre

;通過中序遍歷建立中序線索化二叉樹bithptr

*pre

=null;INTHREAD

(

bithptr

*p

){

if

(

p

!=

NULL

)//左子樹線索化{

INTHREAD

(

p->lchild

);if

(p->lchild

==

NULL

){

p->lchild

=

pre;p->ltag

=

1;}

//建立當(dāng)前結(jié)點的前驅(qū)線索if

(

pre

!=

NULL

&&pre->rchild

==

NULL

)

{pre->rchild

=

p;pre->rtag

=

1;}

//建立前驅(qū)結(jié)點的后繼線索pre

=

p;//前驅(qū)跟上當(dāng)前指針//遞歸,INTHREAD

(

p->rchild);右子樹線索化}}?樹的存儲結(jié)構(gòu)·雙親表示：以一組連續(xù)空間存儲樹的結(jié)點，同時在結(jié)點中附設(shè)一個指針，存放雙親結(jié)點在鏈表中的位置。樹與森林BACDdata0

1

2

3

4A

B

C

D

E5

6F

GEFGparent-1

0

0

0

113用雙親表示實現(xiàn)的樹定義#define

MaxSize//最大結(jié)點個數(shù)typedef

char

datatype;//結(jié)點數(shù)據(jù)//樹結(jié)點定義typedef

struct

{datatype

data;int

parent;}

TreeNode;typedef

TreeNode

Tree[MaxSize];

//樹AB

C

DE

F

G·左子女-右兄弟表示法第一種解決方案

等數(shù)量的鏈域data

child1

child2

child3childdABCDEFG空鏈域n(k-1)+1個結(jié)點結(jié)構(gòu)data

firstChild

nextSiblingAB

C

DE

F

G空鏈域n+1個第二種解決方案

樹的左子女-右兄弟表示（二叉鏈表表示）BCDGFEA用左子女-右兄弟表示實現(xiàn)的樹定義typedef

char

datatype;typedef

struct

node

{datatype

data;struct

node

*firstChild,

*nextSibling;}

TreeNode;typedef

TreeNode

*

Tree;(1)樹轉(zhuǎn)化成二叉樹的簡單方法保留結(jié)點與第一個孩子之間的連線，去掉其余連線；①在同胞兄弟之間加連線；②③順時針旋轉(zhuǎn)45度。以根結(jié)點為軸；左孩子不再旋轉(zhuǎn)。森林轉(zhuǎn)化成二叉樹①將森林中的每棵樹轉(zhuǎn)換成對應(yīng)的二叉樹；②將森林中已經(jīng)轉(zhuǎn)換成的二叉樹的各個根視為兄弟，各兄弟之間自第一棵樹根到最后一棵樹根之間加連線；③以第一棵樹的根為軸，順時針旋轉(zhuǎn)45度。T1

T2

T3A

F

HB

C

D

G

I

JE

KT1ABCDEGT2

T3F

HIKJABCEDHIFG3

棵樹的森林各棵樹的二叉樹表示K

J森林的二叉樹表示?森林與二叉樹的轉(zhuǎn)換樹的二叉樹表示:?樹的遍歷深度優(yōu)先遍歷先根次序遍歷后根次序遍歷AB

C

DE

F

GABCEDGF·深度優(yōu)先遍歷訪問根結(jié)點依次先根遍歷根的各棵 子樹樹先根遍歷ABEFCDG對應(yīng)二叉樹前序遍歷ABEFCDG

樹的先根遍歷結(jié)果與其對應(yīng)二叉樹表示的前序遍歷結(jié)果相同

樹的先根遍歷可以借助對應(yīng)二叉樹的前序遍歷算法實現(xiàn)ABCEDGF·樹的先根次序遍歷當(dāng)樹非空時

樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實現(xiàn)·樹的后根次序遍歷:當(dāng)樹非空時依次后根遍歷根的各棵BA子樹EC訪問根結(jié)點樹后根遍歷EFBCGDAFD對應(yīng)二叉樹中序遍歷EFBCGDAG樹的后根遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同二叉樹的計數(shù)由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：HBDFEKCGA

AEKCG

BH

DFKCGEKCGABH

DFEKCGABHFDEABHFDEABHFDCKG如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。5

81

12

6

2

63

4

7

3

7

89

4

5

9固定前序排列,選擇所有可能的中序排列,可以構(gòu)造多少種不同的二叉樹？例如, 有

3

個數(shù)據(jù){

1,

2,

3

}，可得

5

種不同的二叉樹。它們的前序排列均為123，中序序列可能是

321

，

231，

213，

132，123.31

1

1

1

12

2

2

3

2

23

3

3具有n個結(jié)點不同形態(tài)的樹的數(shù)目和具有

n-1個結(jié)點互不相似的二叉樹的數(shù)目相同。有0個,1個,2個,3個結(jié)點的不同二叉樹如下b0

=1b1

=1b2

=2b3

=5b4

=14·計算具有n個結(jié)點的不同二叉樹的棵數(shù)最終結(jié)果：bibn-i-11哈夫曼樹(HuffmanTree)·路徑長度(Path

Length)兩個結(jié)點之間的路徑長度PL是連接兩結(jié)點的路徑上的分支數(shù)。樹的外部路徑長度是各葉結(jié)點(外結(jié)點)到根結(jié)點的路徑長度之和EPL。樹的內(nèi)部路徑長度是各非葉結(jié)點(內(nèi)結(jié)點)到根結(jié)點的路徑長度之和IPL。樹的路徑長度PL=EPL+IPL1234

5

6

782345678樹的外部路徑長度EPL=3*1+2*3=9樹的外部路徑長度EPL

=

1*1+2*1+3*1+4*1

=

101·帶權(quán)路徑長度(Weighted

Path

Length,WPL)二叉樹的帶權(quán)(外部)路徑長度是樹的各葉結(jié)點所帶的權(quán)值wi

與該結(jié)點到根的路徑長度li

的乘積的和。WPL

=

2*2+WPL

=

2*1+WPL

=

7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2

=

367*3

=

464*3

=

35242

455772

4

5

7帶權(quán)(外部)路徑長度達(dá)到最小哈夫曼樹

帶權(quán)路徑長度達(dá)到最小的二叉樹即為哈夫曼樹。在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。哈夫曼算法(1)由給定的n個權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴充二叉樹的森林F={T0,T1,T2,…,Tn-1

}，其中每棵擴充二叉樹Ti

只有一個帶權(quán)值wi

的根結(jié)點,其左、右子樹均為空。(2)重復(fù)以下步驟,直到F中僅剩下一棵樹為止：①在F中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。F

:

{7}

{5}

{2}

{4}

F

:

{7}

{5}

{6}47

567

5

2初始

F:{7}{11}117

5

62

4合并{5}{6}5合并{7}{11}2462

4合并{2}{4}F

:

{18}187

11舉例哈夫曼樹的構(gòu)造過程Weightparentlchild

rch752407-1-1-115-1-1-122-1-1-134-1-1-14-1-1-15-1-1-16-1-1-1上例存儲結(jié)構(gòu)初態(tài)572

46Weightparentlchild

rch07-1-1-115-1-1-1224-1-1-1344-1-1-146-12-1-315-1-1-16-1-1-1p1p2i過程56Weightparentlchild

rch7

11p107-1-1-1155-1-1-1224-1-1344-1-1465-123511-1-1-416-1-1-12

4p2i52

467

11Weightparentlchild

rch56p1076-1-1-1155-1-1224-1-1344-1-14652311

6-118

-110-14-51p2i18終態(tài)int

n=20;//葉結(jié)點數(shù)int

m=2*n-1;//結(jié)點數(shù)typedef

struct

{float

weight;int

parent,

lchild,

rchild;}

hufmtree;hufmtree[m];哈夫曼樹的定義建立哈夫曼樹的算法void

CreateHuffmanTree

(

HuffmanTree

T,float

fr[

]

)

{for

(

int

i

=

0;

i

<

n;

i++

)T[i].weight

=

fr[i];for

(

i