InOrder Binary Tree with Iterator toString()

Question

我已经编写了所有其他东西，如addChild（），insert（）等，但似乎我的toInorderToList（）不起作用。它应该将树中的所有元素添加到列表中，之后我必须打印出列表，但我总是收到这些错误 java.util.ArrayList$Itr@70dea4e

我的代码片段

    private List<BinaryTreeNode> toInorderList(){
    if(this.root == null){
        return new ArrayList<BinaryTreeNode>();
    }else{
        return toInorderList(this.root);
    }

}
private ArrayList<BinaryTreeNode> toInorderList(BinaryTreeNode node) {
    ArrayList<BinaryTreeNode> treelist = new ArrayList<BinaryTreeNode>();
    if(node.left !=null){
        toInorderList(node.left);
        treelist.add(node.left);    
    }
    treelist.add(this.root);
    if(node.right != null){
        toInorderList(node.right);
        treelist.add(node.right);
    }
    return treelist;
}

和 toString（） 和 iterator（）

    public Iterator<BinaryTreeNode> iterator() {
    return toInorderList().iterator();
}    
public String toString() {
    return toInorderList().iterator().toString();
}

Answer 1

这是树的标准无序遍历

  private void InOrder(AVLNode<T> T)
  {
        if(T == null){
           return;
        } 
        InOrder(T.left);
        System.out.print(T.item + ", ");
        InOrder(T.right);        
 }

创建一个重载，只需将系统替换为 arraylist add

  private void InOrder(AVLNode<T> T, ArrayList list)
  {
        if(T == null){
           return;
        } 
        InOrder(T.left, list);
        list.add(T.item);            
        InOrder(T.right, list);        
  }

我花了两分钟来修改我的 avl 树以接受这一点。根是树的头，我的树在主实例化。 我里面有一堆整数

ArrayList<Integer> list = new ArrayList<>; 

是我的列表实例化。

root.InOrder(root);
root.InOrder(root, list);

两者都工作得很好

Answer 2

首先，在这段代码中：

if(node.left !=null){
    toInorderList(node.left);
    treelist.add(node.left);    
}
treelist.add(this.root);
if(node.right != null){
    toInorderList(node.right);
    treelist.add(node.right);
}

toInorderList函数有一个返回值，因此您需要使用 treelist.addAll(toInorderList(node.left);

此外，为了提高内存效率，我可能会在您的函数外部使用单个 ArrayList，并让每个递归调用访问它。

private List<BinaryTreeNode> toInorderList(){
    if(this.root == null){
        return new ArrayList<BinaryTreeNode>();
    }else{
        ArrayList<BinaryTreeNode> treeList = new ArrayList<BinaryTreeNode>();
        toInorderList(this.root, treeList);
        return treeList;
    }
}
private toInorderList(BinaryTreeNode node, ArrayList<BinaryTreeNode> treelist) {
    if(node.left !=null){
        toInorderList(node.left, treeList));
        treelist.add(node.left);    
    }
    treelist.add(this.root);
    if(node.right != null){
        toInorderList(node.right, treeList));
        treelist.add(node.right);
    }
}