Застрял в реализации binarysearchtree * Java *

Question

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

PrintSideways класса Ipublic {

public static void main(String[] args) { 

    if(args.length == 0 || args[0].length() == 0) 
    { 
     throw new IllegalArgumentException ("This is an invalid argument"); 
    } 




    String chars = args[0]; 

    BinarySearchTree<StringItem, String> bst = new BinarySearchTree<StringItem, String>(); 

Это скелет код, который я получил, и я добавил строку исключения к нему. Я не уверен, как начать этот код, потому что я слабый на binarysearchtrees. В частности, я не понимаю, как использовать метод StringItem в параметре. Это метод StringItem.

public class StringItem extends KeyedItem<String> {  

    public StringItem(String str) {  
    super(str);  
    }  
    public String toString(){  
    return getKey()+"";  
}  
} // end StringItem  

Некоторые подробные объяснения были бы очень благодарны :) Спасибо.

Answer 1

Вот краткая реализация на C#, но вам все равно нужно настроить ее для удовлетворения потребностей ваших структур. Вы все равно должны получить представление алгоритма или если у вас есть проблемы, я могу попытаться объяснить:

private BinaryTreeNode<int> ReconstructPreorderRecursive(List<int> inorder, List<int> preorder, int inorderStart, int inorderEnd) 
    { 
     BinaryTreeNode<int> root = new BinaryTreeNode<int>(); 

     root.Value = preorder[preorderIndex]; 

     int index = inorder.IndexOf(preorder[preorderIndex]); 
     //left subtree 
     if (index > inorderStart) 
     { 
      preorderIndex++; 
      root.LeftChild = ReconstructPreorderRecursive(inorder, preorder, inorderStart, index - 1); 
      if (root.LeftChild != null) 
       root.LeftChild.Parent = root; 

     } 

     //right subtree 
     if (index < inorderEnd) 
     { 
      preorderIndex++; 
      root.RightChild = ReconstructPreorderRecursive(inorder, preorder, index + 1, inorderEnd); 
      if (root.RightChild != null) 
       root.RightChild.Parent = root; 

     } 





     return root; 
    } 

Использование:

newTree.Root = ReconstructPreorderRecursive(lstInorder, lstPreorder, 0, lstInorder.Count - 1);