樹的Java插入

Question

我有一棵樹的問題一個問題。代碼中沒有錯誤;這只是一個錯誤的輸出。問題是當我插入「100」時，它會給出錯誤的樹葉數和高度，並且中序遍歷是錯誤的。下面是二叉樹類：

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」 ......

你可能想使用數字而不是字符串。原因在於字符串從char開始，從左側開始逐字比較。因此，'0'<'4'表示100在14之前排序。如果由於某種原因需要使用字符串，請確保它們具有相同的長度。使用「014」「020」等

Answer 2

如果你使用調試器在內存中觀察你的數據結構，你會發現樹的每個節點只有一個子節點（總是左邊的節點，除了「100」孩子），所以輸出是正確的：你只有一個葉節點，最長的鏈（它是唯一的！）由6個節點組成。很明顯，這不是你期待的，所以問題在於insert（）方法，但是這個方法沒有「後置條件」註釋，所以你不清楚你想要獲得什麼樣的插入邏輯。

斯特凡Haustein的答案是合適太：含有數字的字符串測試可能會產生誤導。