0

我应该将二叉搜索树作为前序、中序和后序遍历，并将值插入到 Java 中的 Object[] 中。老实说，我不知道如何做到这一点，我需要一些建议。

我的功能：

public Object[] traversePreOrder()

我所需要的基本上是一些关于如何完成这项任务的想法或提示。如果我遍历树作为 preorder Object[0] 显然是根的值。然后我继续在左边的树中插入最左边的值到我的数组中。接下来，我插入最左边节点的右子节点，如果右节点没有子节点，则继续使用两个节点的父节点。

但是我的方法不记得已经检查和插入了哪些值。我还想过以后序遍历，将每个元素放入堆栈并将每个元素推送到我的数组中，但我对如何实现这一点的知识有限。

帮助！

以下是我认为已经正确的内容：

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



    return preOrderArray;

}

显然必须填补空白。

此外，我还有基本的方法和构造函数：

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;
}
4

2 回答 2

1

使用递归的理想情况。创建一个方法

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

其中遍历代码遍历左孩子和右孩子（如果有的话），并且

  • 对于前序遍历，连接值、左孩子的结果和右孩子的结果；
  • 对于中序遍历，连接左孩子的结果、值和右孩子的结果；
  • 对于后序遍历，连接左孩子的结果、右孩子的结果和值。

调用traverse根并将结果转换为Object[].

于 2013-05-29T17:05:23.730 回答
0

正如上面提到的Arend，这是一般的想法。我不确定你是否可以让它每次都返回一个列表，但你也许可以。但是，如果该实现不起作用，您可以尝试这样的事情，看看其他一切是否正常：

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}
于 2013-05-29T17:34:12.260 回答