将BinarySearchTree inOrder遍历存储在一个数组中
Storing BinarySearchTree inOrder traversal in an array
我参考了以下 link 来了解如何将中序遍历保存到数组中 Binary Search Tree to inOrder Array。
我的树:
100
/ \
50 300
/ \
20 70
当第一个元素 (20) 插入数组时,索引值递增到 1。现在当控制去获取下一个节点 (50) 时,索引值变为 0。
代码:
storeInOrder(root1,arr1,0);
private static void storeInOrder(Node root1, int[] arr1, int index) {
if(root1 == null){return;}
storeInOrder(root1.left, arr1,index);
arr1[index++] = root1.data;
storeInOrder(root1.right,arr1,index);
}
数组中的预期输出:20 50 70 100 300
我得到的输出为 100 300 0 0 0
将逻辑放在访问代码中的想法是正确的,但你需要一个全局索引。在您的实现中,您修改的索引是按值传递的,这不会导致所需的行为,因为仅更改了值的本地副本。 Java 中的公式如下所示。
int[] iArray; // initialize with the desired size
int GlobalIndex = 0;
void Visit(Node iNode)
{
iArray[GlobalIndex++] = iNode.Data;
}
void StoreInOrder(Node iRoot)
{
if(null != iRoot)
{
StoreInOrder(iRoot.Left);
Visit(iRoot);
StoreInOrder(iRoot.Right);
}
}
或者,以更接近原始问题的更简洁的形式。
int[] iArray; // initialize with the desired size
int GlobalIndex = 0;
void StoreInOrder(Node iRoot)
{
if(null != iRoot)
{
StoreInOrder(iRoot.Left);
iArray[GlobalIndex++] = iNode.Data;
StoreInOrder(iRoot.Right);
}
}
如果实现必须尽可能接近原始版本,可以使用以下版本。它使用 int
的包装器 class 作为引用调用的替代,因为 Java 不允许基本数据类型的引用调用。
class IntWrapper
{
public int Value;
public IntWrapper(int InitialValue)
{
Value = InitialValue;
}
}
int[] iArray;
StoreInOrder(iRoot, iArray, new IntWrapper() )
void StoreInOrder(Node iRoot, int[] iArray, IntWrapper Index)
{
StoreInOrder(iRoot.Left,iArray,Index);
iArray[Index.Value++] = iNode.Data;
StoreInOrder(iRoot.Right,iArray,Index);
}
您可以将函数修改为return上次使用的索引,然后根据新索引进行更新。
storeInOrder(root1,arr1);
private static void storeInOrder(Node root1, int[] arr1) {
storeInOrderRecursive(root1,arr1,0);
}
private static Integer storeInOrderRecursive(Node root1, int[] arr1, int index) {
if(root1 == null){return index;}
index = storeInOrderRecursive(root1.left, arr1,index);
arr1[index++] = root1.data;
storeInOrderRecursive(root1.right,arr1,index);
return index;
}
包装函数不是必需的,但由于您总是将 0 传递给 storeInOrderRecursive
这使得 API 相似,然后 return 值仍然可以是 void
呼叫 storeInOrder
。
我参考了以下 link 来了解如何将中序遍历保存到数组中 Binary Search Tree to inOrder Array。
我的树:
100
/ \
50 300
/ \
20 70
当第一个元素 (20) 插入数组时,索引值递增到 1。现在当控制去获取下一个节点 (50) 时,索引值变为 0。
代码:
storeInOrder(root1,arr1,0);
private static void storeInOrder(Node root1, int[] arr1, int index) {
if(root1 == null){return;}
storeInOrder(root1.left, arr1,index);
arr1[index++] = root1.data;
storeInOrder(root1.right,arr1,index);
}
数组中的预期输出:20 50 70 100 300
我得到的输出为 100 300 0 0 0
将逻辑放在访问代码中的想法是正确的,但你需要一个全局索引。在您的实现中,您修改的索引是按值传递的,这不会导致所需的行为,因为仅更改了值的本地副本。 Java 中的公式如下所示。
int[] iArray; // initialize with the desired size
int GlobalIndex = 0;
void Visit(Node iNode)
{
iArray[GlobalIndex++] = iNode.Data;
}
void StoreInOrder(Node iRoot)
{
if(null != iRoot)
{
StoreInOrder(iRoot.Left);
Visit(iRoot);
StoreInOrder(iRoot.Right);
}
}
或者,以更接近原始问题的更简洁的形式。
int[] iArray; // initialize with the desired size
int GlobalIndex = 0;
void StoreInOrder(Node iRoot)
{
if(null != iRoot)
{
StoreInOrder(iRoot.Left);
iArray[GlobalIndex++] = iNode.Data;
StoreInOrder(iRoot.Right);
}
}
如果实现必须尽可能接近原始版本,可以使用以下版本。它使用 int
的包装器 class 作为引用调用的替代,因为 Java 不允许基本数据类型的引用调用。
class IntWrapper
{
public int Value;
public IntWrapper(int InitialValue)
{
Value = InitialValue;
}
}
int[] iArray;
StoreInOrder(iRoot, iArray, new IntWrapper() )
void StoreInOrder(Node iRoot, int[] iArray, IntWrapper Index)
{
StoreInOrder(iRoot.Left,iArray,Index);
iArray[Index.Value++] = iNode.Data;
StoreInOrder(iRoot.Right,iArray,Index);
}
您可以将函数修改为return上次使用的索引,然后根据新索引进行更新。
storeInOrder(root1,arr1);
private static void storeInOrder(Node root1, int[] arr1) {
storeInOrderRecursive(root1,arr1,0);
}
private static Integer storeInOrderRecursive(Node root1, int[] arr1, int index) {
if(root1 == null){return index;}
index = storeInOrderRecursive(root1.left, arr1,index);
arr1[index++] = root1.data;
storeInOrderRecursive(root1.right,arr1,index);
return index;
}
包装函数不是必需的,但由于您总是将 0 传递给 storeInOrderRecursive
这使得 API 相似,然后 return 值仍然可以是 void
呼叫 storeInOrder
。