在Java中的二叉搜索樹可視化

Question

您好我目前正在做我的項目（算法可視化工具）的測試階段。我遇到了我的BST刪除方法的問題。

public boolean delete(String key) { 
boolean deleted = true; 
boolean finished=false; 
BNode current = root; 
BNode prev = null; 
while (!finished) { 
    if (key.compareTo(current.key) > 0) { 
    prev = current; 
    current = current.right; 
    this.repaint(); 
    } 
    else if (key.compareTo(current.key) < 0) { 
    prev = current; 
    current = current.left; 
    this.repaint(); 
    } 
    else if (key.compareTo(current.key) == 0) { 
     finished=true; 
     this.repaint(); 
    } 

} 

if (check(current) == 0) { 
    if(current==root) 
    { 
     root=null; 
     xPos=400; 
     yPos=60; 
     this.repaint(); 
    } 
    else 
    { 
     if (current.key.compareTo(prev.key) > 0) { 
      prev.right = null; 
      this.repaint(); 
     } 
     else if(current.key.compareTo(prev.key) < 0) { 
      prev.left = null; 
      this.repaint(); 
     } 
    } 

} 
else if (check(current) == 1) { 
    if(current==root) 
    { 
     prev=current; 
     if (current.left != null) { 
      current=current.left; 
      prev.key=current.key; 
      prev.left = current.left; 
      this.repaint(); 
     } 
     else { 
      current=current.right; 
      prev.key=current.key; 
      prev.right = current.right; 
      this.repaint(); 
     } 
    } 
    else 
    { 

    if (current.key.compareTo(prev.key) > 0) { 
    if (current.left != null) { 
     prev.right = current.left; 
     this.repaint(); 
    } 
    else { 
     prev.right = current.right; 
     this.repaint(); 
    } 
    } 
    else if(current.key.compareTo(prev.key) < 0) { 
    if (current.left != null) { 
     prev.left = current.left; 
     this.repaint(); 
    } 
    else { 
     prev.left = current.right; 
     this.repaint(); 
    } 
    } 
    } 
} 
else if (check(current) == 2) { 
    BNode temp = inord(current); 
    if(current==root) 
    { 
     root.key=temp.key; 
     this.repaint(); 
    } 
    else 
    { 

     if (current.key.compareTo(prev.key) > 0) { 
     prev.right.key = temp.key; 
     this.repaint(); 
    } 
    else { 
     prev.left.key = temp.key; 
     this.repaint(0); 
    } 
    } 
} 

return deleted;} 

BST類本身的代碼要長得多。除了當我嘗試刪除沒有子節點的節點時，我使用例9和10作爲輸入（嘗試刪除10）或5和12（嘗試刪除12）但是從不如果我用例如4和8（嘗試刪除8）或9，6和5.我認爲問題是與compareTo。

int check(BNode a) { 
int ret; 
if ((a.left != null) && (a.right != null)) { 
    ret = 2; 
} 
else if ((a.left == null) && (a.right == null)) { 
    ret = 0; 
} 
else { 
    ret = 1; 
} 
return ret;} 

我真的需要幫助this.I可以張貼全班如果需要的話.. 謝謝！

Answer 1

就在幾個注意事項：

1. 如果傳遞null檢查，你會得到一個NPE那裏。
2. if(check(current) == 0)等 - >你應該檢查一次，然後執行，如果（甚至交換機）

例2：

int result = check(current); 
switch(result) { 
    case 0: 
    //do whatever is appropriate 
    break; 
    case 1: 
    //do whatever is appropriate 
    break; 
    case 2: 
    //do whatever is appropriate 
    break; 
    default: 
    //should never happen, either leave it or throw an exception if it ever happens 
} 

編輯：//其實，忘記了這個編輯，剛看到這不應該發生，但它仍然不是一個好作風

你也有這樣的事情在你的代碼：

if (current.left != null) { 
    current=current.left; 
    prev.key=current.key; 
    prev.left = current.left; 
    this.repaint(); 
} 
else { 
    current=current.right; //this might be null 
... 
} 

如果current.left爲空且current.right爲空，則current之後將爲空。