ch10-1树南京大学C语言与数据结构

Ch 10

树

目录

树的基本概念和术语 二叉树

树(Tree)是由一个或多个结点组成的有限集合T。其中：

–有一个特定的结点称为该树的根(Root)结点；–除根结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，…，Tm，且其中每一个集合本身又是一棵树，称之为根的子树(Subtree)。

根（root）

递归的定义

子树为0，结束递归

子树（subtree子树（subtree

树的定义 树T– A是根结点–三个互不相交的子集 T1={B,H,I} T1 B T2={C} T3={D,E,F,G}–子树：T1、T2、T3 H子树的根结点：B、C、DA T T2 C D T3

I

T31

E

F T32

G

树的应用

具有层次关系的集合–社会组织机构–互联网域名–

系统的进程管理

抽象数据类型树的定义

A T

树的表示方法 倒悬树法 嵌套集合表示法 凹入表示法T1 B

T2 C D T3

H

I

T31

E

F T32

G

A BK B G C A F H K I

E F CJ D

G D H I K J

(a)

(b)

结点的度和树的度

树的结点：包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度(Degree)。 树的度是指树中结点的度的最大值。A T T2 T1 B C D T3

B结点有2个子树，则它的度为2。在树T中，A结点的度最大，值为3,树T的度为3。F T32

H

I

T31

E

G9

分支结点和叶子结点

度不为0的结点为分支结点，也叫非终端结点。 度为0的结点为叶子(Leaf)或终端结点。A T T2 T1 B C D T3

H

I

T31

E

F T32

G

孩子、双亲、兄弟 孩子(Child) 双亲(Parent) 兄弟(Sibling)

A T T2 T1 B C D T3

H

I

T31

E

F T32

G

结点的层次和树的高度

结点的层次(Level)从根结点开始定义，根为第一层，根结点的孩子为第二层，依次类推，其余结点的层次值为双亲结点层次值加1。树中结点的最大层次值称为树的高度或深度(Depth)。A T T2 T1 B C D T3

H

I

T31

E

F T32

G12

无序树、有序树、森林

若树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

本文来源：https://www.bwwdw.com/article/x7ae.html