会计学一、树的概念1、树的定义树是一种常见的非线性的数据结构(jiégòu)：树型结构(jiégòu)。空树（不含结点）；非空树（至少一个结点）树的递归定义如下：树是n(n>=0)个结点的有限集，这个集合满足以下条件：⑴有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；⑵除根外，其余的每个结点都有且仅有一个前驱；⑶除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知(kězhī)，树结构没有封闭的回路。2、结点的分类结点一般分成三类⑴根结点：没有父亲的结点。在树中有且仅有一个根结点。⑵分支结点：除根(chúgēn)结点外，有孩子的结点称为分支结点。⑶叶结点：没有孩子的结点称为树叶。根结点到每一个分支结点或叶结点的路径是唯一的。从根A到结点M的唯一路径为ADHM。3、树的度⑴结点的度：一个(yīɡè)结点的子树数目称为该结点的度。⑵树的度：所有结点中最大的度称为该树的度(宽度）。4、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推(lèituī)。图中的树共有4层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为4。5、森林所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点(jiédiǎn)A，其原来的三棵子树Tb，Tc，Td的集合{Tb，Tc，Td}就为森林，这三棵子树的具体形态如图（c）。6、有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。(1)如果树中同层结点从左而右排列，其次序不容(bùróng)互换，这样的树称为有序树；(2)如果同层结点的次序任意，这样的树称为无序树。二、树的表示方法树的表示方法一般有两种：⑴自然界的树形表示法：用结点和边表示树，例如下图采用(cǎiyòng)的就是自然界的树形表示法。树形表示法一般用于分析问题。⑵括号(kuòhào)表示法：先将根结点放入一对圆括号(kuòhào)中，然后把它的子树按由左而右的顺序放入括号(kuòhào)中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号(kuòhào)括起来，同层子树之间用逗号隔开，最后用闭括号(kuòhào)括起来。例如下图可写成如下形式(A(B(E(K,L),F),C(G),D(H(M),I,J)))优点:易于保存;缺点:不直观.树的存储结构一般有两种1、静态的记录数组。所有结点存储在一个(yīɡè)数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个(yīɡè)儿子的下标Constn=树的度；max=结点数的上限；Typenode=record{结点类型}data：datatype；{数据域}child：array[1‥n]ofinteger；{指向各儿子的下标}end；treetype=array[1..max]ofnode；Vartree：treetype；{树数组}12、动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据(shùjù)域和n(n为树的度)个指针域共n+1个域组成，其表示方法如下：Constn=树的度；Typetreetype=^node；{结点类型}node=recorddata：datatype；{数据(shùjù)域}next：array[1‥n]oftreetype；{指向各儿子的指针域}end；Varroot：treetype；{根结点指针}1、家族的统计一已知某个村子中人员关系，统计该村子中含有(hányǒu)几个家族，并求出每个家族中的祖先的编号。输入：第一行：n：该村子人的数量；（n<=10000）以下若干行：每行两个结点编号：i，j：i是j的父结点(I,j<=1000)。输出：第一行：该村中家族的数量。第二行：依次输出每个家族中祖先的编号（从小到大）。样例输入：912234645789194分析：father:array[1..10000]ofinteger;father[i]:记录i的父亲结点。初始(chūshǐ)时：father[i]=0;读入：i，j执行：father[j]:=i;最后统计father[i]=0的结点，即是老祖宗结点。时间复杂度：O(n)已知一个家族中各成员之间的关系(guānxì)，并知道其中有唯一的祖先。完成下列要求。constmaxn=100;typetreetype=r