停留在binarysearchtree实现* Java *

  • Z时代
  • 2024-01-10
  • 分类：问答

我在做我的任务，最后一个问题让我写一个使用二进制搜索树的程序。 您将从输入中读取一系列字符， 表示二叉搜索树的前序遍历。您需要从 这个序列中恢复二叉搜索树的原始形状，并以横向（如下图所示）和顺序方式打印出树的内容。停留在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

一些详细的解释将不胜感激:)谢谢。

回答：

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

以上是 停留在binarysearchtree实现* Java * 的全部内容， 来源链接： utcz.com/qa/258145.html

回到顶部