java - 如何将二叉树中的节点推送到数组中？

Question

我正在努力将二进制搜索树中的值推送到数组中，但我也需要对它们进行排序。以下是所需内容的说明。

toArray 方法应该创建并返回一个数组，其中包含按排序顺序（“按顺序”）排列的树中的每个元素。这个数组的容量应该等于它包含的元素数。此方法应使用递归私有辅助方法 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;
    }
}
}

标签： javaarrayssortingbinary-search-treenodes

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，插入root

//B.2
tree = 
2      
 \      
  3     

array =[2]

后跟步骤 B.3 从右侧插入所有内容

树是空的吗？不（那里有一个 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]