java - 如何从文本文件构造无序二叉树

Question

亲爱的 friend 们，我是一名中级java用户。我陷入了以下问题。我想从多行(假设 40 行)文本文件构造一个无序二叉树 [或最多有两个节点的一般树]。然后文本文件被分成两半；假设 20:20 行。然后，对于每一半，计算一个特定的(比如说哈希)值并将其存储在根节点中。所以每个节点包含四个元素。指向两个子文件(左和右)的两个指针以及原始文件两半的两个哈希值。接下来，对于每一半(20 行)重复该过程，直到每片叶子都有一行文本。让节点有

public class BinaryTree {

    private BinaryTreeNode leftNode, rightNode;

    private String leftHash,rightHash;

}

我需要帮助来编写树结构和搜索函数。通过输入一行来执行井搜索。然后为此查询行创建哈希代码，并将其与每个节点保存的两个哈希进行比较。如果查询行的哈希值接近 leftHas，则访问 leftNode；如果查询行的哈希值接近 rightHash，则访问 rightNode。该过程持续进行，直到找到精确的哈希值。我只需要树的构建和搜索技巧。哈希比较等都不是问题

Answer 1

您需要首先将文件读入字符串。

字符串中的第一个字符可以用作根。 root + 1 为左侧，root + 2 为右侧

考虑根的左节点(Root + 1)，您也可以将其视为 Root + N。这意味着右节点将是 Root + N + 1。

您现在可以通过确定当前所在的节点并分别设置左侧和右侧来递归地解决此问题。

让我们考虑一下，

您已经建立了根节点、左节点和右节点。此时您已经使用了 3 个字母/数字(如果无序也没关系)。下一步是向下移动一层并开始填充左侧，您有根，您需要左侧和右侧节点。然后移动到右边的节点，做左右节点的这个等等。

稍微想一下，看看你会得到什么。

干杯，

迈克

编辑:

要搜索，

搜索二叉树也是一个递归主题。 (我以为您之前说过树是无序的，如果假设树是有序的，这可能会改变树的布局方式)。

如果它是无序的，您可以简单地以这样的方式递归树

A.) 检查根节点B.) 检查左节点C.) 继续检查左侧节点，直到有匹配项，或者没有更多左侧节点可供检查D.) 递归1，检查右节点E.) 检查左节点，F.) 退避，检查右侧节点

这个主题将持续下去，直到最终您首先检查了所有左侧节点，然后检查了右侧节点。关键是在任何时候你有一个根节点，先向左，然后向右。 (我忘记了这是什么遍历类型，但是如果你想在此之上实现它们，还有其他的遍历类型，我个人认为这是最容易记住的)。

然后您将对根节点的右子节点重复此操作。

如果您在任何时候找到匹配项，请退出。

请记住，这是递归的，因此请确保您一步一步地思考这个过程。根据定义，它是递归的，因为您将始终对树的每个部分执行步骤 x、y、z。

要打败一匹马，让我们从 3 个节点开始。(简化)

首先是根，

if(root == (what your looking for))
{ 
   return root
}
else if(root.leftNode == (what your looking for))
{
   return root.leftNode
}
else if(root.rightNode == (what your looking for))
{
   return root.rightNode
}
else
{
   System.out.println("Value not found")
}

如果你有 5 个节点，那么 root 将有一个左节点和右节点，而 root.leftNode 将有一个左节点和右节点...您也可以在 root.leftNode 上重复上述步骤，然后搜索 root。右节点

如果您有 7 个节点，您将搜索 root.leftNode 的所有节点，然后递归回搜索 root.leftNode。

希望这对您有所帮助，

在我看来，当谈论遍历树木时，图片效果更好。

也许在这里寻找更好的视觉效果 http://www.newthinktank.com/2013/03/binary-tree-in-java/