二叉搜索树到inOrder数组 [英] Binary Search Tree to inOrder Array

问题描述

一个很简单的问题:

如何递归地创建一个使用此构造函数的二进制搜索树数组(按顺序):

Recursively how can I create an array of a binary search tree (in order) which uses this constructor:

public class OrderedSet<E extends Comparable<E>> {
    private class TreeNode {
    private E data;
    private TreeNode left, right;

    public TreeNode(E el) {
        data = el;
        left = null;
        right = null;
    }
}

  private TreeNode root;
  public int size = 0;

  public OrderedSet() {
    root = null;
  }

推荐答案

按顺序表示您首先必须遍历树的左侧，所以:

In-Order means you first have to traverse the left part of the tree, so:

TreeNode tree  // this is your tree you want to traverse
E[] array = new E[tree.size];  // the arrays length must be equivalent to the number of Nodes in the tree
int index = 0; // when adding something to the array we need an index
inOrder(tree, array, index);  // thats the call for the method you'll create

该方法本身可能看起来像这样:

The method itself could looks something like this:

public void inOrder(TreeNode node, E[] array, int index){
    if(node == null){  // recursion anchor: when the node is null an empty leaf was reached (doesn't matter if it is left or right, just end the method call
       return;
    }
    inOrder(node.getLeft(), array, index);   // first do every left child tree
    array[index++]= node.getData();          // then write the data in the array
    inOrder(node.getRight(), array, index);  // do the same with the right child
}

有点像.我只是不确定该索引及其需要增加的位置.如果您不想担心索引，或者不知道树中有多少个节点，请改用ArrayList并将其最后转换为数组.

Somewhat like that. I am just not sure about the index and where it needs to be incremented. If you don't want to worry about the index or if you don't know how many nodes are in the tree, then use an ArrayList instead and transform it in the end to an array.

通常在这样的递归方法周围构建一个更简洁的调用方法:

Normally a cleaner call method is build around the recursive method like this:

public E[] inOrderSort(TreeNode tree){
    E[] array = new E[tree.size];
    inOrder(tree, array, 0);
    return array;
}

这篇关于二叉搜索树到inOrder数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！