java - 如何将节点从二叉树插入数组？

Question

我正在努力将二叉搜索树中的值插入数组，但我还需要对它们进行排序。以下是所需内容的说明。

toArray 方法应该创建并返回一个数组，其中包含按排序顺序(“按顺序”)排列的树中的每个元素。这个数组的容量应该等于它包含的元素的数量。此方法应使用递归私有(private)辅助方法 toArray(BSTNode, List) 来生成数组。该数组将需要创建为 Comparable 对象的数组，并转换为 E 对象的数组。您可以使用 Collection 的 toArray(E[]) 方法来帮助生成数组。

因此这是我目前的代码:

 public E[] toArray()
    {
        List<E> lista = new ArrayList<E>();
        toArray(root, lista);
        E[] good = (E[]) lista.toArray();
        return good;
    }
    private void toArray(BSTNode<E> node, List<E> aList)
    {
        if(node.left != null)
        {
            aList.add(node.left.data);
        }
    }

这是供引用的其余代码，但我更关注 toArray 方法。我不知道如何将它们排序到数组中。请帮忙。

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;

// post: constructs an empty search tree
public BinarySearchTree()
{
    root = null;
}

// post: value added to tree so as to preserve binary search tree
public void add(E value)
{
    root = add(root, value);
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value);
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value);
    }
    return node;
}

// post: returns true if tree contains value, returns false otherwise
public boolean contains(E value)
{
    return contains(root, value);
}
// post: returns true if given tree contains value, returns false otherwise
private boolean contains(BSTNode<E> node, E value)
{
    if (node == null)
    {
        return false;
    }
    else
        {
        int compare = value.compareTo(node.data);
        if (compare == 0)
        {
            return true;
        }
        else if (compare < 0)
        {
            return contains(node.left, value);
        }
        else
            {   // compare > 0
            return contains(node.right, value);
        }
    }
}
    public void remove(E value)
    {
        root = remove(root, value);
    }
    private BSTNode<E> remove(BSTNode<E> node, E value)
    {
        if(node == null)
        {
            return null;
        }
        else if(node.data.compareTo(value) < 0)
        {
            node.right = remove(node.right, value);
        }
        else if(node.data.compareTo(value) > 0)
        {
            node.left = remove(node.left, value);
        }
        else
        {
            if(node.right == null)
            {
                numElements--;
                return node.left;// no R child; replace w/ L
            }
            else if(node.left == null)
            {
                numElements--;
                return node.right;   // no L child; replace w/ R
            }
            else
            {
                // both children; replace w/ max from L
                node.data = getMax(node.left);
                node.left = remove(node.left, node.data);
            }
        }
        return node;
    }
    private E getMax(BSTNode<E> node)
    {
        if(node.right == null)
        {
            return node.data;
        }
        else
        {
            return getMax(node.right);
        }
    }
    public void clear()
    {
        root = null;
        numElements--;
    }
    public boolean isEmpty()
    {
        if(numElements == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public int size()
    {
        return numElements;
    }
    //My toArray Methods will go here. 
    public Iterator<E> iterator()
    {
        return new Iterator<>(root);
    }
    public static class Iterator<E>
    {
        private Stack<BSTNode<E>> stack;

        public Iterator(BSTNode<E> node)
        {
            this.stack = new Stack<>();
            while (node != null)
            {
                stack.push(node);
                node = node.left;
            }
        }
        public boolean hasNext()
        {
            return !stack.isEmpty();
        }
        public E next()
        {
            BSTNode<E> goodDays = stack.pop();
            E result = goodDays.data;
            if (goodDays.right != null)
            {
                goodDays = goodDays.right;
                while (goodDays != null)
                {
                    stack.push(goodDays);
                    goodDays = goodDays.left;
                }
            }
            return result;
        }
    }
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;

    public BSTNode(E data)
    {
        this(data, null, null);
    }
    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
}

Answer 1

等等，这是一个二叉搜索树，所以它已经排序了。

然后你需要走树。

假设你有类似的东西:

   4
 /   \
2      6
 \    /  \
  3  5    9

要插入它你必须:

给定一个树根

• A.如果树为空，则没有可插入的内容。
• B.如果不为空:
  • B.1 在左边插入所有内容
  • B.2 插入树根
  • B.3 在右边插入所有内容

看起来像这样:

void walkAndInsert(tree, array) {
    if (tree == null) {//A
        return
    } else { //B
      walkAndInsert(tree.left) //B.1
      array.add(tree.root) //B.2
      walkAndInsert(tree.right) //B.3
    }
}    

所以在数组上应用这些步骤:

树是否为空？否，则执行步骤#B(插入所有左、根和所有右)

//B
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[]

我们取左分支并重复该过程(步骤#B.1，插入所有左分支):

树是否为空？否，则执行#B

//B.1
tree = 
2      
 \      
  3     

array =[]

因为左边的分支是空的，接下来的执行是这样的:

树是否为空？是的，然后返回

//A
tree = 

array = []

这将结束步骤 B.1，我们现在可以转到步骤 B.2，插入根

//B.2
tree = 
2      
 \      
  3     

array =[2]

接着是步骤B.3 insert all from right

树是否为空？不(那里有一个 3)，

//B.3
tree =      
  3     

array =[2]

然后在这棵树上执行#B.1

树是空的吗？是的，本B.1到此结束

//A
tree =      

array =[2]

现在在 B.2 中我们插入这个根

树是否为空？不(那里有一个 3)，

//B.2
tree =      
  3     

array =[2,3]

最后我们转到 B.3 全部从右插入

但那里什么也没有，所以我们只好返回

 //A
tree =      

array =[2,3]

这完成了我们最初树的左侧分支。

所以在 B.1 在我们的初始树上完成后，我们执行 B.2，我们的数据如下所示:

// B.2 on the initial tree
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[2,3,4]

我们在右侧重复

是否为空？否，则B在有5的分支上，插入6，在有9的分支上步B

//B.3
tree = 
    6
   /  \
  5    9

array =[2,3,4]

// B.1
tree = 
    5

array =[2,3,4]

// A
tree = 


array =[2,3,4]

// B.2
tree = 
    5

array =[2,3,4,5]

// B.2
tree = 
    6
   /  \
  5    9

array =[2,3,4,5,6]

// B.3
tree = 
    9

array =[2,3,4,5,6]

// A
tree = 


array =[2,3,4,5,6]

// B.2
tree = 
    9

array =[2,3,4,5,6,9]