Traversing a tree into an array

问题:

I'm supposed to traverse a Binary Seach Tree as preorder, inorder and postorder and insert the values into an Object[] in Java. I honestly have no clue how to do this and I need some advice.

My function:

public Object[] traversePreOrder()

All I need are basically some ideas or hints on how to complete this task. If I traverse a tree as preorder Object[0] is obviously the value of the root. Then I continue in the left tree and insert the most left values in my array. Next I insert the right child of the most left node and continue with the parent of both nodes if the right node has no children.

But my method can't remember which values have already been checked and inserted. I also thought of traversing in postorder, putting each element onto an stack and push each element onto my array, but I've got limits to my knowledge on how to implement this.

Help!

Here's what is in my opinion already correct:

@Override
public Object[] traversePreOrder() {
    Object[] preOrderArray = new Object[elements];
    if (elements == 0) {
        return preOrderArray;
    }



    return preOrderArray;

}

The gap has to be filled obviously.

Additionally I have as basic methods and constructors:

BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left,
        BinarySearchTreeNode<T> right) {
    this.value = value;
    this.left = left;
    this.right = right;
}

BinarySearchTreeNode(T value) {
    this(value, null, null);
}

BinarySearchTreeNode<T> getLeft() {
    return left;
}

void setLeft(BinarySearchTreeNode<T> left) {
    this.left = left;
}

BinarySearchTreeNode<T> getRight() {
    return right;
}

void setRight(BinarySearchTreeNode<T> right) {
    this.right = right;
}

T getValue() {
    return value;
}

void setValue(T value) {
    this.value = value;
}

回答1:

An ideal case for using recursion. Create a method

List<BinarySearchTreeNode> traverse(BinarySearchTreeNode n) {
    // traversal code
}

where the traversal code traverses the left child and the right child if any, and

• for preorder traversal, concatenates the value, left child's result and the right child's result;
• for inorder traversal, concatenates the left child's result, the value, and the right child's result;
• for postorder traversal, concatenates the left child's result, the right child's result and the value.

Call traverse for the root and convert the result into an Object[].

回答2:

As Arend mentioned above, this is the general idea. I'm not sure if you can have it return a list each time, but you might be able to. However, if that implementation doesn't work you could try something like this just to see if everything else is working:

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}