树的概念及相关术语

注：转发

---

1.基本概念：

①树是n(n>=0)个节点的集合T，当n==0时，称为空树；当n>0时，该集合满足以下条件

②必有个根节点，他没有直接前驱，有零个或多个后继。

③其余n-1个结点划分成m（m>=0）个互不相交的有限集。每一个称为根的子树，每个子树的根节点有且仅有一个直接前驱，但有零个或多个直接后继。

2.树的相关术语：

结点：包括一个数据元素及若干指向其结点的分支信息

结点的度：一个节点的子树个数（说白了就是节点拥有的子分支数）

叶节点：度为0的结点，即无后继的结点，也称终端结点

分支结点：度不为零的结点，也称非终端结点

结点的层次：从根节点开始定义，根节点的层次为1，根的直接后继的层次为2，以此类推

节点的层序编号：将数中的结点按从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数

树的度：树中所有结点的度的最大值

树的高度（深度）：数中所有结点的层次的最大值

有序树：在树T中，如果个子树之间有先后次序的，则称为有序树

森林：m（m>=0）个互不相见交的树的集合，将一颗非空树的根节点删去，树就变成一个森林；繁殖给森林增加一个统一的根结点，森林就变成一棵树

同构：对两棵树，通过对结点是当地重命名，就可以使两棵树完全相等，（对应结点相等，对应结点的相关关系也相等），则称为两棵树的同构

孩子结点：一个结点的直接后继称为该结点的孩子结点

双亲结点：一个结点的直接前驱称为该结点的双亲结点

兄弟结点：同一双亲结点的孩子结点间互称兄弟结点

堂兄结点：父亲是兄弟关系或堂兄弟关系的陈伟堂兄弟结点

祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点

子孙结点：一个结点的直接后继和间接后继称为该节点的子孙结点

前辈：层号比该结点小的结点

后辈：层号比该结点大的结点