1

我的任务是执行以下操作：

编写、记录（内部）和测试 Java 程序以解决以下问题：

使用链接表示来实现二叉树 ADT，其中每个节点包含以下内容：

  • 数据
  • 左孩子的参考/链接
  • 参考/链接到正确的孩子

假设数据是整数值。

执行以下操作（如教科书 7.3 节所述）：

  • 尺寸
  • 是空的
  • 取代
  • 根
  • 剩下
  • 正确的
  • 已经离开了
  • 有权利
  • 是内部的
  • 是外部的
  • 是根
  • 向左插入
  • 插入右
  • 附
  • 消除

以及以下遍历：

  • 预购
  • 后购
  • 为了

我知道二叉树是如何工作的，并且在大多数情况下我这样做没有问题 - 但我遇到的问题是我不允许在节点类中拥有除给定三个之外的任何变量 - 也就是说，我无法建立父链接。如果我无法链接到父节点，如何检查给定节点是否是树的根？

4

3 回答 3

2

假设你有一个孤立的节点，只知道它的左右链接节点，没有别的，没有办法确定根，除非你有一组节点要测试。

显而易见的方法——当然——是使用周围树结构的根属性，它实际上定义了树，即这里介绍的所有其他解决方案。

但是，如果由于某种原因不允许您这样做，您可以执行以下代码来测试所有可用节点。作为副作用，它还为您提供了“父”属性的实现。

实际上，“根”可以定义为“没有父节点的节点”。

public TreeNode Parent(TreeNode node)
{
  TreeNode result = null;
  foreach (TreeNode candidate in allTheNodes)
    if (candidate.left == node || candidate.right == node)
      return candidate;

  return null;
}

public TreeNode root()
{
  foreach (node in allTheNodes)
    if (Parent(node)==null) 
      return node;

  return null;
}
于 2013-02-25T19:50:07.417 回答
2

您可以定义BinaryTree类并Node在其中保留根字段。所以你已经知道了根源

于 2013-02-25T18:52:48.307 回答
1

使用 aBinaryTree你有具有三个属性的节点：

int value; 
Node left;
Node right;

因此，如果我想构建一棵树，我可以这样做：

root = Node();
root.value = 5;
root.left = Node();
root.left.value = 3;
root.left.right = Node()
root.left.right.value = 4;
root.right = Node();
root.right.value = 6;
root.left.left = node();
root.left.left.value = 1;

这会给一棵树：

    5
   / \
  3   6
 / \
1   4

现在我们root持有所有这些信息，我们可以通过它访问任何连接到它的节点。

因此，本质上，您需要为所有这些操作编写一个包装器。要检查任意节点是否为根，只需将其与您存储为根的节点进行比较即可。

结构如下：

public class BinaryTree{
    class Node {
        int value;
        Node left;
        Node right;
    }
    Node root;
    //method declarations
}
于 2013-02-25T19:03:15.593 回答