文档介绍：数据结构(shù jù jié ɡòu)C语言树形结构
第一页，共115页。
树的定义
形式化定义：
树：T＝{K,R}。K是包含n个结点(jié diǎn)的有穷集合(n>0),关系R满足以下条件:
(1)有且仅有一个结点(jié diǎn)k0∈K,它对于关系R来说没有前驱结点(jié diǎn),结点(jié diǎn)k0称作树的根。
(2)除结点(jié diǎn)k0外,K中的每个结点(jié diǎn)对于关系R来说都有且仅有一个前驱结点(jié diǎn)。
(3)K中每个结点(jié diǎn)对于关系R来说可以有多个后继结点(jié diǎn)。
第1页/共115页
第二页，共115页。
递归定义：
树是由n(n≥0)个结点组成(zǔ chénɡ)的有限集合(记为T)。其中,
如果n=0,它是一棵空树,这是树的特例；
如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分为m (m>0)个互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。
第2页/共115页
第三页，共115页。
树的表示(biǎoshì)
(1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象(xíngxiàng)。下图就是采用这种表示法。
第3页/共115页
第四页，共115页。
(2)文氏图表示法。使用集合以及集合的包含关系描述(miáo shù)树结构。下图就是树的文氏图表示法。
第4页/共115页
第五页，共115页。
(3)凹入表示法。使用(shǐyòng)线段的伸缩描述树结构。下图是树的凹入表示法。
第5页/共115页
第六页，共115页。
(4)括号表示法。将树的根结点写在括号的左边,除根结点之外的其余(qíyú)结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。
第6页/共115页
第七页，共115页。
树的基本术语
1. 结点的度与树的度：树中某个(mǒu ɡè)结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。
2. 分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点,其余类推。
第7页/共115页
第八页，共115页。
3. 路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然(xiǎnrán),从树的根结点到树中其余结点均存在一条路径。
第8页/共115页
第九页，共115页。
4. 孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。具有(jùyǒu)同一双亲的孩子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。
第9页/共115页
第十页，共115页。