树的定义和基本术语

2014/10/29 posted in  算法&数据结构

定义

树是n个结点的有限集。在任意一棵非空树中:

1.有且只有一个特定称为根的结点

2.当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,....,Tm。其中每一个集合本身又是一棵树,并且称为根的子树

和广义表一样,树的结构定义是一个递归 的定义,即在树的定义中又用到树的概念。

 基本术语

  1. 结点的度:一个结点含有的子树的个数称为该节点的度;
  2. 叶节点终端节点:度为零的节点称为叶节点;
  3. 非终端节点分支节点:度不为零的节点;
  4. 双亲节点:在含有孩子的节点中,这个节点称为孩子节点的双亲节点;
  5. 孩子节点:一个节点子树的根节点称为孩子节点;
  6. 兄弟节点:具有相同双亲节点的节点互称为兄弟节点;
  7. 树的度:一棵树中,最大的结点的度称为树的度;
  8. 结点的层次:从根开始定义起,根为第0层,根的孩子为第1层;
  9. 树的高度深度:树中节点的最大层次;
  10. 堂兄弟:双亲在同一层的节点互为堂兄弟;
  11. 节点的祖先:从根到该节点所经分支上的所有节点;
  12. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  13. 有序树:树中结点的各子树看成从左至右是有次序的(既不可互换),反之为无序树
  14. 森林:由m(m>=0)棵互不相交的树的集合称为森林;、

就逻辑结构而言,任何一棵树是一个二元组Tree(root,F),其中;root是数据元素,称作树的根结点;F是m(m>=0)棵树的森林,F=(T1,T2,....,Tm),其中Ti = (r,Fi)称作为根root 的第i棵子树;当m!=0时,在树根和其子树森林之间存在下列关系:

Rf = {|i = 1,2,...,m,m>0}。

这个定义将有助于得到森林和树与二叉树之间转换的递归定义。