树型结构是一类重要的非线性结构,树型结构是结点之间有分支, 并且具有层次关系的结构,它非常类似于自然界中的树。
树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程等等。
树是n(n>=0)个结点的有限集,递归是树的固有特性。
当n=0时,称为空树。当n>0时,有且仅有一个特定的称为根的结点;其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm,其中每个子集Ti又是一棵树,并称其为子树。
1. 一般表示法
2. 文氏图法
3. 嵌套括号法
4. 凹入法表示
1. 结点:由一个数据元素及若干指向其它结点的分支所组成。
2. 度:分为节点的度和树的度。节点的度是该节点的子树数量,即分支的数量。树的度是树中节点的最大值。
3. 叶子:度为零的结点。
4. 非终端结点:度不为零的结点。
5. 孩子:结点的子树的根称为该结点的孩子。
6. 双亲:一个结点称为该结点所有子树根的双亲。
7. 祖先:结点祖先指根到此结点的一条路径上的所有结点。
8. 子孙:从某结点到叶结点的分支上的所有结点称为该结点的子孙。
9. 兄弟:同一双亲的孩子之间互称兄弟。
10. 结点的层次:从根算起,根为第一层,其孩子在第二层, …., L层上任何结点的孩子都在L+1层上。
11. 堂兄弟:其双亲在同一层的结点。
12. 树的深度:树中结点的最大层次。
13. 有序树:若树中各结点的子树从左到右是有次序的, 不能互换,称为有序树。
14. 无序树:若树中各结点的子树是无次序的, 可以互换,则成为无序树。
15. 森林:是 m(≥0) 棵树的集合。
1. 求根 Root(T):求树T的根结点。
2. 求双亲 Parent(T,X):求结点X在树T上的双亲; 若X是树T的根或X不在T上,则结果为一特殊 标志。
3. 求孩子 Child(T,X,i):求树T上结点X的第i个孩子 结点;若X不在T上或X没有第i个孩子,则结 果为一特殊标志。
4. 建树 Create(X,T1 ,…,Tk ),k>1:建立一棵以X为根, 以T1 ,…,Tk为第1,…,k棵子树的树。
5. 剪枝 Delete(T,X,i):删除树T上结点X的第i棵子 树;若T无第i棵子树,则为空操作。
6. 遍历 TraverseTree(T):遍历树,即访问树中每个 结点,且每个结点仅被访问一次。