树 #

树在逻辑上是树状结构的数据结构，在物理上是根据实现的方式所决定的，主要有数组实现 (顺序存储结构) 和链表实现 (链式存储结构)。

树是一种非常重要的数据结构，该结构中的一个结点可以有一至多个直接后继结点，该结构可以用来描述客观世界中广泛存在的层次结构关系。

树是有 n (n>=0) 个结点的有限集合，当 n=0 时称为空树。在任一非空树 (n>0) 中，有且仅有一个称为根结点；其余结点可分为 m(m>=0) 个互不相交的有限子集 T(1),T(2),...,T(m)，其中，每个 T 又都是一棵树，并且称为根结点的子树。也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。

基本概念 #

• 双亲、孩子和兄弟。结点的子树的根结点称为该结点的孩子结点，且结点称为该孩子结点的双亲结点，具有相同双亲的结点互为兄弟结点。
• 结点的度。一个结点的子树的个数记为该结点的度。
• 叶子结点。叶子结点也称为终端结点，指度为 0 的结点。
• 内部结点。度不为 0 的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
• 结点的层次。根结点为第一层，根结点的孩子结点为第二层，依此类推，若某结点在第 i 层，则其孩子结点在第 i+1 层。
• 树的高度。一棵树的最大层数记为树的高度 (或深度)。