菜单驱动 Java 实现二进制搜索树的程序。无法获得树结构以在根之外添加节点（插入功能）

Question

除了根之外，我无法永久添加更多节点。一旦在插入函数中创建了一个树对象，在下一次进入插入函数时它就会被取消，所以只有根存在。我找不到问题，这让我发疯。有人请帮忙，如果你使用我在这段代码中使用的相同数据结构会更好。

    import java.util.Scanner;

    class tree

    { 
          int x;

           tree left=null;

        tree right=null;
     }

       class bst28
        {
           public static tree root=null;

            public static void main(String[] args)
            {  
               bst28 bl=new bst28();
               int ch,y;
                 Scanner scn=new Scanner(System.in);
               do{
                   System.out.println("Menu:\n1.Insert\n2.Search");   System.out.println("\n3.In-order-traversal\n4..Exit:");
                 ch=scn.nextInt();
                switch(ch)
                 {
                  case 1:System.out.println("Enter the element to insert :");
                 y=scn.nextInt();
                 bl.insert(y);
                     break;
          case 2:System.out.println("Enter the element to search for :");
                y=scn.nextInt();
                bl.search(y);
                     break;
          case 3:  bl.inorder(bl.root);
                     break;

          default:break;  
       }
      }while(ch!=4);

   }

        void insert(int a) 
        {
            tree temp=new tree();
           temp.x=a;
            boolean val=true;
            if(root==null)
            {  
               root=new tree();
                 root=temp;

          return;
       }
        System.out.println(root.x);
       tree current=new tree();
       current=root;
       while(val)
        {
           if(a<current.x)
            { System.out.println(current.x);
                 System.out.println("Trav to left");
              current=current.left;
              if(current==null)
               {  
                     System.out.println("Node currently null");
                  current=new tree();
                  current=temp;
                  System.out.println("Entered left of a node");
                  System.out.println(current.x);
                  val=false;
                }
            }
           else if(a>current.x)
             {
               System.out.println("Trav to right");
             current=current.right;
              if(current==null)
               {  
                  System.out.println("Node currently null");
                 current=new tree();
                 current=temp;
                 System.out.println("Entered right of a node");
                 System.out.println(current.x);
                  val=false;
                }
              }
              else
                 {
                   System.out.println("Value exists in the tree\n");
                   val=false;
                 }
        }
      }

         void search(int a)
           {
               if(root==null)
                {
                    System.out.println("Empty tree !");
                    return;   

                 } 

                 tree current=new tree();
                  current=root;
                  while(current!=null)
                   {
                       if(a==current.x)
                         {
                           System.out.println("FOund !");
                            return;               
                           }
                           else if(a<current.x)
                           {
                           current=current.left;
                          }
                        else
                       {
                          current=current.right;
                        }   

                   } 
               System.out.println("Not Found !");
            } 

          void inorder(tree temp)
          {
             if(temp!=null)
            {
               inorder(temp.left);
                  System.out.println("Visited node :"+temp.x);
               inorder(temp.right);
               }

             }



          }`

Answer 1

您没有将新子树（我们称它为 "node"，因为它只包含 1 个元素）与现有树相关联。您正在创建节点，向下移动树，当您发现当前节点为空时，将新节点关联到当前节点。您必须保持领先一步，这意味着：在向下移动树（向左或向右）之前检查 (left/right) 子树是否为空并采取相应行动。所以，代码：

if(a<current.x)
    { System.out.println(current.x);
         System.out.println("Trav to left");
      current=current.left;
      if(current==null)
       {  
             System.out.println("Node currently null");
          current=new tree();
          current=temp;
          System.out.println("Entered left of a node");
          System.out.println(current.x);
          val=false;
        }
    }

变成这样（我没有运行代码，所以测试一下）：

if(a<current.x)
    { System.out.println(current.x);
         System.out.println("Trav to left");

      if(current.left!=null)
      {
          current=current.left;
          System.out.println("Entered left of a node");
          System.out.println(current.x);
      } 
      else
       {  
             System.out.println("Node currently null");
          current.left=temp;
          val=false;
        }
    }

另一种情况也必须这样做。

菜单驱动 Java 实现二进制搜索树的程序。无法获得树结构以在根之外添加节点（插入功能）

Menu Driven Java Program to implement Binary Search Tree. Cant get the Tree structure to add nodes beyond the root (insert function)

java

data-structures

binary-search-tree