4.2 树的概念★1◎4

4.2 树的概念★1◎4

　　1．树的定义：树是n(n□0)个结点的有限集，当n=0时，称为空树，否则称为非空树，在一棵非空树中：
　　（1）有且仅有一个特定的结点称为根；
　　（2）当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集 , ,…, ，其中每个集合本身又是一棵树，称为根的子树。
　　2．结点的度：一个结点所拥有的子树数目称为此结点的度。
　　3．树的度：树内各结点度的最大值。
　　4．孩子与双亲：结点子树的根称为此结点的孩子，此结点称为孩子的双亲。
　　5．兄弟：同一个双亲的孩子之间称为兄弟。
　　6．祖先与子孙：从根到此结点所经分支上的所有结点称为此结点的祖先；以某结点为根的子树中的任一结点都称为此结点的子孙。
　　7．结点的层次：根结点的层次为1，其他结点的层次是它的双亲结点的层次加1。
　　8．树的深度：树中结点的最大层次称为该树的深度。
　　9．堂兄弟：双亲在同一层的结点互为堂兄弟。
　　10．有序树与无序树：如果树中结点各子树从左到右看是有次序的，则称此树为有序树，否则称为无序树。
　　11．森林：由m(m□0)棵互不相交树构成的集合称为森林，对树中每个结点而言，子树的集合称为子森林。
　　12．满m次树：如果除根结点和叶子结点外，其他结点的度均为m，且所有叶子结点都在同一层，这样的树称为满m次树。