第6章树和二叉树 6.1树 61.1树的定义 树是由n(心0)个结点组成的有限集合(记为T)。如 果n=0,它是一棵空树,这是树的特例;如果灬>0,这n个结 点中存在(有仅存在)一个结点作为树的根结点(root), 其余结点可分为m(m0)个互不相交的有限集T、T2…、 Tm,其中每个子集本身又是一棵符合本定义的树,称为根 结点的子树
第6章 树和二叉树 6.1 树 6.1.1 树的定义 树是由n（n≥0）个结点组成的有限集合（记为T）。如 果n=0，它是一棵空树，这是树的特例；如果n>0，这n个结 点中存在（有仅存在）一个结点作为树的根结点（root）， 其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、 Tm，其中每个子集本身又是一棵符合本定义的树，称为根 结点的子树
树是一种非线性数据结构,具有以下特点 它的每一结点可以有零个或多个后继结点,但有且只有 个前驱结点(根结点除外);这些数据结点按分支关系组 织起来,清晰地反映了数据元素之间的层次关系。可以看出, 数据元素之间存在的关系是一对多的关系
树是一种非线性数据结构，具有以下特点： 它的每一结点可以有零个或多个后继结点，但有且只有 一个前驱结点（根结点除外）；这些数据结点按分支关系组 织起来，清晰地反映了数据元素之间的层次关系。可以看出， 数据元素之间存在的关系是一对多的关系
抽象数据类型树的定义如下: ADT Tree 数据对象: D={a11si≤n,n≥0,a为 Elemtype类型} /假设 ElemType为 string 数据关系: R={r} r={<a1a1>|a1a;∈D,1≤i,j≤n,其中每个结点最多只有一个前驱结点、 可以有零个或多个后继结点,有且仅有一个结点即根结点没有前驱结点} 基本运算: bool CreateTreeo:由树的逻辑结构表示建立其存储结构。 string DispTreeo:输出树。 string GetParent(inti):求编号为的结点的双亲结点 string getsons(inti):求编号为的结点的所有孩子结点
抽象数据类型树的定义如下： ADT Tree { 数据对象： D={ai | 1≤i≤n,n≥0,ai为ElemType类型} //假设ElemType为string 数据关系： R={r} r={<ai ,aj> | ai ,aj∈D, 1≤i，j≤n，其中每个结点最多只有一个前驱结点、 可以有零个或多个后继结点，有且仅有一个结点即根结点没有前驱结点} 基本运算： bool CreateTree()：由树的逻辑结构表示建立其存储结构。 string DispTree()：输出树。 string GetParent(int i)：求编号为i的结点的双亲结点。 string GetSons(int i)：求编号为i的结点的所有孩子结点。 … }
6.12树的逻辑结构表示方法 D B IK K (a)树形表示法 (b)文氏图表示法
6.1.2 树的逻辑结构表示方法 A C G J B E D F H I K L M H L D I K M C G J E B F （a）树形表示法 （b）文氏图表示法 A
F G J D A(B(E,F, C(G(), D(H, IK, L, MD) H K M (c)凹入表示法 (d)括号表示法
F C A B D E G J H I K L M （c） 凹入表示法 （d）括号表示法 A(B(E,F),C(G(J)),D(H,I(K,L,M)))