I am trying to create a parse tree for prefix expressions. The Nodes created have a parent pointer, and a Boolean identifying operators.
My issue is, once i get to 6(The end of the left side of the tree) The root pointer remains as 15. So the array continues to get smaller, but the recursion never travels back up to the original root, in order to populate the right side of the tree.
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);
}
}
TreeNode class
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");
}
}
}
}
CodePudding user response：
Okay, I gave up on your solution and implemented my version for it.
You had some cycles in your graph, because sometimes one if your TreeNodes would reference itself or its parent as its left. My method getMaxWidthOfChildren() will showcase that and is compatible with your code. So you could use it in your code to see the problems.
But there's another problem involved: Once you have to iterate upwards more than one step, your 'array indexing' (or in your case: removing the first array element from the array on EACH call) gets out of step. You remove too many elements, and thus lose the elements and track of the remaining cells.
Now to my solution:
- this is more straightforward, because it is naturally recursive, exactly matching the intent of your (depth-first) first-order logic, and each constructor decides and acquires the needed data for itself.
- The big trick here is - analogous to advancing an index on an array - to use a
Stack, here in the form of aLinkedList. (The java.util.Stack is thread-safe, which is not needed here, so I use its modern counterpartLinkedList) - Also, you can input the whole data string again, without any artificial additional notes and variables.
So construction was really easy, but getting the toString() method implemented properly was a bit of a struggle.
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);
}
}