树的讲解.doc

线性结构:数据元素的逻辑位置之间呈线性关系,即每一个数据元素通常只有一个前件(除第一个元素外)和一个后件(除最后一个元素外)。 非线性结构:至少存在一个结点(数据元素)有多于一个前件或后件的数据结构。树和图为非线性结构。 1.树的概念 树是n(n>0)个结点的有限集,这个集合满足以下条件: (1)有且仅有一个结点没有前件(父亲结点),该结点称为树的根; (2)除根外,其余的每个结点都有且仅有一个前件; (3)除根外,每一个结点都通过唯一的路径连到根上。这条路径由根开始,而未端就在该结点上,且除根以外,路径上的每一个结点都是前一个结点的后件(儿子结点); 树结构没有封闭的回路。