Как я могу вставить строку в BST и проверить его действительность JAVA? - PullRequest
Новая
       20

Как я могу вставить строку в BST и проверить его действительность JAVA?

0 голосов
/ 16 мая 2019

Я должен вернуть true или false, если входная строка является действительным или недействительным BST (бинарное дерево поиска).

Проблема в том, что у меня на входе нетипичная строка с этим "шаблоном": (ROOT (LEFT, RIGHT)); между каждым элементом есть пробел, ROOT - это центральный узел, слева - слева, а справа - справа. Если узел имеет нулевое значение, кодируется как «-», лист кодируется числовым значением, если узел, имеющий некоторый дочерний элемент, кодируется следующим образом: например, B имеет два дочерних элемента (D слева, E справа), поэтому ( A (B (D, E), C))

Я пытался разбить строку в массиве String, но я понятия не имею, как заполнить дерево, и в то же время проверить, является ли это BST. Как я могу заполнить дерево не по порядку, а как строка говорит с этим вводом String?

Я бы попробовал с этим алгоритмом: 

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Stack;

     //Java implementation to check if given Binary tree 
     //is a BST or not 

    /* Class containing left and right child of current 
        node and key value*/
    class  Node {
        int data;
        Node left, right;

    public Node(int item) {
    data = item;
    left = right = null;
        }
       }

         public class BinaryTree {

       // Root of the Binary Tree
       Node root;

    /*
   * can give min and max value according to your code or can write a 
     function to
     * find min and max value of tree.
    */

    /*
 * returns true if given search tree is binary search tree (efficient 
  version)
 */
  boolean isBST() {
    return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

/*
 * Returns true if the given tree is a BST and its values are >= min and <= max.
 */
       boolean  isBSTUtil(Node node, int min, int max) {
    /* an empty tree is BST */
    if (node == null)
        return true;

       /* false if this node violates the min/max constraints */
        if (node.data < min || node.data > max)
              return false;

    /*
     * otherwise check the subtrees recursively tightening the min/max 
     constraints
     */
    // Allow only distinct values
    return (isBSTUtil(node.left, min, node.data - 1) && 
    isBSTUtil(node.right, node.data + 1, max));
   }
   public static Node insert(Node root, int key)
   {
    // if the root is null, create a new node an return it
    if (root == null) {
        return new Node(key);
    }

    // if given key is less than the root node,
    // recur for left subtree
    if (key < root.data) {
        root.left = insert(root.left, key);
    }

    // else recur for right subtree
    else {
        // key >= root.data
        root.right = insert(root.right, key);
    }

    return root;
}

     /* Driver program to test above functions */
     public static void main(String args[]) throws 
     FileNotFoundException,IOException
     { 

    BufferedReader b = new BufferedReader(new 
    FileReader("Input1Es2.txt"));
    String[] treesStrings = b.readLine().replaceAll("[^0-9-, 
     ()]","").split(",|(?<=\\()|(?=\\()|(?<=\\))|(?=\\))");
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(4); 
    tree.root.left = new Node(3); 
    tree.root.right = new Node(5); 
    tree.root.left.left = new Node(1); 
    tree.root.left.right = new Node(3);


   if (tree.isBST()) 
   System.out.println("IS BST"); 
   else
   System.out.println("Not a BST"); 







       } 
    }

Я пытался вставить вручную, и это работает, но я не понимаю, как автоматизировать вставку узлов и в то же время проверить правильность.

ВХОД 1: (100 (19 (17 (2, 7), 3), 36 (25, 1)))

ВЫХОД 1: не BST

ВХОД 2: (8 (3 (1, 6 (4, 7)), 10 (-, 14 (13, -))))

ВЫХОД 2: BST

...