停留在binarysearchtree實現* Java *

我在做我的任務，最後一個問題讓我寫一個使用二進制搜索樹的程序。您將從輸入中讀取一系列字符，表示二叉搜索樹的前序遍歷。您需要從這個序列中恢復二叉搜索樹的原始形狀，並以橫向（如下圖所示）和順序方式打印出樹的內容。停留在binarysearchtree實現* Java *

Ipublic類PrintSideways {

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>();

這是我收到的骨架代碼和我增加了例外線給它。我並不確定如何啓動此代碼，因爲我在二元搜索樹上很弱。具體來說，我沒有得到如何在參數中使用StringItem方法。這是提供的StringItem方法。

public class StringItem extends KeyedItem<String> {  

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

一些詳細的解釋將不勝感激:)謝謝。

來源

2014-02-15 Andy

我相信你會找到一些很好的例子，如果它只是谷歌 – fmodos

我完成編碼後綴到Postfix轉換器/計算器，並得到了這個問題。我沒有得到的一件事是將樹打印爲橫向輸出。我該怎麼做.. – Andy

谷歌DFS和BFS – Bohemian

以下是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);

來源

2014-02-15 08:12:31 korhner

感謝您的解釋:)。但我想我會放棄這個問題，因爲我沒有太多時間了。我需要從二叉樹的基礎知識重新開始。 – Andy

停留在binarysearchtree實現* Java *

回答

相關問題