停留在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 *

回答

相关问题