Я пытаюсь распечатать диаграмму дерева выражений для инфиксного выражения. У меня уже есть методы, которые выполняют преобразование инфиксных выражений в post и prefix и возвращают их в виде строк. Я ожидаю, что выходные данные для выражения «1 + 3 - 6 ^ 7 * 5» следующие:
-
+ *
1 3 ^ 5
6 7
Печать предварительного заказа, пост-заказа и обхода не дает мне правильного результата. Он пересекает дерево / печатает содержимое дерева, но не различает guish между операторами и операндами. Есть ли способ отредактировать эти обходы, чтобы правильно распечатать дерево выражений (т. Е. С интервалом, как в примере выше), или мне нужно сделать новую функцию оператора обхода / печати, которая находит узел root (в в этом случае "-"), а затем устанавливает операторы в качестве корней, а операнды в качестве конечных узлов. Как сообщить функции, какой оператор в выражении является оператором root (например, «-» в приведенном выше примере), и обработать остальное как корни для поддеревьев?
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, введя их методы