在java中使用二進制搜索樹的AddressBook

Question

你好我正在用java編寫一個AddressBook應用程序，我寫了整個程序。唯一的問題是它沒有按預期工作，代碼中沒有錯誤，所以我無法排除它的故障。任何幫助將非常appriciated。

編輯：這不是一個重複的問題，因爲這包括所有的方法。另一個沒有主要的方法，也不完整，因爲它被關閉，我不得不問一個新的問題。說得通？

package com.addressbook; 

public abstract class KeyedItem<KT extends Comparable<? super KT>> { 
private KT searchKey; 

public KeyedItem(KT key){ 
    searchKey = key; 
} 

public KT getKey(){ 
    return searchKey; 
} 
} 




package com.addressbook; 

public class People extends KeyedItem<String> { 
private String address; 
private String phone; 


public People(String n, String a, String p){ 
    super(n); 
    this.address = a; 
    this.phone = p; 
} 

public void setAddress(String a){ 
    address = a; 
} 

public void setPhone(String p){ 
    phone = p; 
} 

public String toString(){ 
    return "Name:" + getKey() + "\nAddress:" + address + "\nPhone:" + phone; 
} 

public String getTheKey(){ 
    return getKey(); 
} 
} 



package com.addressbook; 

public class BinaryNode{ 
// Friendly data; accessible by other package routines 
private People people;  // The data in the node 
private BinaryNode left;  // Left child 
private BinaryNode right; // Right child 
// Constructors 

public BinaryNode(People pe, BinaryNode l, BinaryNode r) { 
    people = pe; 
    left = l; 
    right = r; 
} 

public BinaryNode(People pe) { 
    people = pe; 
    left = right = null; 
} 

public void setData(People p){ 
    people = p; 
} 

public String getSearch(){ 
    return people.getTheKey(); 
} 

public People getData(){ 
    return people; 
} 

public BinaryNode getLeft(){ 
    return left; 
} 

public BinaryNode getRight(){ 
    return right; 
} 
} 



package com.addressbook; 

import com.addressbook.People; 
import com.addressbook.BinaryNode; 

public class AddressBook { 
private BinaryNode root; 

public AddressBook() { 
    super(); 
} 

public AddressBook(People p) { 
    super(); 
    root = new BinaryNode(p); 
} 

public void insert(People p){ 
    insert(p, root); 
} 

public People get(String key) { 
    BinaryNode node = root; 
    while (node != null) { 
     if (key.compareTo(node.getSearch()) == 0) { 
      return node.getData(); 
     } 
     if (key.compareTo(node.getSearch()) < 0) { 
      node = node.getLeft(); 
     } else { 
      node = node.getRight(); 
     } 
    } 
    return null; 
} 

protected BinaryNode insert(People p, BinaryNode node) { 
    if (node == null) { 
     return new BinaryNode(p); 
    } 
    if (p.getTheKey().compareTo(node.getSearch()) == 0) { 
     return new BinaryNode(p, node.getLeft(), node.getRight()); 
    } else { 
     if (p.getTheKey().compareTo(node.getSearch()) < 0) { // add to left subtree 
      insert(p, node.getLeft()); 
     } else {            // add to right subtree 
      insert(p, node.getRight()); 
     } 
    } 
    return node; 
} 

public void remove(String key) { 
    remove(key, root); 
} 

protected BinaryNode remove(String k, BinaryNode node) { 
    if (node == null) { // key not in tree 
     return null; 
    } 
    if (k.compareTo(node.getSearch()) == 0) { // remove this node 
     if (node.getLeft() == null) { // replace this node with right child 
      return node.getRight(); 
     } else if (node.getRight() == null) { // replace with left child 
      return node.getLeft(); 
     } else { 
      // replace the value in this node with the value in the 
      // rightmost node of the left subtree 
      node = getRightmost(node.getLeft()); 
      // now remove the rightmost node in the left subtree, 
      // by calling "remove" recursively 
      remove(node.getSearch(), node.getLeft()); 
      // return node; -- done below 
     } 
    } else {  // remove from left or right subtree 
     if (k.compareTo(node.getSearch()) < 0) { 
      // remove from left subtree 
      remove(k, node.getLeft()); 
     } else {  // remove from right subtree 
      remove(k, node.getRight()); 
     } 
    } 
    return node; 
} 

protected BinaryNode getRightmost(BinaryNode node) { 
    assert(node != null); 
    BinaryNode right = node.getRight(); 
    if (right == null) { 
     return node; 
    } else { 
     return getRightmost(right); 
    } 
} 

protected String toString(BinaryNode node) { 
    if (node == null) { 
     return ""; 
    } 
    return node.getData().toString() + "(" + toString(node.getLeft()) + ", " + 
     toString(node.getRight()) + ")"; 
} 

public static void main(String[] arguments) { 
    AddressBook tree = new AddressBook(); 

    People p1 = new People("person 1", "adresa 1", "404040404"); 
    People p2 = new People("person 2", "adresa 2", "4040434345"); 
    People p3 = new People("person 3", "adresa 3", "346363463"); 
    People p4 = new People("person 4", "adresa 4", "435346346"); 
    People p5 = new People("person 5", "adresa 5", "4363907402"); 

    tree.insert(p1); 
    tree.insert(p2); 
    tree.insert(p3); 
    tree.insert(p4); 
    tree.insert(p5); 

    System.out.println(tree.get("person 1")); 
    } 
} 

Answer 1

一方面：

public void insert(People p){ 
    insert(p, root); 
} 

但方法開始

protected BinaryNode insert(People p, BinaryNode node) { 
    if (node == null) { 
     return new BinaryNode(p); 
    } 

這意味着，同時考慮拼在一起，你總是忽視了新的根，因此你的樹永遠充滿。試試這個：

public void insert(People p){ 
    root = insert(p, root); 
} 

在你忽略的insert內insert返回值也以相同的方式。你應該以類似的方式處理它們。