树的概念与基本术语解析-数据结构讲义

"树的基本术语-树和森林--清华大学课程讲义-数据结构(PPT)" 树是一种非线性的数据结构，它由一个有限的结点集合组成。这些结点按照特定的关系组织起来，形成一个层次分明的结构。在树的数据结构中，每个结点可以有零个或多个子结点，这使得树能够表示多种复杂的关系。 1. 结点的度：度是指一个结点拥有的子结点数量。例如，如果一个结点有两个子结点，它的度就是2。 2. 子女与父结点：子结点是指直接连接到父结点的结点，而父结点是子结点的直接前驱。在树中，除了根结点之外，每个结点都有且只有一个父结点。 3. 兄弟结点：拥有相同父结点的结点互称为兄弟结点。例如，一个父结点的两个子结点就是兄弟结点。 4. 根结点：树中的顶级结点，没有父结点，只有子结点。它是树的起始点，层次为0。 5. 分支结点：也称为非终端结点，是指至少有一个子结点的结点，不同于叶结点，它们不是树的末梢。 6. 叶结点：又称终端结点，是没有子结点的结点。叶结点是树的最末端。 7. 结点的层次：从根结点开始，根的层次为0，其子结点的层次为1，依此类推。层次的计算是基于父结点的层次加上1。 8. 树的高度：树的高度是树中最大结点层次的值。空树的高度为-1。 9. 树的度：树的度是指树中所有结点的度的最大值，反映了树的最大分支程度。 10. 有序树与无序树：在有序树中，结点的子结点顺序是有意义的，改变子结点的顺序会创建一棵不同的树。而在无序树中，子结点的顺序无关紧要，可以互换位置。 11. 森林：森林是若干棵树的集合，其中每棵树都遵循上述的树定义和术语。 树型结构在计算机科学中广泛应用，如文件系统、网页链接结构、数据库索引、编译器语法分析等。它们提供了一种高效的方式来存储和操作分层的数据，便于进行搜索、插入和删除等操作。通过理解和掌握这些基本术语，我们可以更好地理解和利用树结构解决实际问题。