NoImageNoImageNoImage第4章非线性数据结构基础(1)石志国大纲◎树与二叉树的基本概念、他们的存储结构◎图的基本概念和存储结构4.1树与二叉树树型结构是一类重要的非线性结构。树型结构是结点之间有分支、并且具有层次关系的结构。在计算机领域中，树有着非常广泛的应用。例如，在编译程序中，用树来表示源程序的语法结构。在数据库系统中，用树来组织信息等。4.1.1树的基本概念树(Tree)是n(n≥0)个结点的有限集，如该有限集为空，则称为空树。对于非空的树，应该满足如下2个条件：①有且仅有一个称为根(Root)的结点；②除根结点外的其余结点可分为m(m>0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)4.1.1树的基本概念树中常用的术语有：①结点的度结点所拥有的子树的个数称为该结点的度。②叶结点度为0的结点称为叶结点，或者称为终端结点。③分支结点度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。除根结点以外的分支结点也称为内部结点。④孩子、双亲、兄弟树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。4.1.1树的基本概念⑤路径、路径长度如果一棵树的一串结点n1，n2，…，nk存在如下关系：结点ni是ni+1的父结点（1≤i...
