61树的基本概念 树的基本概念 结 1.树:是n(n>=0)个结点的有限集 n=0称空树。 在任一非空树(n>0)中 (1)有且仅有一个称为根的结点; 树 (2)其余结点可分为m(m>=0)个互不相交的 和有限集T1,T2,…,Tm,其中,每个集 合本身又是一棵树,并且称为根的子树 树2.结点的度:树的结点所拥有的子树数; 3.树的度:是树内各结点的度的最大值 4度为0的结点称为叶结点或终端结点 5.孩子结点、双亲结点、兄弟结点、堂兄弟 数 据 结点、祖先结点、子孙结点 物6结点的层次从根开始,根为第一层,根的 孩子为第二层;若某结点在第L层,则其 子树的根就在第L+1层。 7.树的深度或高度:树中结点的最大层次 树8有序树:如果将树中结点的各子树看成是 从左至右有次序的;反之,则是无序树 树9.森林:是m棵互不相交的树的集合。2 数 据 结 构 之 树 和 二 叉 树 3 6.1 树的基本概念 ¾ 树的基本概念 1. 树：是n(n>=0)个结点的有限集。 n=0 称空树。 在任一非空树(n>0)中: (1) 有且仅有一个称为根的结点； (2) 其余结点可分为m(m>=0)个互不相交的 有限集T1，T2，……，Tm，其中，每个集 合本身又是一棵树，并且称为根的子树。 2. 结点的度：树的结点所拥有的子树数； 3. 树的度：是树内各结点的度的最大值； 4. 度为0的结点称为叶结点或终端结点 数 据 结 构 之 树 和 二 叉 树 4 5. 孩子结点、双亲结点、兄弟结点、堂兄弟 结点、祖先结点、子孙结点…… 6. 结点的层次从根开始，根为第一层，根的 孩子为第二层；若某结点在第L层，则其 子树的根就在第L+1层。 7. 树的深度或高度：树中结点的最大层次。 8. 有序树：如果将树中结点的各子树看成是 从左至右有次序的；反之，则是无序树。 9. 森林：是m棵互不相交的树的集合