1

我的班级目前正在将二叉树作为我们数据结构单元的一部分。我知道 Node 类的构造函数中必须有 3 个参数（值、左节点、右节点）。作为要求的一部分，我们必须有一个 Tree 类。树类的目的是什么？是为了管理整个节点集吗？它是否仅包含插入、删除和搜索特定节点所需的功能？

先感谢您。

我的节点类：

class Node {
protected int data;
protected leftNode;
protected rightNode;

Node (int data, Node leftNode, Node rightNode){
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
4

5 回答 5

2

是的，它应该通过封装所有与内部结构相关的行为和算法来给出Tree的功能接口。

为什么这很好？ 因为您将定义一些仅提供一些功能并且以独立方式工作的东西，这样每个人都应该能够使用您的树类，而无需关心节点、算法等。

理想情况下，该类应该是参数化的，这样您就可以拥有Tree<T>并且可以拥有通用方法，例如

T getRoot()

基本上你必须投影它，这样它才能让你

  • 插入值
  • 删除值
  • 搜索值
  • 参观整棵树
  • 任何
于 2012-04-09T22:11:00.640 回答
1

正如我所看到的，一个Tree类应该包含对树的根节点的引用，以及对整个树上操作的方法和属性的引用，而不是属于每个节点的方法，例如getLeft(), getValue()。

例如，我会size在类中定义一个属性，Tree向树添加或删除节点的方法（也恰好在这个类中）将负责保持大小是最新的。

于 2012-04-09T22:12:48.550 回答
1

任何数据结构的目的都是为您提供一种方法来保存相关值的集合并以有意义的方式操作它们。

树是一种特殊的数据结构。对于分层数据：具有自然父子关系的数据，这是一个不错的选择。二叉树的每个父节点最多有两个子节点。

树的另一个值得特别提及的特性是它是自相似的：树中的每个节点本身就是子树的根。递归利用了这个事实。

是的，这些都是开始的好方法。您可能想查看java.util.Map其他可能有用的界面。

于 2012-04-09T22:10:50.843 回答
0

正如你所怀疑的那样，这个假设有点缺陷。您定义的Node类型是二叉树的完美实例。

Jack 提到您希望Tree在整个节点集周围有一个类型，以便提供诸如getRoot插入、删除等操作。这当然不是一个坏主意，但绝不是要求。其中许多操作可以Node自行进行，您不一定必须拥有所有这些操作；例如，有支持和反对进行getRoot手术的论据。反对它的一个论点是，如果你有一个算法在某一时刻只需要一个子树，那么Tree持有根的对象会阻止你的算法不再需要Node的 s 的垃圾收集。Node

但更一般地说，这里需要问的真正问题是：你处理的哪些是接口，哪些是实现？因为如果你想将二叉树作为接口暴露给调用者是一回事，如果你想提供某种有限映射作为接口则是另一回事，而二叉树只是一个实现细节。在前一种情况下，客户端将“知道”一棵树要么是要么null是Node具有值和分支的，并且将被允许，例如，对树的结构进行递归；在后一种情况下，客户“知道”的只是你的类支持某种形式的put,get和delete操作，但不允许依赖于将其存储为搜索树这一事实。在后一种情况的许多变体中，您确实会使用Tree类型作为前端来对客户端隐藏节点。（例如，Java 的内置java.util.TreeMap类就是这样做的。）

所以最短的答案是，真的，这取决于。稍长一点的答案是它取决于二叉树实现与其用户之间的合约是什么；调用者允许对树进行哪些假设，二叉树的哪些细节是作者希望将来能够改变的事情，等等。

于 2012-04-09T22:27:00.010 回答
0

“是用来管理整套节点的吗？”

是的。

“它是否仅包含插入、删除和搜索特定节点所需的功能？”

基本上，是的。因此，它应该至少包含对根节点的引用。

于 2012-04-09T22:10:29.557 回答