我正在編寫一個程序,轉換爲莫爾斯碼或反之亦然。我使用樹來更有效地搜索代碼或相關值。莫爾斯和相關的值從文件讀入靜態數組。索引0是所有其他子樹的根,實際上是一個鏈接到左子樹(索引[1])和右子樹(索引[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看起來像你所期望的那樣:左右兒童的實例變量,莫爾斯電碼和與之相關的字母以及所需的所有獲取者和設置者。如果我在linkLeftTree()和linkRightTree()中的setter上使用System.out.println(),我在循環中看不到任何空值,但當我實際嘗試訪問子節點時仍然沒有空值節點(例如,像在預先搜索中那樣)。
(信貸,信貸是由於:。在這個計劃實施的字母樹基於查爾斯Petzold的書中,「代碼」優化樹但是,所有的代碼在這裏被你真正寫的)
無法回答的問題。您沒有顯示構建樹的代碼。但是,除非節點的數量是2的冪,否則你總是會在二叉樹中「缺少」子節點。我也很好奇你爲什麼不使用內建的Java集合類,或者說Collections.binarySearch))。 – EJP
對不起!我將編輯我的問題以添加該代碼。而且我不使用內置代碼,因爲我想嘗試自己實現這一點,如果這是有道理的。 – Mims
爲什麼節點0的右側子樹在索引16處,但是每個其他節點的右側子樹在索引* N + 1 *處是* N *?這沒有任何意義。 – EJP