英文:
Traversal in Tree Data Structure (IN-Order) not working in java
问题
以下是翻译的内容:
我对数据结构还不熟悉,目前正在编写一个树数据结构的遍历方法。目前,在执行中序遍历时,应该是从较小的值移动到较大的值。但是似乎我的方法没有遵循这个顺序。请问这里有什么问题?以下是代码片段:
int[] intArr = { 100, 20 ,140, 55, 19, 22, 89, 200, 120 };
for( int i = 0; i < intArr.length; i++ )
{
key += intArr[i];
tree.insert(key, intArr[i]); // Key is the same as data in this case
key = "";
}
String str = tree.inOrderTraverse();
System.out.println(str);
期望的输出应该是这样的:19 20 22 55 89 100 120 140 200
但实际输出是:100 120 140 19 20 200 22 55 89
以下是我的递归方法和包装方法:
// 子模块:inOrderTraverse (包装方法)
// 输入:无
// 输出:(String)
public String inOrderTraverse()
{
return inOrderRec( root, "" );
}
// 子模块:inOrderRec
// 输入:currNd (DSATreeNode), str (String)
// 输出:str (String)
private String inOrderRec( DSATreeNode currNd, String str )
{
if( currNd != null )
{
str = inOrderRec( currNd.left, str );
str += currNd.data + " ";
str = inOrderRec( currNd.right, str );
}
return str;
}
以下是我的插入方法及其包装方法:
// 子模块:insert (包装方法)
// 输入:key (String), data (Object)
// 输出:无
public void insert( String key, Object data )
{
try { root = insertRec( root, key, data ); } // 现在 root 包含了所有树的地址
catch(IllegalArgumentException e) { System.out.println(e.getMessage()); }
}
// 子模块:insertRec
// 输入:currNd (DSATreeNode), key (String), data (Object)
// 输出:updateNd (DSATreeNode)
// 断言:创建新的树节点
private DSATreeNode insertRec( DSATreeNode currNd, String key, Object data )
{
DSATreeNode updateNd;
updateNd = currNd;
if( currNd == null )
{
currNd = new DSATreeNode( key, data );
updateNd = currNd;
}
else if( key.equals(currNd.key) )
throw new IllegalArgumentException( "提供了现有的键" ); // 键必须唯一
else if( key.compareTo(currNd.key) < 0 )
currNd.left = insertRec( currNd.left, key, data ); // 递归到左侧
else
currNd.right = insertRec( currNd.right, key, data ); // 递归到右侧
return updateNd;
}
英文:
I am new to Data Structure and currently I am writing a Tree Data Structure traversing method. Right now, when I perform in-order traversal, it should be moving from smaller to largest value. But it seems that my method is not following the sequence. May I know what is the issue here? Here is the code snippet:
int[] intArr = { 100, 20 ,140, 55, 19, 22, 89, 200, 120 };
for( int i = 0; i < intArr.length; i++ )
{
key += intArr[i];
tree.insert(key, intArr[i]); // Key is the same as data in this case
key = "";
}
String str = tree.inOrderTraverse();
System.out.println(str);
The output supposed to look like this: 19 20 22 55 89 100 120 140 200
But this is the actual output: 100 120 140 19 20 200 22 55 89
Here is my recursive method and wrapper method:
// SUBMODULE: inOrderTraverse (Wrapper Method)
// IMPORT: none
// EXPORT: (String)
public String inOrderTraverse()
{
return inOrderRec( root, "" );
}
// SUBMODULE: inOrderRec
// IMPORT: currNd (DSATreeNode), str (String)
// EXPORT: str (String)
private String inOrderRec( DSATreeNode currNd, String str )
{
if( currNd != null )
{
str = inOrderRec( currNd.left, str );
str += currNd.data + " ";
str = inOrderRec( currNd.right, str );
}
return str;
}
This is my insert and its wrappers
// SUBMODULE: insert (Wrapper)
// IMPORT: key (String), data (Object)
// EXPORT: none
public void insert( String key, Object data )
{
try { root = insertRec( root, key, data ); } // Now root has the address of all the trees
catch(IllegalArgumentException e) { System.out.println(e.getMessage()); }
}
// SUBMODULE: insertRec
// IMPORT: currNd (DSATreeNode), key (String), data (Object)
// EXPORT: updateNd (DSATreeNode)
// ASSERTION: Create the new tree node
private DSATreeNode insertRec( DSATreeNode currNd, String key, Object data )
{
DSATreeNode updateNd;
updateNd = currNd;
if( currNd == null )
{
currNd = new DSATreeNode( key, data );
updateNd = currNd;
}
else if( key.equals(currNd.key) )
throw new IllegalArgumentException( "Existing key provided" ); // Key must be unique
else if( key.compareTo(currNd.key) < 0 )
currNd.left = insertRec( currNd.left, key, data ); // Recursive to left
else
currNd.right = insertRec( currNd.right, key, data ); // Recursive to right
return updateNd;
}
答案1
得分: 1
你的键实际上是字符串。因此,您将获得您插入的键的词典顺序。这就是输出的原因。
100 120 140 19 20 200 22 55 89 是正确的词典顺序!
如果您的元素是整数,请不要使用字符串作为键的数据类型。如果您的元素是整数,请使用整数。
或者在比较之前尝试将键从字符串转换为整数,例如在您的插入方法中使用 Integer.valueOf(key).compareTo(Integer.valueOf(currNd.key))
。
但这会额外增加工作量,并且容易引发异常,除非您确保键始终表示整数。
英文:
Your keys are actually strings. Therefore you will get the lexicographical order of the keys you have inserted. That is why the output is what you see.
100 120 140 19 20 200 22 55 89 is the correct lexicographical order!
Don't use string as datatypes for keys. Use integer if your elements are integers.
Or try to convert the keys to integers from strings before comparing like: Integer.valueOf(key).compareTo(Integer.valueOf(currNd.key))
in your insert method.
But this is extra work and is prone to exceptions unless you are sure that keys represent integers always.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论