java - 将树遍历到数组中

Question

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

我的功能:

public Object[] traversePreOrder()

我所需要的基本上只是一些关于如何完成这项任务的想法或提示。如果我按照前序对象[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;
}

Answer 1

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

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

其中遍历代码遍历左子节点和右子节点(如果有)，并且

• 对于前序遍历，将值、左子节点的结果和右子节点的结果连接起来；
• 对于中序遍历，连接左子节点的结果、值和右子节点的结果；
• 对于后序遍历，将左子节点的结果、右子节点的结果和值连接起来。

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