数据结构(5.0)——树的定义和基本术语

树的基本概念

树是n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一颗非空树中应该满足:

有且仅有一个特定的称为根的结点。

当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1、T2、.......，Tm，其中每个集合本身又是一颗树，并且称为根结点的子树

树形逻辑结构的应用

结点之间的关系描述 

在树形结构中，节点之间的关系可以通过家族关系来类比理解。下面是根据您提供的家族关系术语，对应到树形结构中的节点关系：

1. 祖先结点：

   • 在树形结构中，从一个节点到根节点的路径上的所有节点都被称为该节点的祖先结点。例如，从“你”到“爷爷”的路径上，父亲是“你”的祖先结点，爷爷是“你”和“父亲”的共同祖先结点。

2. 子孙结点：

   • 一个节点的子孙结点是指它的所有后代节点。例如，对于“父亲”节点，它的子孙结点包括“你”以及“你”的所有子节点（在这个例子中是F、K和L）。

3. 双亲结点（父结点）：

   • 每个节点（除了根节点）都有一个父结点，即直接连接到该节点的上一级节点。例如，“父亲”是“你”的父结点。

4. 孩子结点：

   • 一个节点的直接子节点被称为它的孩子结点。例如，“你”是“父亲”的孩子结点。

5. 兄弟结点：

   • 具有相同父结点的节点互称为兄弟结点。例如，“父亲”、“二叔”和“三叔”是兄弟结点，因为他们都有相同的父结点“爷爷”。

6. 堂兄弟结点：

   • 在家族关系中，堂兄弟是指父亲的兄弟的孩子。在树形结构中，如果一个节点的父结点与另一个节点的父结点是兄弟关系，那么这两个节点互称为堂兄弟结点。例如，“你”和“二叔”与“三叔”的孩子结点是堂兄弟结点。

祖先结点：爷爷—>父亲—>你

子孙结点： 父亲—>你+F—>K+L

双亲结点(父结点)：父亲—>你

孩子结点：父亲—>你

兄弟结点：爷爷—>父亲+二速+三叔

堂兄弟结点：父亲+二速+三叔

结点的路径

• 定义：从一个节点到另一个节点的路径是指在这两个节点之间的一系列连续的边。在树形结构中，从任意节点到根节点的路径是唯一的。
• 表示：路径通常通过列出路径上的节点来表示，节点之间用箭头或线段连接。

路径长度

• 定义：路径长度是指路径上的边的数量。在树形结构中，路径长度也常用来表示两个节点之间的距离。
• 计算：路径长度等于路径上的节点数减一，因为每两个节点之间有一条边。

结点、树的属性描述

属性：

结点的层次(深度)——从上往下数

结点的高度——从下往上数

树的高度(深度)——总共多少层

结点的度——有几个孩子(分支)

树的度——各结点的度的最大值

有序树和无序树

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

树和森林

森林：森林是m(m>=0)颗互不相交的树的集合

如果在所有树之上再加一个根结点，那么森林就又变成了一颗树

 总结