java - 如何递归地将列表转换为 BSTree？

Question

我尝试将 3{1{,2{,}},5{4{,},6{,}}} 转换为列表像这样的二叉树

               3
           1       5
             2    4  6

我认为使用递归会更容易，但我陷入困境。

public void ListToTree (ArrayList al) {
    Iterator it = al.iterator(); 
    // n is the Tree's root
    BSTnode n = new BSTnode(it.next());
    recurse(al,it,n); 

}

void recurse (ArrayList al, Iterator it, BSTnode n) {
    if(!it.hasNext()) return;
    Object element = it.next();
    if(element=="{"){
            recurse(al,it,n.left());
            return;
    } else if (element==",") {
            recurse(al,it,n.right());
            return;
    } else if (element =="}") {

    }

}

我不知道如何继续，想知道这是否是正确的道路。请给我一些如何解决它的提示。此外，我意识到我经常陷入递归问题。是因为我总想把它拆散吗？我应该自上而下思考并仔细检查它是否正确吗？提前致谢!

Answer 1

首先:你是否受限于那个可怕的列表表示？您可以使用以下代码轻松地根据 BST 规则构建 BST:

void insert(Node n, int value) {
     if(n == null) {
           n = new Node(value);
     } else if(value < n.value) {
           if(n.left == null) {
               n.left = new Node(value);
               return;
           }
           insert(n.left, value);
     } else if(value > n.value) {
           if(n.right == null) {
                n.right = new Node(value);
                return;
           }
           insert(n.right, value);
     }
}

您确实不必传递迭代器。只需使用列表中的值即可。此外，通常不建议在方法签名中使用实现类型。 (即 ArrayList -> 列表)。
这里的另一个大错误是你不使用 == 进行值比较，即进行引用比较。使用 equals 代替，但您应该在实例化测试后向下转换对象，例如:

if( element instanceof String) {
    String seperator = (String)element;
    if("{".equals(separator))
         //do sth...

顺便说一句，代码中缺少的是实际插入和向后导航。
通过使用 {-s 和 ,-s 导航找到正确的子树后，检查该元素是否为 Integer，然后将其设置为当前节点的值。向后导航应该在 } 分支中，通过从递归和一些技巧返回一级或调用实际节点的父节点上的方法。
但我不建议您遵循这个方向，仅使用列表中的值和简单的插入方法要容易得多。