树的基本知识、性质及专有名词释义

小咪咪 2022-03-15 01:24 539阅读 0赞

（一）.树的定义 ：**树**是由n（n>=0）个节点（元素）组成的有限集合（记为T）。其中，如果n = 0，他就是一颗空树，这是树的特例；如果n > 0，这n个节点中存在（有仅存在）一个节点作为树的根节点，简称为根节点，其余节点可分为m(m >= 0)个互不相交的有限集T1,T2,T3…Tm，其中每一个子集本身又是一颗符合本定义的树，更为根节点的子树。  
树的定义是递归的，因为在树的定义中又用到树的定义他刻画了书的固有特性。  
（二）.树的基本术语：  
1.节点的度与树的度：树中**某个节点的子树的个数称为该节点的度**。**树中各节点的度的最大值称为树的度**，通常称度为m的树称为**m次树**。  
2.分支节点与叶子节点：度不为0的节点称为**非终端节点**，又叫**分支节点**。度为零的节点称为**终端节点**或者**叶子节点**。在分支节点中，每个节点的分支数就是该节点的度。  
3.路径与路径长度：对于任意两个节点Ki和Kj，若树中存在一个节点序列Ki，Ki1，Ki2，…Kin使得序列中除Ki外的任一节点都是其在序列中的前一个节点的后继，则称该节点序列为由Ki到Kj的一条路径，用路径所通过的节点序列表示这条路径。路径的长度等于路径所通过的边的数目。（在树中所有的边都是有向的，如果<a,b>是树中的一条边，则a是b的双亲节点，b是a的孩子节点，两个兄弟节点之间不存在路径，从根节点到树中其他任何节点都存在路径）。  
4.孩子节点、双亲节点、兄弟节点：在一棵树中，每一个节点的后继被称作该节点的**孩子节点**（或子女节点）。相应的，该节点被称作孩子节点的双亲节点（或父节点），具有同一个双亲的孩子节点互为兄弟节点。  
5.节点的层次和树的高度：树中的每个节点都处在一定的层次上，界点的层次从树根开始定义，根节点为第一层，他的孩子节点为第二层，以此类推。一个节点所在的层次为其双亲节点所在层次加一。树中节点的最大层次成为**树的高度**（或树的深度）。  
6.有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则**称为有序树**，否则称之为无序树。通常意义上讲的树都是无序树。  
7.森林：n（n>=0）个互不相交的树的集合称为**森林**。森林与树的概念十分相近，因为只要把树的根节点删掉，它就变成了森林。反之，只要给n颗独立的树加上一个节点，并把这n棵树作为该节点的子树，则森林就变成了树。  
8.满m次树：如果除根节点和叶子节点外，其他节点的度均为m，且所有叶子节点均在同一层，这样的树称为**满m次树**。满m次树可以按层从上到下、同层从左到右遍历，并对层次遍历的次序编号，根节点编号为1，然后依次递增，这样称为满m次树的层序编号。  
9.完全m次树：对于高度为h的满m次树，按满m次树的 层序编号后，最高曾连续缺少编号最大的若干个节点，但最高层中至少有一个节点，这样的树称为高度为h的**完全m次树**。  
（三）树的性质：、  
1.树中的节点数等于所有节点的度数加一。  
2.度为m的树中第i层上至多有m^(i - 1)个节点（i >=1）。（通常约定，树中根节点的层次为1，其孩子节点层次为2）以此类推。  
3.高度为h的m次树至多有（m^h - 1）/(m - 1)个节点。  
4.具有n个节点的m次树的最小高度为logm(n(m - 1) + 1)。