将树遍历为数组 [英] Traversing a tree into an array

问题描述

我应该遍历二叉树作为预排序，后排序和后排序，然后将值插入Java中的Object []中.老实说，我不知道如何执行此操作，我需要一些建议.

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.

我的功能:

public Object[] traversePreOrder()

基本上，我所需要的只是一些有关如何完成此任务的想法或提示. 如果我遍历一棵树，那么Object [0]显然是根的值.然后，我继续在左侧树中并将最左侧的值插入到我的数组中. 接下来，我插入最左侧节点的右侧子节点，如果右侧节点没有子节点，则继续使用两个节点的父节点.

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.

帮助！

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

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;

}

必须明显地填补空白.

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

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

推荐答案

使用递归的理想情况.创建方法

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

• 对于预遍历，将值，左孩子的结果和右孩子的结果连接起来；
• 对于有序遍历，将左孩子的结果，值和右孩子的结果连接起来；
• 对于后遍历，将左孩子的结果，右孩子的结果和值连接起来.

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

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

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