java - 中序遍历给出不正确的输出

Question

class Node {
    Node parent;
    Node left;
    Node right;
    int value;

    Node (int value) {
        this.value = value;
        this.parent = null;
        this.left = null;
        this.right = null;
    }
}

class TreeofNodes {
    Node insert (Node root, Node node) {
        if (root == null)
        {
            root = node;
            return root;
        }

        Node cur    = root;
        Node father = root;

        while(cur != null)
        {
            father = cur;
            if (cur.value > node.value)
                cur = cur.left;
            else
                cur = cur.right;
        }
        if(father.value > node.value)
            father.left  = node;
        else
            father.right = node;

        node.parent = father;

        return node;
    }

    void Inorder (Node n) {
        if (n == null)
           return;
        Inorder (n.left);
        System.out.print (n.value + " ");
        Inorder (n.right);
    }
}

class binarySearchTree {

public static void main (String [] args) {

    int A[] = {6, 8, 5, 3, 7, 9, 1};

    TreeofNodes obj = new TreeofNodes ( );

    Node root = null;
    Node n = new Node (A[0]);
    root = obj.insert (root, n);

    Node Croot = root;

    for (int i = 1; i < 7; i++)
    {
        n = new Node (A[i]);
        Croot = obj.insert (Croot, n);
    }

    System.out.println ("============ Inorder ============");
    obj.Inorder (root);
  }
}

当我调用 Inorder 方法时，我期望输出为:

 1   3   5   6   7   8   9

但确实如此

 6   3   7   1   9   5   8

我怀疑我的插入方法是错误的。

有人可以告诉我我错在哪里以及如何解决吗？

Answer 1

您的insert函数在末尾返回node而不是root。变化:

    return node;

至

    return root;