向BST插入節點時出現無限循環

Question

我有一種按照字母順序在BST中插入節點的方法，但是當我比較兩個字符串時我有一個無限循環，我認爲當它通過比較時值不會改變所以它再次與相同的值進行比較，導致無限循環。我認爲aux和T節點沒有使用遞歸方法更新值，因此它會反覆比較相同的值。

class BST { 

    BSTNode root; 

    public BST() { 
     root = null; 
    } 

    BSTNode aux = new BSTNode(); 

    BSTNode insertNames(BSTNode T , int data, String name, double salary) { 
     if (root == null) { 
      T = new BSTNode(); 
      T.setName(name); 
      root = T; 
     } else { 
      aux = root; 

      if (name.compareTo(aux.getName()) < 0) 
       aux.setLeft(insertNames(aux.getLeft(),data, name, salary)); 
      else if (name.compareTo(aux.getName()) >= 0) 
       aux.setRight(insertNames(aux.getRight(),data, name, salary)); 
     } 

     return T; 
    }  
} 

class Main{ 
public static void main(String[] args){ 

     BST alpha=new BST(); 
     BSTNode root = new BSTNode(); 
     alpha.insertNames(root, 0, "Roy", 0); 
     alpha.insertNames(root, 0, "Joseph", 0); 
} 
} 

Answer 1

package com.gati.dsalgo.string; 

class BST { 

    BSTNode root; 

    public BST() { 
     root = null; 
    } 

    void insertNames(int data, String name, double salary) { 
     root = insertNames(root, data, name, salary); 
    } 

    BSTNode insertNames(BSTNode root, int data, String name, double salary) { 
     if (root == null) { 
      root = new BSTNode(); 
      root.setName(name); 
      return root; 
     } 

     if (name.compareTo(root.getName()) < 0) 
      root.setLeft(insertNames(root.getLeft(), data, name, salary)); 
     else if (name.compareTo(root.getName()) >= 0) 
      root.setRight(insertNames(root.getRight(), data, name, salary)); 

     return root; 
    } 
} 

public class Main1 { 
    public static void main(String[] args) { 

     BST alpha = new BST(); 
     alpha.insertNames(0, "Roy", 0); 
     alpha.insertNames(0, "Joseph", 0); 
     System.out.println("hello"); 
    } 
} 

class BSTNode { 
    private String name; 
    BSTNode left; 
    BSTNode right; 

    public void setName(String name) { 
     this.name = name; 

    } 

    public void setRight(BSTNode right) { 
     this.right = right; 
    } 

    public void setLeft(BSTNode left) { 
     this.left = left; 
    } 

    public BSTNode getRight() { 

     return right; 
    } 

    public BSTNode getLeft() { 
     return left; 
    } 

    public String getName() { 

     return name; 
    } 

} 

Answer 2

請在遞歸結束邏輯中返回節點。

 /* If the tree is empty, return a new node */ 
if (root == null) { 
    root = new BSTNode(); 
    root.setName(name); 
    return root; 
} 

/* Otherwise, recur down the tree */ 
if (name.compareTo(root.getName()) < 0) 
    root.setLeft(insertNames(root.getLeft(), data, name, salary)); 
else if (name.compareTo(aux.getName()) >= 0) 
    root.setRight(insertNames(root.getRight(), data, name, salary)); 

/* return the (unchanged) node pointer */ 
return root; 

，或者可以解決迭代的方式

if (localRoot == null) { 
    newNode = new Node <V> (value, null); 
    root = newNode; 
    size++; 
    return true; 
} 
if (comparator != null) { 
//Some code 
} else { 
    Comparable << ? super V > v = (Comparable << ? super V >) value; 
    while (localRoot != null) { 
     parent = localRoot; 
     cmp = v.compareTo(localRoot.getValue()); 
     if (cmp < 0) { 
      localRoot = localRoot.getLeftChield(); 
     } else if (cmp > 0) { 
      localRoot = localRoot.getRightChield(); 
     } else { 
      localRoot.incrementBy(nCopies); 
      return true; 
     } 
    } 
    newNode = new Node <V> (value, parent); 
    if (cmp < 0) { 
     parent.setLeftChield(newNode); 
    } else if (cmp > 0) { 
     parent.setRightChield(newNode); 
    } 
    size++; 
    return true; 
} 
return false;