Вставка дерева Java

Question

У меня проблема с вопросом дерева. Ошибок в коде нет; это просто неправильный вывод. Проблема в том, что когда я вставляю «100», это дает неправильное количество листьев и высоты, а также ошибочный обход Traversal. Вот бинарное дерево класс:

public class BinaryTree { 

    //Definition of the node 
    protected class BinaryTreeNode { 

     Object info; 
     BinaryTreeNode llink; 
     BinaryTreeNode rlink; 
    } 
    protected BinaryTreeNode root; 

    //default constructor 
    //Postcondition: root = null; 
    public BinaryTree() { 
     root = null; 
    } 

    //copy constructor 
    public BinaryTree(BinaryTree otherTree) { 
     if (otherTree.root == null) //otherTree is empty 
     { 
      root = null; 
     } else { 
      root = copy(otherTree.root); 
     } 
    } 

    //Method to determine whether the binary tree is empty. 
    //Postcondition: Returns true if the binary tree is empty; 
    //    otherwise, returns false.  
    public boolean isEmpty() { 
     return (root == null); 
    } 

    //Method to do an inorder traversal of the binary tree. 
    //Postcondition: The nodes of the binary tree are output 
    //    in the inorder sequence. 
    public void inorderTraversal() { 
     inorder(root); 
    } 

    //Method to do a preorder traversal of the binary tree. 
    //Postcondition: The nodes of the binary tree are output 
    //    in the preorder sequence. 
    public void preorderTraversal() { 
     preorder(root); 
    } 

    //Method to do a postorder traversal of the binary tree. 
    //Postcondition: The nodes of the binary tree are output 
    //    in the postorder sequence.  
    public void postorderTraversal() { 
     postorder(root); 
    } 

    //Method to determine the height of the binary tree. 
    //Postcondition: The height of the binary tree is returned.  
    public int treeHeight() { 
     return height(root); 
    } 

    //Method to determine the number of nodes in the 
    //binary tree. 
    //Postcondition: The number of nodes in the binary tree 
    //    is returned.  
    public int treeNodeCount() { 
     return nodeCount(root); 
    } 
    //Method to determine the number of nodes in the binary 
    //tree to which p points. 
    //Postcondition: The number of nodes in the binary tree 
    //    to which p points is returned.  

    private int nodeCount(BinaryTreeNode p) { 
     if (p == null) { 
      return 0; 
     } else { 
      return (1 + nodeCount(p.llink) + nodeCount(p.rlink)); 
     } 
    } 

    //Method to determine the number of leaves in the 
    //binary tree. 
    //Postcondition: The number of leaves in the binary tree 
    //    is returned.  
    public int treeLeavesCount() { 
     return leavesCount(root); 
    } 
    //Method to determine the number of leaves in the binary 
    //tree to which p points. 
    //Postcondition: The number of leaves in the binary tree 
    //    to which p points is returned.  

    private int leavesCount(BinaryTreeNode p) { 
     if (p == null) { 
      return 0; 
     } 
     if (p.llink == null && p.rlink == null) { 
      return 1; 
     } 
     return (leavesCount(p.rlink) + leavesCount(p.llink)); 
    } 

    //Method to destroy the binary tree. 
    //Postcondition: root = null  
    public void destroyTree() { 
     root = null; 
    } 

    //Method to make a copy of the binary tree 
    //specified by otherTree points. 
    //Postcondition: A copy of otherTree is assigned to 
    //    this binary tree. 
    public void copyTree(BinaryTree otherTree) { 

     if (this != otherTree) //avoid self-copy 
     { 
      root = null; 

      if (otherTree.root != null) //otherTree is nonempty 
      { 
       root = copy(otherTree.root); 
      } 
     } 

    } 

    //Method to make a copy of the binary tree to 
    //which otherTreeRoot points. 
    //Postcondition: A copy of the binary tree to which 
    //    otherTreeRoot is created and the reference of 
    //    the root node of the copied binary tree 
    //    is returned. 
    private BinaryTreeNode copy(BinaryTreeNode otherTreeRoot) { 
     BinaryTreeNode temp; 

     if (otherTreeRoot == null) { 
      temp = null; 
     } else { 
      temp = new BinaryTreeNode(); 
      temp.info = (((String) otherTreeRoot.info)); 
      temp.llink = copy(otherTreeRoot.llink); 
      temp.rlink = copy(otherTreeRoot.rlink); 
     } 

     return temp; 
    }//end copy 

    //Method to do an inorder traversal of the binary 
    //tree to which p points. 
    //Postcondition: The nodes of the binary tree to which p 
    //    points are output in the inorder sequence.  
    private void inorder(BinaryTreeNode p) { 
     if (p != null) { 
      inorder(p.llink); 
      System.out.print(p.info + " "); 
      inorder(p.rlink); 
     } 
    } 

    //Method to do a preorder traversal of the binary 
    //tree to which p points. 
    //Postcondition: The nodes of the binary tree to which p 
    //    points are output in the preorder sequence.  
    private void preorder(BinaryTreeNode p) { 
     if (p != null) { 
      System.out.print(p.info + " "); 
      preorder(p.llink); 
      preorder(p.rlink); 
     } 
    } 

    //Method to do a postorder traversal of the binary 
    //tree to which p points. 
    //Postcondition: The nodes of the binary tree to which p 
    //    points are output in the postorder sequence.  
    private void postorder(BinaryTreeNode p) { 
     if (p != null) { 
      postorder(p.llink); 
      postorder(p.rlink); 
      System.out.print(p.info + " "); 
     } 
    } 

    public void insert(String x) { 
     BinaryTreeNode c1, c2, nn; 
     nn = new BinaryTreeNode(); 
     nn.info = x; 
     nn.llink = null; 
     nn.rlink = null; 
     if (isEmpty()) { 
      root = nn; 
     } else { 
      c2 = root; 
      c1=null; 
      while (c2 != null) { 
       c1 = c2; 
       if (c2.info.equals(x)) { 
        System.out.println("Error"); 
        return; 
       } else { 
        if (((String) c2.info).compareTo(x) > 0) { 
         c2 = c2.llink; 
        } else { 
         c2 = c2.rlink; 
        } 
       } 
      } 
     if (((String) c1.info).compareTo(x) > 0) { 
      c1.llink = nn; 
     } else { 
      c1.rlink = nn; 
     } 
    } 
    } 

    public boolean search(String x) { 
     boolean found = false; 
     BinaryTreeNode c1; 
     BinaryTreeNode c2 = root; 
     while (c2 != null && !found) { 
      c1 = c2; 
      if (c2.info.equals(x)) { 
       found = true; 
      } else { 
       if (((String) c2.info).compareTo(x) > 0) { 
        c2 = c2.llink; 
       } else { 
        c2 = c2.rlink; 
       } 
      } 
     } 
     return found; 
    } 
    //Method to determine the height of the binary tree 
    //to which p points. 
    //Postcondition: The height of the binary tree to which p 
    //    points is returned. 

    private int height(BinaryTreeNode p) { 
     if (p == null) { 
      return 0; 
     } else { 
      return 1 + max(height(p.llink), height(p.rlink)); 
     } 
    } 

    //Method to determine the larger of x and y. 
    //Postcondition: The larger of x and y is returned.  
    private int max(int x, int y) { 
     if (x >= y) { 
      return x; 
     } else { 
      return y; 
     } 
    } 

    public void deleteNode(String deleteItem) { 
     BinaryTreeNode current; //reference variable to 
     //traverse the tree 
     BinaryTreeNode trailCurrent; //reference variable 
     //behind current 
     boolean found = false; 

     if (root == null) { 
      System.out.println("Cannot delete from the empty tree."); 
     } else { 
      current = root; 
      trailCurrent = root; 

      while (current != null && !found) { 
       if (current.info.equals(deleteItem)) { 
        found = true; 
       } else { 
        trailCurrent = current; 
        if (((String) current.info).compareTo(deleteItem) > 0) { 
         current = current.llink; 
        } else { 
         current = current.rlink; 
        } 
       } 
      }//end while 
      if (current == null) { 
       System.out.println("The delete item is not in " 
         + "the list."); 
      } else if (found) { 
       if (current == root) { 
        root = deleteFromTree(root); 
       } else if (((String) trailCurrent.info).compareTo(deleteItem) > 0) { 
        trailCurrent.llink = deleteFromTree(trailCurrent.llink); 
       } else { 
        trailCurrent.rlink = deleteFromTree(trailCurrent.rlink); 
       } 
      }//end if 
     } 
    }//end deleteNode   
    //Method to delete the node, to which p points, from the 
    //binary search tree. 
    //Postcondition: The node to which p points is deleted 
    //    from the binary search tree. The reference 
    //    of the root node of the binary search tree 
    //    after deletion is returned. 

    private BinaryTreeNode deleteFromTree(BinaryTreeNode p) { 
     BinaryTreeNode current;  //reference variable to 
     //traverse the tree 
     BinaryTreeNode trailCurrent; //reference variable 
     //behind current 
     if (p == null) { 
      System.out.println("Error: The node to be deleted " 
        + "is null."); 
     } else if (p.llink == null && p.rlink == null) { 
      p = null; 
     } else if (p.llink == null) { 
      p = p.rlink; 
     } else if (p.rlink == null) { 
      p = p.llink; 
     } else { 
      current = p.llink; 
      trailCurrent = null; 

      while (current.rlink != null) { 
       trailCurrent = current; 
       current = current.rlink; 
      }//end while 

      p.info = current.info; 

      if (trailCurrent == null) //current did not move; 
      //current == p.llink; adjust p 
      { 
       p.llink = current.llink; 
      } else { 
       trailCurrent.rlink = current.llink; 
      } 
     }//end else 

     return p; 
    }//end deleteFromTree 
} 

и здесь является основным классом:

/* 
* To change this template, choose Tools | Templates 
* and open the template in the editor. 
*/ 

/** 
* 
* @author Evil Weevil 
*/ 
public class Run { 

    public static void main(String[] args) { 
     BinaryTree a=new BinaryTree(); 
     a.insert("88"); 
     a.insert("75"); 
     a.insert("100"); 
     a.insert("70"); 
     a.insert("20"); 
     a.insert("70");  
     a.insert("14"); 
     System.out.println("InorderTraversal Tree:"); 
     a.inorderTraversal(); 
     System.out.print("\n"); 
     System.out.println("PreorderTraversal Tree:"); 
     a.preorderTraversal(); 
     System.out.print("\n"); 
     System.out.println("PostorderTraversal Tree:");   
     a.postorderTraversal(); 
     System.out.print("\n"); 
     System.out.println(" Tree Node Count:"); 
     System.out.println(a.treeNodeCount()); 
     System.out.println(" Tree Leaves Count:"); 
     System.out.println(a.treeLeavesCount()); 
     System.out.println(" is the Tree Empty :"); 
     System.out.println(a.isEmpty()); 
     System.out.println(" Tree Height(longest chain of nodes):"); 
     System.out.println(a.treeHeight()); 
    } 
} 

Answer 1

Ожидаемый заказ:

"100" "14" "20" ...

, если вы ожидаете

"14" "20" ....

Вы, вероятно, хотите использовать номера istead строк. Причина в том, что строки сравниваются char по char, начиная с левой. Итак, '0' < '4' означает, что 100 отсортировано до 14. Если вам по какой-то причине нужно использовать строки, убедитесь, что они имеют одинаковую длину. Используйте «014» «020» и т. Д.

Answer 2

Если вы наблюдаете за своей структурой данных в памяти с помощью отладчика, вы видите, что каждый узел дерева имеет только один ребенок (всегда левый, кроме «100», который имеет право child), поэтому вывод правильный: у вас есть только один листовой узел, а самая длинная цепочка (это единственная!) состоит из 6 узлов. Очевидно, это не то, чего вы ожидали, поэтому проблема заключается в методе insert(), но этот метод не имеет комментария «postcondition», поэтому неясно, какую логику вставки вы хотите получить.

Ответ Stefan Haustein тоже подходит: тестирование со строками, содержащими цифры, может ввести в заблуждение.