java - 打印表达式树

Question

我正在尝试为中缀表达式打印表达式树图。我已经有了将中缀表达式转换为 post 和 prefix 并将它们作为字符串返回的方法。我期望表达式“1 + 3 - 6 ^ 7 * 5”的输出如下

              -
        +           *
    1      3     ^     5
                6  7

Preorder、Postorder 和中序遍历打印似乎没有给我正确的结果。它遍历树/打印树的内容，但不区分运算符和操作数。有没有办法编辑这些遍历以以正确的方式打印出表达式树（即，像上面的示例一样使用间距），或者我是否需要创建一个新的遍历/打印语句函数来查找根节点（在这种情况下“-”），然后将运算符设置为根，将操作数设置为叶节点。如何让函数知道表达式中的哪个运算符是根运算符（例如，上例中的“-”）并将其余的视为子树的根？

import java.util.Iterator;
import java.util.Stack;

/**
 * Binary Tree.
 */


public class DDBinaryTree<E>{

    protected Node<E> root;

    /**
     * Constructs an empty binary tree.
     */
    public DDBinaryTree() {

    }

    /**
     * Constructs a binary tree with given data in the root and the specified left and right
     * subtrees.
     *
     * @param data The data to store in root.
     * @param leftTree The left subtree.
     * @param rightTree The right subtree.
     */
    public DDBinaryTree(E data, DDBinaryTree<E> leftTree, DDBinaryTree<E> rightTree) {
        root = new Node<E>(data);
        if (leftTree!=null) {
            root.left = leftTree.root;
        }
        if (rightTree!=null) {
            root.right = rightTree.root;
        }
    }

    /**
     * Constructs a binary tree with a given node as its root.
     * @param root The root of the binary tree.
     */
    protected DDBinaryTree(Node<E> root) {
        this.root = root;
    }

    /**
     * Gets the left subtree of this tree.
     * @return The left subtree, or null if it doesn't exist.
     */
    public DDBinaryTree<E> getLeftSubtree() {
        if (root!=null && root.left!=null) return new DDBinaryTree<E>(root.left);
        else return null;
    }

    /**
     * Gets the right subtree of this tree.
     * @return The right subtree, or null if it doesn't exist.
     */
    public DDBinaryTree<E> getRightSubtree() {
        if (root!=null && root.right!=null) return new DDBinaryTree<E>(root.right);
        else return null;
    }

    /**
     * Gets the data from the root node.
     * @return The data from the root, or null if tree is empty.
     */
    public E getData() {
        if (root!=null) return root.data;
        else return null;
    }

    /**
     * Checks if tree is empty
     * @return true if root is null, and false otherwise
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Checks if tree is a leaf.
     * @return true if this tree is a leaf, and false otherwise.
     */
    public boolean isLeaf() {
        return root != null && root.left == null && root.right == null;
    }

    /**
     * Performs a preorder traversal, executing the specified operation
     * on the data in each node it visits.
     *
     * @param visitOperation An operation to apply to the data of each visited node.
     */
    protected void preOrderTraversal(ProcessData<E> visitOperation) {
        preOrderTraversal(root, visitOperation);
    }

    private void preOrderTraversal(Node<E> node, ProcessData<E> visitOperation) {
        if (node==null) return;
        visitOperation.process(node.data);
        preOrderTraversal(node.left, visitOperation);
        preOrderTraversal(node.right, visitOperation);
    }

    /**
     * Performs a postorder traversal, executing the specified operation
     * on the data in each node it visits.
     *
     * @param visitOperation An operation to apply to the data of each visited node.
     */
    protected void postOrderTraversal(ProcessData<E> visitOperation) {
        postOrderTraversal(root, visitOperation);
    }

    private void postOrderTraversal(Node<E> node, ProcessData<E> visitOperation) {
        if (node==null) return;
        postOrderTraversal(node.left, visitOperation);
        postOrderTraversal(node.right, visitOperation);
        visitOperation.process(node.data);
    }

    /**
     * Performs a inorder traversal, executing the specified operation
     * on the data in each node it visits.
     *
     * @param visitOperation An operation to apply to the data of each visited node.
     */
    protected void inOrderTraversal(ProcessData<E> visitOperation) {
        inOrderTraversal(root, visitOperation);
    }

    private void inOrderTraversal(Node<E> node, ProcessData<E> visitOperation) {
        if (node==null) return;
        if (node.left != null && visitOperation instanceof PrePostProcess){
            ((PrePostProcess<E>)visitOperation).pre();

        }

        inOrderTraversal(node.left, visitOperation);
        visitOperation.process(node.data);
        inOrderTraversal(node.right, visitOperation);

        if (node.right != null && visitOperation instanceof PrePostProcess){
            ((PrePostProcess<E>)visitOperation).post();
        }
    }

    protected interface ProcessData<E> {
        void process(E data);
    }

    protected interface PrePostProcess<E> extends ProcessData<E> {
        void pre();
        void post();
    }

    protected static class Node<E> {
        protected E data;
        protected Node<E> left;
        protected Node<E> right;

        /**
         * Constructs a Node containing the given data.
         * @param data Data to store in node
         */
        public Node(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

}


import java.util.Iterator;
import java.util.Stack;

/**
 * Binary Search Tree
 */
public class DDBinarySearchTree<E extends Comparable<E>> extends DDBinaryTree implements Iterable<E> {
    static final int COUNT = 5;

    /**
     * Searches tree for target.
     *
     * @param target The element to look for.
     * @return true if in tree, and false otherwise
     */
    public boolean contains(E target) {
        return contains(root, target);
    }

    /**
     * Adds target to tree if it doesn't already exist.
     *
     * @param target The element to add.
     * @return true if target added and false otherwise.
     */
    public boolean add(E target) {
        if (root == null) {
            root = new Node<E>(target);
            return true;
        }
        return add(root, target);
    }

    /**
     * Output contents in order.
     */
    public void printOrderedData() {
        inOrderTraversal(new ProcessData<E>() {
            @Override
            public void process(E data) {
                System.out.print(data + " ");
            }
        });
    }

    private boolean contains(Node<E> subtreeRoot, E target) {
        if (subtreeRoot == null) return false;
        if (target.compareTo(subtreeRoot.data) == 0) return true;
        else if (target.compareTo(subtreeRoot.data) < 0)
            return contains(subtreeRoot.left, target);
        else
            return contains(subtreeRoot.right, target);
    }


    private boolean add(Node<E> subtreeRoot, E target) {
        if (target.compareTo(subtreeRoot.data) == 0) return false;
        else if (target.compareTo(subtreeRoot.data) < 0) {
            if (subtreeRoot.left == null) {
                subtreeRoot.left = new Node<E>(target);
                return true;
            }
            return add(subtreeRoot.left, target);
        } else {
            if (subtreeRoot.right == null) {
                subtreeRoot.right = new Node<E>(target);
                return true;
            }
            return add(subtreeRoot.right, target);
        }
    }

}




public class Tester {


    public static void main(String[] args) {

        DDBinarySearchTree<Integer> integerSearchTree = new DDBinarySearchTree<>();
        DDBinarySearchTree<String> stringSearchTree = new DDBinarySearchTree<>();

        String stringToSplit = "1 + 3 - 6 ^ 7 * 5";

        //Splits up string and adds to stringSearchTree
        for (String str : stringToSplit.split(" ")) {
            stringSearchTree.add(str);
        }

        stringSearchTree.printOrderedData();


    }
}

在 printOrderedData 方法中，您可以通过键入它们的方法将遍历类型从 inorder 更改为 pre/postorder

标签： javabinary-treebinary-search-treeexpression-treesrecursive-datastructures