Java двоичное дерево, введенное в определенном порядке

Question

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

Например: "((3 (4)) 7 ((5) 9))"

бы быть введены в виде дерева с 7 в качестве корневого, 3 и 9, как дети, и 4, как правым ребенком 3 лет и 5 в качестве левого ребенка от 9.

Мой код ниже .. Проблема, с которой я сталкиваюсь, заключается в том, что, поскольку я основываю свои проверки на поиске правой скобки, я не уверен, как чтобы получить элементы правильно, если они не находятся непосредственно перед скобками, например 3 в приведенной выше строке. Любое направление будет высоко ценится ..

class Node { 
     int value; 
     Node left, right; 
    } 

class BST { 

public Node root; 

// Add Node to Tree 
public void add(int n) { 
    if (root == null) { 
     root = new Node(); 
     root.value = n; 
    } 
    else { 
     Node marker = root; 
     while (true) { 
      if (n < marker.value) { 
       if (marker.left == null) { 
        marker.left = new Node(); 
        marker.left.value = n; 
        break; 
       } else { 
        marker = marker.left; 
       } 
      } else { 
       if (marker.right == null) { 
        marker.right = new Node(); 
        marker.right.value = n; 
        break; 
       } else { 
        marker = marker.right; 
       } 
      } 
     } 
    } 
} // End ADD 

//Find Height of Tree 
public int height(Node t) { 
    if (t.left == null && t.right == null) return 0; 
    if (t.left == null) return 1 + height(t.right); 
    if (t.right == null) return 1 + height(t.left); 
    return 1 + Math.max(height(t.left), height(t.right)); 
} // End HEIGHT 

// Check if string contains an integer 
public static boolean isInt(String s) { 
    try { 
     Integer.parseInt(s); 
    } 
    catch(NumberFormatException e) { 
     return false; 
    } 
     return true; 
} // End ISINT 

public int elementCount(String[] a) { 
    int count = 0; 
    for (int i = 0; i < a.length; i++) { 
     if (isInt(a[i])) count++; 
    } 
    return count; 
} 

} // End BST Class 

public class Depth { 

public static void main(String[] args) { 
    String[] a = args[0].split(" "); 
    BST tree = new BST(); 
    int[] bcount = new int[10]; 
    int[] elements = new int[10]; 
    int x = 0, bracketcount = 0; 

    // Display entered string 
    System.out.print("Entered Format: "); 
    for (int j=0; j < a.length; j++) { 
     System.out.print(a[j]); 
    } 

    for (int i=0; i < a.length; i++) { 
     char c = a[i].charAt(0); 
     switch (c) 
     { 
      case '(': 
       bracketcount++; 
       break; 
      case ')': 
       if (isInt(a[i-1])) { 
        bcount[x] = bracketcount--; 
        elements[x++] = Integer.parseInt(a[i-1]); 
       } 
       break; 
      case '1': 
      case '7': 
      default : // Illegal character 
       if ((a[i-1].charAt(0) == ')') && (a[i+1].charAt(0) == '(')) { 
        bcount[x] = bracketcount; 
        elements[x++] = Integer.parseInt(a[i]); 
       } 
       break; 
     } 
    } 

    System.out.println("\nTotal elements: " + tree.elementCount(a)); 
    // Display BracketCounts 
    for (int w = 0; w < x; w++) { 
     System.out.print(bcount[w] + " "); 
    } 
    System.out.println(" "); 
    // Display Elements Array 
    for (int w = 0; w < x; w++) { 
     System.out.print(elements[w] + " "); 
    } 

    System.out.println("\nDepth: " + tree.height(tree.root)); 


    // Build the tree 
    for (int y = 0; y < x-1; y++) { 
     for (int z = 1; z < tree.height(tree.root); z++) { 
      if (bcount[y] == z) { 
       tree.add(elements[y]); 
      } 
     } 
    } 
} // End Main Function 

public static boolean isInt(String s) { 
    try { 
     Integer.parseInt(s); 
    } 
    catch(NumberFormatException e) { 
     return false; 
    } 
     return true; 
} 

} // End Depth Class 

Answer 1

Я хотел бы сделать несколько заявлений, чтобы получить доступ к дереву с такой формой:

Для ввода строки: вход = «((3 (4)) 7 ((5) 9))»

Вы можете сделать:

public class Trial { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     String input = "((3(4))7((5)9))"; 

     String easier = input.replaceAll("\\(\\(", ""); 
     String evenEasier = easier.replaceAll("\\)\\)", ""); 
     System.out.println(evenEasier); 

     int firstVal = Integer.parseInt(evenEasier.substring(0, 1)); 


     int firstBracketVal = Integer.parseInt(evenEasier.substring(2, 3)); 

     int middleVal = Integer.parseInt(evenEasier.substring(3, 4)); 

     int secondBracketVal = Integer.parseInt(evenEasier.substring(4,5)); 

     int lastVal = Integer.parseInt(evenEasier.substring(6)); 

     System.out.println("First Val:"+firstVal); 
     System.out.println("First bracket Val:"+firstBracketVal); 
     System.out.println("Middle Val:"+middleVal); 
     System.out.println("Second Bracket Val:"+secondBracketVal); 
     System.out.println("Last Val:"+lastVal); 

    } 

} 

Это, однако, будет работать только для записей в этом определенном формате, если это изменить, или длина из вход идет вверх - это будет работайте немного или сломайте ..... Если вам нужно иметь возможность обрабатывать более сложные деревья в качестве входных данных в этом формате, потребуется немного больше мысли о том, как лучше всего обрабатывать и конвертировать в ваш внутренний формат для обработки.

Answer 2

псевдокод:

function getNode(Node) 
    get one char; 
    if (the char is "(") 
     getNode(Node.left); 
     get one char; 
    end if; 

    Node.value = Integer(the char); 

    get one char; 
    if (the char is "(") 
     getNode(Node.right); 
     get one char; 
    end if; 
    //Now the char is ")" and useless. 
end function 

Перед вызовом этой функции, вы должны получить "(" первая

---

В этом методе framwork узла в строке является «[LeftChild или. NULL] [rightchild или NULL]) ".
"(" не принадлежит узлу, но ")" есть.