Java - 数据结构之树
基本概念
树(Tree)不是线性表,而是一种描述非线性层次关系的数据结构,描述的是一对多的数据结构。
● 结点:Node,有的资料也叫做节点。
● 根结点(Root):没有父结点的结点,一棵树只能有一个根结点。
● 兄弟结点(Siblings):拥有同一个父结点的结点,它们是父结点的子结点。
● 孩子、双亲(Child、Parent):结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲。
● 结点的度(Degree):一个结点所包含的子树的数量,即子结点的数量。
● 树的度:该树所有结点中最大的度。
● 叶子结点(Leaf):树中度为零的结点,也叫终端结点。
● 分支(Branch):至少有一个孩子的结点,也叫非终端结点。
● 祖先(Ancestor):结点的祖先是从根到该结点所经分支上的所有结点。
● 后代(Descendant):以某结点为根的子树中的任一结点都称为该结点的后代。
● 边(Edge):一个结点和另一个结点之间的连接被称为边。
● 路径(Path):连接结点和其后代的结点之间的(结点,边)的序列
● 层次(Level):从根结点开始算,根结点是第一层,依次往下。(也可以把根结点作为第0层)
● 结点的高度(Height of node):该结点和某个叶子之间存在的最长路径上的边的个数。
● 树的高度(Height of tree):树的高度是其根结点的高度。
● 结点的深度(Depth of node):从树的根结点到该结点的边的个数。和高度的区别在于,深度是从根结点开始往下到自身结点;高度是从自身结点往下到叶子结点。
● 树的深度(Depth of tree):树中结点的最大层次。树的高度等于树的深度。
● 无序树:树中任意结点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树。
● 有序树:树中各结点的子结点之间从左到右按一定次序排列的树。
● 森林:n(n>=0)棵互不相交的树的集合。