對樹中的節點使用遞歸返回引用不允許更改節點本身

我的數據結構類正在使用樹。我們正在實現一個3元樹，其中包含2個值，引用左，中，右節點（左子樹小於值1，中子樹值在1和值2之間，右子樹大於值2 ）。已經爲Tree類提供了一個接口，並且find，insert和delete方法必須是遞歸的。這將被測試的客戶端代碼反覆使用插入方法來創建樹，並且根開始爲null。對樹中的節點使用遞歸返回引用不允許更改節點本身

我試圖通過在單獨的私有方法中查找父節點，然後根據情況更改返回的節點，遞歸地插入值到樹中。目前的問題是該方法返回作爲根的初始節點，並且因爲根爲空而正確地創建了具有該值的新節點。但是，根仍然爲空。我非常確定這是由於引用和值在Java中工作的方式（與在this article by Jon Skeet中描述的類似於C＃）。考慮到約束條件，我應該如何改變它以允許插入到樹中？下面是樹類中的當前插入方法以及類似的私有方法。

public void insert(AnyType newData) 
{ 
    // If insert node is null, make a new node with newData as first key 
    TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
     insert_node = new TernaryNode<AnyType>(newData); 
    } 
    else 
    { 
     // Get the key that is equal if the insert node is not null 
     if (insert_node.getKey1() == null) 
     { 
      insert_node.setKey1(newData); 
     } 
     else 
     { 
      insert_node.setKey2(newData); 
     } 
    }// end else 
}// end insert 

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node) 
{ 
    TernaryNode<AnyType> current_node = node; 
    if (current_node != null) 
    { 
     if (current_node.getKey1() != item && 
       current_node.getKey2() != item) 
     { 
      // Comparator checks left 
      if (compare.compare(current_node.getKey1(), item) <= -1) 
      { 
       return findNode(item, current_node.left); 
      } // Comparator checks right 
      else if (compare.compare(current_node.getKey2(), item) >= 1) 
      { 
       return findNode(item, current_node.right); 
      }// Comparator checks middle 
      else 
      { 
       return findNode(item, current_node.middle); 
      } 
     }// end while 
    }// end if 
    // Return current node even if it is null 
    return current_node; 
}// end findNode

來源

2009-11-26 Feanor

除非您將某物分配給root成員，否則它將永遠不會獲得值。您的樹可能需要某種外部容器，類似於XML文檔（也是樹）具有與實際文檔根節點不同的外部對象Document。

來源

2009-11-26 22:23:08 Jherico

謝謝Jherico。我更新了這個以澄清爲什麼root從null開始的要求;它是較大樹類的一個字段。 – Feanor 2009-11-26 23:08:25

TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
      insert_node = new TernaryNode<AnyType>(newData); 
      root = insert_node; 
    }

來源

2009-11-26 22:40:43 irreputable

感謝發佈。然而，該方法打算從根開始並從那裏向前移動。如果這個代碼爲null，那麼這個代碼總是會讓root成爲插入節點，這絕對不是我想要的。 – Feanor 2009-11-26 22:46:46

if（root == null）root = insert_node; 您只需在適當的時候將其分配給根。 – irreputable 2009-11-26 22:54:58

對樹中的節點使用遞歸返回引用不允許更改節點本身

回答

相關問題