我应该按前序、中序和后序遍历二叉搜索树,并将值插入到 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;
}
最佳答案
使用递归的理想情况。创建一个方法
List<BinarySearchTreeNode> traverse(BinarySearchTreeNode n) {
// traversal code
}
其中遍历代码遍历左子节点和右子节点(如果有),并且
- 对于前序遍历,将值、左子节点的结果和右子节点的结果连接起来;
- 对于中序遍历,连接左子节点的结果、值和右子节点的结果;
- 对于后序遍历,将左子节点的结果、右子节点的结果和值连接起来。
调用根的traverse
并将结果转换为Object[]
。
关于java - 将树遍历到数组中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16819177/