Как мне теперь «построить» дерево с помощью сканера? (объяснение после кода)

Question

Назначение предназначено, чтобы помочь понять и практиковать концепции деревьев и обход. Я должен использовать дерево для оценки выражения в префиксной (полированной) нотации, а также для печати выражения в постфиксной (обратной польский) нотации и инфиксной нотации.

Вот класс оценки, который был предоставлен.

import java.util.*; 
public class Evaluation 
{ 
public static void main(String[] args) 
{ 
    System.out.print("Enter a prefix expression: "); 
    Scanner scanner = new Scanner(System.in); 

    // build an expression tree 
    Node root = buildTree(scanner); 

    // print prefix expression 
    System.out.println("prefix expression:"); 
    preorder(root); 
    System.out.println(); 

    // print postfix expression 
    System.out.println("postfix expression:"); 
    postorder(root); 
    System.out.println(); 

    // print infix expression 
    System.out.println("infix expression:"); 
    inorder(root); 
    System.out.println(); 

    // evaluate the expression using postfix 
    System.out.println("Result = " + evaluate(root)); 
} 

// build an expression tree and return the root node of the tree 
public static Node buildTree(Scanner sc) 
{ 
    // your code here 

} 

// Postfix expression is the result of a post-order traversal 
public static void postorder(Node node) 
{ 
    // your code here 

} 

// Prefix expression is the result of a pre-order traversal 
public static void preorder(Node node) 
{ 
    // your code here 

} 

// Infix expression is the result of a in-order traversal 
public static void inorder(Node node) 
{ 
    // your code here 

} 

// Evaluate the expression tree using postorder traversal 
public static int evaluate(Node node) 
{ 
    // your code here 

} 
} 

EDIT: Вот класс Node, который мне пришлось написать.

public class Node { 
String value; 
Node left, right; 

Node(String value){ 
    this.value = value; 
} 

Node(String value, Node left, Node right){ 
    this.left = left; 
    this.right = right; 

} 

public boolean isLeaf(){ 
    if() 

    return true; 
} 

} 

Инструкции по заданию должны были использовать данный метод buildTree построить дерево и оценить 4 заданные выражения в префиксной нотации:

1.- + 10 * 2 8 3

2 ./ * + 3 14 2 7

3. + + 4 2 * 3 - 15 1

4./-% + 1 2 3 6 + 2 3

EDIT: в предыдущем задании мне приходилось оценивать выражения Postfix с использованием стека, но как бы я мог построить и пройти через это дерево для оценки префиксных выражений? (Я предполагаю, что операнды и операторы будут значением узлов, а затем узлы каким-то образом свяжутся.)

Answer 1

Ну, давайте подумаем об этом. Что делает узел листом?

Я бы сказал, что лист - это узел без детей. Итак, как насчет использования следующего булевого выражения для вашего if check: if(left == null && right == null)?

LATER EDIT: на самом деле вам даже не нужна проверка if. Вы можете поместить это просто нравится

public boolean isLeaf(){ 
    return left == null && right == null; 
} 

Кроме того, следует помнить, что ваш перегруженный конструктор

Node(String value, Node left, Node right){ 
    this.left = left; 
    this.right = right; 

} 

не правильно назначая value.

Answer 2

Я ожидал бы, что если это листовой узел, он не будет иметь ссылок на другие узлы, следовательно, левый узел, а правый узел будет пустым. Вы можете использовать это, чтобы проверить, является ли он листовым узлом, применяя проверку для обоих и возвращая true, если оба узла ссылаются на нуль.

if(left == null && right == null) 
    return true; 
else 
    return false;