首页  

树的定义和术语     所属分类 DS 浏览量 77
树的定义
树(tree)是包含n(n>0)个结点的有穷集,其中
1)每个元素称为结点(node)
2)有一个特定的结点被称为根结点或树根(root)
3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合 T1 T2 ... Tm-1 
   其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树 

也可以这样定义
树是由根结点和若干颗子树构成的
树是由一个集合以及在该集合上定义的一种关系构成的
集合中的元素称为树的结点,所定义的关系称为父子关系
父子关系在树的结点之间建立层次结构

Tree Root  SubTree 


子树不相交
除了根结点外,每个结点有且仅有一个父节点
一棵N个结点的树有N-1条边


树相关术语 节点的度 Degree 一个节点含有的子树的个数 叶子节点 leaf 度为0的节点 父节点 Parent 孩子节点或子节点 Child 一个节点含有的子树的根节点 兄弟节点 Sibling 具有相同父节点的节点 树的度 最大的节点的度 节点的层次 Level 从根开始 ,根为第1层,根的子节点为第2层,以此类推 树的高度或深度 Depth 树中节点的最大层次 堂兄弟节点 双亲在同一层的节点互为堂兄弟 节点的祖先 Ancestor 从根到该节点所经分支上的所有节点 子孙 Descendant 以某节点为根的子树中任一节点 森林 由n(n>=0)棵互不相交的树的集合 路径 路径长度

上一篇     下一篇
编程语言发展史

LLVM简介

数据结构中的各种树

算法基础知识

java String indexOf 为何不使用KMP

AVL树与红黑树(RBTree)