在树数据结构中遍历(中序遍历),在Java中不起作用。

huangapple go评论68阅读模式
英文:

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 &lt; intArr.length; i++ )
    {
        key += intArr[i];
        tree.insert(key, intArr[i]); // Key is the same as data in this case
        key = &quot;&quot;;
    }

    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, &quot;&quot; );
}

// 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 + &quot; &quot;;
        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( &quot;Existing key provided&quot; );      // Key must be unique

    else if( key.compareTo(currNd.key) &lt; 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.

huangapple
  • 本文由 发表于 2020年9月11日 22:37:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/63849204.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定