我尝试将 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 =="}") {
}
}
我不知道如何继续,想知道这是否是正确的道路。请给我一些如何解决它的提示。此外,我意识到我经常陷入递归问题。是因为我总想把它拆散吗?我应该自上而下思考并仔细检查它是否正确吗?提前致谢!
最佳答案
首先:你是否受限于那个可怕的列表表示?您可以使用以下代码轻松地根据 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,然后将其设置为当前节点的值。向后导航应该在 } 分支中,通过从递归和一些技巧返回一级或调用实际节点的父节点上的方法。
但我不建议您遵循这个方向,仅使用列表中的值和简单的插入方法要容易得多。
关于java - 如何递归地将列表转换为 BSTree?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8938060/