二叉搜索树

Question

class Student
{
    String name;
    int roll;
    int age;
    public Student(String n,int r,int a) {
        name=n;
        roll=r;
        age=a;
    }
    public String retname() {
        return name;
    }
    public int retroll() {
        return roll;
    }
    public int retage() {
        return age;
    }
    public void displaystudent() {
        System.out.print("Name : "+name+" Roll : "+roll+" Age : "+age+"\n");
    }
}

class Node
{
    Student s;
    Node lchild;
    Node rchild;
    public Node(String n,int r ,int a) {
        s=new Student(n,r,a);
    }
    public void displayNode() {
        s.displaystudent();
    }
}
class Tree
{
    public Node root;
    public void insert(String n,int r,int a) {
        Node newNode=new Node(n,r,a);
        if(root==null)
            root=newNode;
        else {
            Node current=root;
            Node parent;
            while(true) {
                parent=current;
                if(n.compareTo(current.s.retname())<0) {
                    current=current.lchild;
                    if(current==null)
                        parent.lchild=newNode;
                    return;
                } else {
                    current=current.rchild;
                    if(current==null)
                        parent.rchild=newNode;
                    return;
                }
            }
        }
    }
    public void order() {
        inorder(root);
        preorder(root);
        postorder(root);
    }
    public void inorder(Node localroot) {
        if(localroot!=null) {
            inorder(localroot.lchild);
            localroot.displayNode();
            inorder(localroot.rchild);
        }
    }
    public void preorder(Node localroot) {

        if(localroot!=null) {
            preorder(localroot.lchild);
            preorder(localroot.rchild);
            localroot.displayNode();
        }
    }
    public void postorder(Node localroot) {
        if(localroot!=null) {
            localroot.displayNode();
            postorder(localroot.lchild);
            postorder(localroot.rchild);
        }
    }
}
class e
{
    public static void main(String [] args) { //throws IOException

        Tree t=new Tree();
        t.insert("E",1,23);
        t.insert("D",2,2);
        t.insert("C",3,4);
        t.insert("B",4,89);

        t.insert("A",5,45);

        t.order();
    }
}

上面的代码没有显示它应该显示的所有输出。另外，为什么 preorder 和 inorder 给出相同的结果？另外，不从根开始的子树怎么遍历呢？有什么办法可以避免递归吗？

这是当前的错误输出。它应该打印我插入的所有元素，并且也按特定顺序打印。

Name : D Roll : 2 Age : 2 
Name : E Roll : 1 Age : 23 
Name : D Roll : 2 Age : 2 
Name : E Roll : 1 Age : 23 
Name : E Roll : 1 Age : 23 
Name : D Roll : 2 Age : 2

Answer 1

我注意到的最明显也是第一个问题是您的 insert 方法。在此方法中，您总是 return 在检查 while 循环的下一次迭代之前（在根有子子节点的情况下，不会插入任何内容）。要修复此错误，只需像这样更改您的 while 循环：

while(true)
     { 
        parent=current; //assign parent to root
        if(n.compareTo(current.s.retname())<0) 
        {
             current=current.lchild; 
             if(current==null) {//added brackets so the return only happened when this was true
               parent.lchild=newNode;
               return;
            }
       }
       else
       { 
        current=current.rchild;
        if(current==null){ //added brackets so the return only happened when this was true
            parent.rchild=newNode;
            return;
            }
        }
   }

进行这些更改后，您的其他问题可能会自行得到解答。进行这些更改，看看它是否解决了您的问题，如果没有，请发表评论让我知道，我会再看看。

编辑一个：

我认为您的预订有误。我相信您应该打印节点 before 分别递归遍历左右子节点。它应该是这样的：

   public void preorder(Node localroot) {

    if(localroot!=null) {
        localroot.displayNode(); //here!
        preorder(localroot.lchild);
        preorder(localroot.rchild);
        //localroot.displayNode(); not here!
    }
}

二叉搜索树

A binary search tree

java

binary-search-tree