我正在嘗試為前綴運算式創建一個決議樹。創建的節點有一個父指標和一個布爾標識運算子。
我的問題是，一旦我到達 6（樹左側的末尾） 根指標仍然為 15。 所以陣列繼續變小，但遞回永遠不會回到原始根，以便填充樹的右側。
public class demo {
public static void main(String[] args){
String[] in = {"3","*","4","*","15", "6"," ","/","14","3","*","65","5"};
TreeNode root = new TreeNode(" ");
TreeNode nuw = new TreeNode("-");
System.out.println(root.data);
populate(in,root,nuw);
}
public static TreeNode populate(String[] array, TreeNode root, TreeNode nuw){
TreeNode current = root;
String[] copy = new String[array.length-1];
System.arraycopy(array, 1, copy, 0, array.length-1);
TreeNode next = new TreeNode(copy[0]);
if(current==null){
return null;
}
if(current.left==null && !nuw.operator){
current.left=nuw;
nuw.parent = current;
}else if(current.left!=null && current.right==null && !nuw.operator){
current.right = nuw;
nuw.parent = current;
}else if(nuw.operator && current.left==null){
current.left=next;
next.parent=current;
current=next;
}else if(nuw.operator && current.left!=null && current.right==null){
current.right=next;
next.parent=current;
current=next;
}else if(current.right!=null && current.left!=null){
current = current.parent;
}
for(int i=0;i<array.length;i )System.out.print(array[i]);
System.out.println("\n current: " current.data);
System.out.println("next: " next.data);
return populate(copy,current,next);
}
}
樹節點類
public class TreeNode {
protected String data;
protected boolean operator;
protected TreeNode left,right,parent;
public TreeNode(String x){
this.left = null;
this.right = null;
this.parent = null;
if(x.equals(" ")||x.equals("-")||x.equals("*")||x.equals("/")||x.equals("%")){
this.operator=true;
this.data=x;
}else{
try{
Integer.parseInt(x);
this.data=x;
this.operator=false;
}catch(NumberFormatException e){
System.out.println("Invalid Input");
}
}
}
}
uj5u.com熱心網友回復：
好的，我放棄了您的解決方案并為此實施了我的版本。
您的圖中有一些回圈，因為有時如果您TreeNode的 s 會將其自身或其父級參考為其left. 我的方法getMaxWidthOfChildren()將展示這一點并與您的代碼兼容。因此，您可以在代碼中使用它來查看問題。
但是還涉及另一個問題：一旦您必須向上迭代不止一個步驟，您的“陣列索引”（或者在您的情況下：在每次呼叫時從陣列中洗掉第一個陣列元素）就會失步。您洗掉了太多元素，從而丟失了剩余單元格的元素和軌跡。
現在到我的解決方案：
- 這更直接，因為它自然是遞回的，完全符合您的（深度優先）一階邏輯的意圖，并且每個建構式自己決定并獲取所需的資料。
- 這里的大技巧是 - 類似于在陣列上推進索引 - 使用 a
Stack，這里以 a 的形式LinkedList。（java.util.Stack 是執行緒安全的，這里不需要，所以我使用它的現代版本LinkedList） - 此外，您可以再次輸入整個資料字串，而無需任何人為的附加注釋和變數。
所以構建真的很容易，但是要toString()正確實施該方法卻有點困難。
package stackoverflow;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
public class PopulateTree {
static public class TreeNode {
protected String data;
protected boolean isOperator;
protected TreeNode left, right, parent;
public TreeNode(final LinkedList<String> pQueue, final TreeNode pParent) {
data = pQueue.poll();
isOperator = isOperator(this.data);
parent = pParent;
left = isOperator ? new TreeNode(pQueue, this) : null;
right = isOperator ? new TreeNode(pQueue, this) : null;
}
// it's likely we need this functionality method somewhere else, too, so we put it in its own method
// also, it makes the CTOR so much shorter and its use obvious
static public boolean isOperator(final String pString) {
return pString.equals(" ") || pString.equals("-") || pString.equals("*") || pString.equals("/") || pString.equals("%");
}
public int getMaxWidthOfChildren() {
return getMaxWidthOfChildren(new HashSet<>());
}
private int getMaxWidthOfChildren(final HashSet<TreeNode> pAlreadyVisitedNodes) {
if (pAlreadyVisitedNodes.contains(this)) {
System.out.println("Error: recursive loop for " this.data);
return 0;
} else {
pAlreadyVisitedNodes.add(this);
}
int ret = 1;
if (left != null) ret = left.getMaxWidthOfChildren(pAlreadyVisitedNodes);
if (right != null) ret = right.getMaxWidthOfChildren(pAlreadyVisitedNodes);
return ret;
}
public int getMaxDepth() {
final int l = left == null ? 0 : left.getMaxDepth();
final int r = right == null ? 0 : right.getMaxDepth();
return 1 Math.max(l, r);
}
@Override public String toString() {
final int maxDepth = getMaxDepth();
System.out.println("maxDepth: " maxDepth);
final int maxWidth = (int) (Math.pow(2, maxDepth - 2) * 2 - 1);
System.out.println("maxWidth: " maxWidth);
final String[][] out = new String[maxDepth][maxWidth];
// fill array with data
final int center = maxWidth / 2;
fillArray(out, maxWidth, center, this, 0);
// form array into String
final StringBuilder sb = new StringBuilder();
for (int y = 0; y < out.length; y ) {
for (int x = 0; x < out[y].length; x ) {
final String dat = out[y][x];
final String text = dat == null ? "" : dat;
sb.append(text "\t");
}
sb.append("\n");
}
return sb.toString();
}
private void fillArray(final String[][] pOut, final int pWidth, final int pCenter, final TreeNode pTreeNode, final int pLineIndex) {
if (pTreeNode == null) return;
System.out.println("Filling: w=" pWidth "\tc=" pCenter "\tl=" pLineIndex);
pOut[pLineIndex][pCenter] = pTreeNode.data;
final int newWidth = pWidth / 2;
final int leftCenter = pCenter - newWidth / 2 - 1;
final int rightCenter = pCenter newWidth / 2 1;
fillArray(pOut, newWidth, leftCenter, pTreeNode.left, pLineIndex 1);
fillArray(pOut, newWidth, rightCenter, pTreeNode.right, pLineIndex 1);
}
}
public static void main(final String[] args) {
final String[] in = { "-", " ", "3", "*", "4", "*", "15", "6", " ", "/", "14", "3", "*", "65", "5" };
final LinkedList<String> queue = new LinkedList<>(Arrays.asList(in));
final TreeNode root = new TreeNode(queue, null);
System.out.println();
System.out.println("Printing Root Node:");
System.out.println(root);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/470926.html
上一篇：使用遞回去除二叉搜索樹