d树及二叉树.doc

结点包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。 在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。 在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。 数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点。数据结构中的“树” 数据结构:树树的定义树（tree）是包含n（n0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件： （1）有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。 （2）除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。 （3）K中各结点，对关系N来说可以有m个后继（m=0）。 若n1，除根结点之外的其余数据元素被分为m（m0）个互不相交的结合T1，T2，Tm，其中每一个集合Ti（1=i=m）本身也是一棵树。树 T1，T2，Tm称作根结点的子树（sub tree）。 树也就可以这样定义：树是有根结点和若干颗子树构成的。（上一段来自高林，数据结构（C+），北京 清华大学出版社） 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下: 单个结点是一棵树，树根就是该结点本身。 设T1,T2,.,Tk是树，它们的根结点分别为n1,n2,.,nk。用一个新结点n作为n1,n2,.,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,.,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,.,nk为结点n的子树。 空集合也是树，称为空树。空树中没有结点。 数学规律h树 连通无回路的无向图. h树的判别 图 ,T是树的充分必要条件是(六个等价定义) (定理14): (1) T是无回路的连通图； (2) 图T无回路且mn1； (3) 图T连通且mn1 (4) 图T无回路，若增加一条边，就得到一条且仅一条回路； (5) 图T连通，若删去任一边，G则不连通； (6) 图T的每一对结点之间有一条且仅有一条通路. h生成树 图G的生成子图是树，该树就是生成树. h权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T). h最小生成树 带权最小的生成树. h有向树 有向图删去边的方向为树，该有向图就是有向树. h根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. 数据结构:树h每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的