0

我正在编写一个转换为摩尔斯电码的程序，反之亦然。我使用树来更有效地搜索代码或相关值。Morse 和相关值从文件读入静态数组。索引 0 是所有其他子树的根，实际上是一个连接到左子树 (index[1]) 和右子树 (index[16]) 的虚拟节点。

读入节点后，我通过遍历静态数组并在执行过程中分配节点来链接子节点。索引 [2] - [16] 保存左子树。索引 [17] - (alphaTree.length - 1) 持有右子树。

这是我的问题：在尝试分配所有子节点时，其中一些在我打印出来时为空。节点本身不是空的，只是子节点。

我注意到一个模式，但不知道如何修复它。

下面是示例输出。输出很大，所以我把它剪掉了，但留得足够多，这样你就可以明白我的意思了：

Element left 0: -, t
Element right 0: *, e
Element left 1: null
Element right 1: null
Element left 2: --, m
Element right 2: null
Element left 3: null
Element right 3: -*, n
Element left 4: ---, o
Element right 4: null
Element left 5: null

. . .

Element right 25: null
Element left 26: null
Element right 26: *-**, l
Element left 27: **--, ö
Element right 27: null
Element left 28: null
Element right 28: **-*, f
Element left 29: ***-, v
Element right 29: null

以下是我用来填充静态数组的文件。因为树中有特殊字符，所以我使用 ASCII 并在读取文件时进行转换：

- 116
-- 109
-* 110
--- 111
--* 103
-*- 107
-** 100
---- 247 
---* 246
--*- 113
--** 122
-*-- 121
-*-* 99
-**- 120
-*** 98
* 101
*- 97
** 105
*-- 119
*-* 114
**- 117
*** 115
*--- 106
*--* 112
*-*- 228
*-** 108
**-- 246
**-* 102
***- 118
**** 104

下面是我用来填充树和链接节点的代码。linkLeftTree() 和 linkRightTree() 是将父节点与其子节点链接的方法。节点在 open() 方法中被读入数组。

package MorseTrees;

import MorseTrees.Nodes.*;
import java.util.*;
import java.io.*;

public class TreePopulater {
    private static final int ALPHABET = 31;
    private static final String alphaRaw = "alphatree2.txt";    
    private static final A_Node[] alphaTree = new AlphaNode[ALPHABET];
    private A_Node aNode;

    public TreePopulater() {
        alphaTree[0] = new AlphaNode("000");
        alphaTree[0].setAlpha('0'); 
        populateRaw(alphaRaw);
    }

    private A_Node[] populateRaw(String treeType)
    {   
        // open and fill static array
        open(treeType);
    }

    private void open(String fileName) {

        //try, catch, etc.
        Scanner in = new Scanner(new File(fileName));
     int counter = 1;

   while (in.hasNextLine()) {
      aNode = new AlphaNode(in.next());
      aNode.setAlpha((char) in.nextInt());
           alphaTree[counter] = aNode;

      counter++;
   }

        linkNodes();
    }

    private void linkNodes() {  
        // force link root node 
        alphaTree[0].setLeft(alphaTree[1]);
        alphaTree[0].setRight(alphaTree[16]);

        linkLeftTree();
        linkRightTree();
        printChildren();
    }

    public void linkLeftTree()
    {
        // link the left, or first half, of the array
        for (int i = 2; i < (alphaTree.length / 2); i++) // or 16
        {   
            alphaTree[i].setLeft(alphaTree[(i++)]);
            alphaTree[i].setRight(alphaTree[(i)]);
        }
    }

    public void linkRightTree()
    {
        // link the right, or second half, of the array
        for (int i = 17; i <= alphaTree.length - 1; i++)
        {
            alphaTree[i].setLeft(alphaTree[(i++)]);
            alphaTree[i].setRight(alphaTree[(i)]);  
        }   
    }

    public void printChildren()
    {
        for (int i = 0; i < alphaTree.length - 1; i++)
        {
            System.out.println("Element left " + i + ": " + alphaTree[i].leftChild());
            System.out.println("Element right " + i + ": " + alphaTree[i].rightChild());
        }   
    }

    public static void main(String[] args)
    {
        TreePopulater tp = new TreePopulater();
    }
}

节点类 AlphaNode 扩展了 A_Node。A_Node 看起来像您所期望的那样：左右子节点的实例变量，莫尔斯电码和与之关联的字母，以及所需的所有 getter 和 setter。

奇怪的是，如果我在 linkLeftTree() 和 linkRightTree() 中的设置器上使用 System.out.println()，我在循环中看不到空值，但当我实际尝试访问子节点时仍然有空值（如例如预订搜索）。

（功劳归于功劳：本程序中实现的字母树是基于 Charles Petzold 在《代码》一书中优化的树。但这里所有的代码都是你写的。）

4

2 回答 2

0

我对以下代码表示怀疑：

   public void linkLeftTree()
    {
        // link the left, or first half, of the array 
        // NOTE: the code runs for i=2,4,8,10,12,14 so many nodes have the left
        //      and right neighbors unassigned
        for (int i = 2; i < (alphaTree.length / 2); i++) // or 16
        {   // NOTE:
            // This should alphaTree[i].setLeft(alphaTree[i+1])
            // Since you are changing the value of i twice 
            // A good idea is to print i and verify the values
            alphaTree[i].setLeft(alphaTree[(i++)]);
            alphaTree[i].setRight(alphaTree[(i)]);
        }
    }

    public void linkRightTree()
    {
        // link the right, or second half, of the array
        //NOTE: the code runs for i=17,19.. so many nodes have the left
        //      and right neighbors unassigned
        for (int i = 17; i <= alphaTree.length - 1; i++)
        {
            // Same as above
            alphaTree[i].setLeft(alphaTree[(i++)]);
            alphaTree[i].setRight(alphaTree[(i)]);  
        }   
    }

我不确定哪些索引特定于您的算法，但我想我回答了您与出现的空值相关的问题。

一切顺利！你自己解决问题真是太好了..:-)

五

于 2012-06-11T02:31:58.870 回答
0

（代表 OP 发布）。

我更改了 printChildren() 方法以打印出父节点，并意识到我将父母自己分配为他们自己的孩子（例如：n 成为 n 的孩子）。在其他情况下，我完全跳过了节点。这是因为我在 for 循环中使用了 i 变量。

下面的代码已经解决了这个问题，并且完全符合我的要求。这是一个可怕的、不优雅的 hack，但是当我回去重构它时，我会想办法让它更干净。解决方案来自 linkLeftTree() 和 linkRightTree() 方法。我意识到我不应该将子节点分配给叶子，所以我减少了在这两种情况下循环通过的节点数量，并使用计数器来分配子节点。

public void linkLeftTree() {    
    int counter = 2;
    int counter2 = 3;

        // link the left, or first half, of the array

    for (int i = 1; i < 8; i++) {   
    alphaTree[i].setLeft(alphaTree[(counter++)]);
    alphaTree[i].setRight(alphaTree[(counter2++)]);

              if (counter <= 13) {
         counter++;
             counter2++;
    }
    }
}

public void linkRightTree() {
    int counter = 16;
    int counter2 = 17;

    // link the right, or second half, of the array
    for (int i = 16; i < (24); i++) {   
        alphaTree[i].setLeft(alphaTree[(counter++)]);
        alphaTree[i].setRight(alphaTree[(counter2++)]);

        if (counter < 29) { 
            counter++;
            counter2++;
        }
    }
}

我的递归搜索和打印也按预期工作，我几乎完成了程序的编写。现在开始清理它的过程。感谢所有花时间看这个的人！

于 2016-09-18T19:14:29.077 回答