从字符串数组递归创建二叉解析树

Question

我正在尝试为前缀表达式创建解析树。创建的节点有一个父指针和一个布尔标识运算符。

我的问题是，一旦我到达 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);
    }
}

树节点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");
            }
        }
    }
}

Answer 1

好的，我放弃了你的解决方案并为它实现了我的版本。

您的图表中有一些循环，因为有时如果您的 TreeNode 会引用自身或其父项作为其 left。我的方法 getMaxWidthOfChildren() 将展示这一点并与您的代码兼容。所以你可以在你的代码中使用它来查看问题。

但是还涉及另一个问题：一旦您必须向上迭代不止一个步骤，您的 'array indexing'（或者在您的情况下：在 EACH 调用中从数组中删除第一个数组元素）就会失步.您删除了太多元素，因此丢失了剩余单元格的元素和轨迹。

现在我的解决方案：

这更直接，因为它是自然递归的，完全符合你的（depth-first）first-order逻辑的意图，每个构造函数自己决定并获取所需的数据。
这里的大技巧是 - 类似于在数组上推进索引 - 使用 Stack，这里是 LinkedList 的形式。（java.util.Stack 是 thread-safe，这里不需要，所以我使用它的现代对应物 LinkedList）
另外，您可以将整个数据串重新输入，无需任何人为的附加注释和变量。

所以构造真的很容易，但是要正确实现 toString() 方法有点困难。

package Whosebug;

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);
    }



}

从字符串数组递归创建二叉解析树

Recursively creating a binary parse tree from an array of strings

java

algorithm

recursion

parsing

binary-tree