注：转发
1.基本概念：
①树是n(n>=0)个节点的集合T，当n==0时，称为空树；当n>0时，该集合满足以下条件
②必有个根节点，他没有直接前驱，有零个或多个后继。
③其余n-1个结点划分成m（m>=0）个互不相交的有限集。每一个称为根的子树，每个子树的根节点有且仅有一个直接前驱，但有零个或多个直接后继。
2.树的相关术语：
结点：包括一个数据元素及若干指向其结点的分支信息
结点的度：一个节点的子树个数（说白了就是节点拥有的子分支数）
叶节点：度为0的结点，即无后继的结点，也称终端结点
分支结点：度不为零的结点，也称非终端结点
结点的层次：从根节点开始定义，根节点的层次为1，根的直接后继的层次为2，以此类推
节点的层序编号：将数中的结点按从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数
树的度：树中所有结点的度的最大值
树的高度（深度）：数中所有结点的层次的最大值
有序树：在树T中，如果个子树之间有先后次序的，则称为有序树
森林：m（m>=0）个互不相见交的树的集合，将一颗非空树的根节点删去，树就变成一个森林；繁殖给森林增加一个统一的根结点，森林就变成一棵树
同构：对两棵树，通过对结点是当地重命名，就可以使两棵树完全相等，（对应结点相等，对应结点的相关关系也相等），则称为两棵树的同构
孩子结点：一个结点的直接后继称为该结点的孩子结点
双亲结点：一个结点的直接前驱称为该结点的双亲结点
兄弟结点：同一双亲结点的孩子结点间互称兄弟结点
堂兄结点：父亲是兄弟关系或堂兄弟关系的陈伟堂兄弟结点
祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点
子孙结点：一个结点的直接后继和间接后继称为该节点的子孙结点
前辈：层号比该结点小的结点
后辈：层号比该结点大的结点
网友评论