(1)有且仅有一个称为根的结点;6 k) o0 O( G+ g8 l0 ~# v
(2)其余结点分为m(m≥0)个互不相交的非空集合,T 1 ,T 2 ,…,T m ,这些集合中的每一个都是一棵树,称为根的子树。
, U; X' v2 S3 z5 z在树上,根结点没有直接前趋。对树上任一结点X来说,X是它的任一子树的根结点惟一的直接前趋。为了讨论方便,我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直接前趋,则称A为B的双亲或父结点,称B为A的孩子(即“子女”)或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点,父结点相同的结点互称为兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙。反之若B是A的子孙,则称A是B的祖先,结点的层数(或深度)从根开始算起:根的层数为1,其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。
0 N- X5 D! P% H树(及一切树形结构)是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中,树中的一个结点可用来存储实际问题中的一个数据元素,而结点间的逻辑关系(即父结点与子结点之间的邻接关系)往往用来表示数据元素之间的某种重要的、必须加以表达的关系。 u( r' w; ~3 E3 O$ q
用图示法表示任何树形结构时,箭头的方向总是从上到下,即从父结点指向子结点,因此,可以简单地用连线代替箭头。4 u, d) N0 F; f1 F( y% w* F9 Q
2.树的基本运算包括:" u7 z' A1 K; q$ X" H
①求根ROOT(T),引用型运算,其结果是结点X在树T的根结点。
7 e9 f. F8 j2 g- O3 F2 S②求双亲PARENT(T,X),引用型运算,其结果是结点X在树T上的双亲结点;若X是树T的根或X不在T上,则结果为一特殊标志。
4 h, c" K, j4 r( m; ~/ H- J' x" w③求孩子CHILD(T,X,i),引用型运算,其结果是树T上的结点X的第i个孩子;若X不在T上或X没有第i个孩子,则结果为一特殊标志。& q: B' G- w2 O! E7 p+ n9 s+ z8 v3 `
④建树CREATE(X,T 1 ,…,T k )k≥1,加工型运算,其作用是建立一棵以X为根,以T 1 ,…,T k 为第1,…k棵子树的树。% S! g4 g5 E" K8 u, ^7 ?4 ?
⑤剪枝DELETE(T,X,i),加工型运算,其作用是删除树T上结点X的第i棵子树;若T无第i棵子树,则为空操作。
$ ^0 U3 J9 U x3 j( G$ P' S, f1 ?0 R3.二叉树
" z$ `0 Z6 ~1 Z( b$ t$ i6 |(1)二叉树的基本概念 |