数据结构一树

请尊重作者的劳动成果,如需转载请注明出处,谢谢！

如果觉得不错,可以关注我或者点赞,这就是你们对我最大的鼓励！

---

树型结构是非线性数据结构。树与二叉树最为常用。

树结构在生活中很常见，比如说，家族的族谱，政府机构的上下级关系等，都可以形象的表示树的结构。

树是由结点构成的。我们称结点A为根结点。结点{B,E,F,I,J}组成的集合，结点集合{C,G}，结点集合{D,H,K}都是A的子树。

关于树，有很多专业名词，下面介绍一些基本名词

度(Degree)------结点拥有的子树的个数称为结点的度。在上图中 A的度为3。B的度为2。C的度为1。D的度为1。G的度为0

叶子(Leaf)---度为0的结点称为叶子或者终端结点。在上图中，I , J , G , K都是叶子

孩子(Child)，双亲(Parent)--结点的子树的根称为该结点的孩子。在上图中， B , C , D 是 A 的孩子。 I , J 为 E 的孩子。相对的，A为B, C, D的双亲。 E 是 I, J 的双亲

兄弟(Sibling)---同一个双亲的孩子之间的关系则为兄弟。上图中，B , C , D 的关系为兄弟。 E , F 之间的关系也是兄弟

层次(Level)---树的根结点为第一层，根结点的孩子为第2层。某个结点为第 k 层则它的子树的根就在第(k + 1)层。

深度(Depth)--树的最大层次称为深度，或者高度。 上图中，该树的深度为4.

如果从树的结点的子树从左往右看，是有次序的。那么称该树为有序树，否则称为无序树。有序树的最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。如上图，该树为有序树，结点顺序为A,B,C,D,E,F..... 。 B 称为 A 的第一个孩子，D称为A的最后一个孩子。