6.1  

6.1  

树的定义和基本术

树的定义和基本术

语

语

1. 

1. 

树的定义

树的定义

    

    

    

    

树是由

树是由

n

n

 (

 (

n

n

 

 

≥

≥

 0)

 0)

个结点组成的有限集

个结点组成的有限集

合。

合。

   

   

如果

如果

n

n

 = 0

 = 0

，称为空树；

，称为空树；

   

   

如果

如果

n

n

 > 0

 > 0

，则

，则

:

:

    

    





 

 

有一个特定的称之为

有一个特定的称之为

根

根

(root)

(root)

的结点

的结点

，它只有后继，但没有前驱；

，它只有后继，但没有前驱；

    

    





 

 

除根以外的其它结点划分为

除根以外的其它结点划分为

m

m

 (

 (

m

m

 

 

≥

≥

 

 

0)

0)

个互不相交的有限集合

个互不相交的有限集合

T

T

0

0

, 

, 

T

T

1

1

, …, 

, …, 

T

T

m

m

-1

-1

，每

，每

个集合本身又是一棵树，并且称之为根的

个集合本身又是一棵树，并且称之为根的

子

子

树

树

(subTree)

(subTree)

。每棵子树的根结点有且仅有一

。每棵子树的根结点有且仅有一

个

个

直接

直接

前驱，但可以有

前驱，但可以有

0

0

个或多个后继。

个或多个后继。