树（Tree）是若干个结点组成的有限集合，其中必须有一个结点是根结点，其余结点划分为若干个互不相交的集合，每一个集合还是一棵树，但被称为根的子树。注意，当树的结点个数为0时，我们称这棵树为空树，记为Φ ### 树的术语 1. 结点：表示树中的元素，包括数据项及若干指向其子树的分支； 2. 结点的度：结点所拥有的子树的个数称为该结点的度； 3. 叶子结点：度为0的结点称为叶子结点，或者称为终端结点； 4. 分支结点：度不为0的结点称为分支结点，或者称为非终端结点；一棵树的结点除叶子结点外，其余的都是分支结点； 5. 孩子、双亲、兄弟：若在树中一个结点A的子树的根结点是B，则称B为A的孩子（也称子结点），称A为B的双亲（也称父节点）；具有同一个双亲的子结点互称为兄弟； 6. 路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系，即结点ni是ni+1的父结点（1≤i<k），就把n1,n2,…,nk称为一条由n1至nk的路径；这条路径的长度是k-1； 7. 祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙； 8. 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1； 9. 树的深度：树中所有结点的最大层数称为树的深度； 10. 树的度：树中各结点度的最大值称为该树的度； 11. 有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树； 12. 森林：零棵或有限棵不相交的树的集合称为森林；自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别；任何一棵树，删去根结点就变成了森林；