在樹中設置父項

Question

我有一個以空節點a開頭的huffman二叉樹。

A指向左節點和右節點，它們也指向左右節點。有這個樹後可以遞歸地設置每個節點的父節點嗎？

這是我想到的代碼：

public Node setParents(Node n) 
{ 
    if(n.getZero() == null && n.getOne() == null) 
    { 
     return n; 
    } 
    Node a = setParents(n.getZero()); // Zero being left 
    a.setParent(n); 
    Node b = setParents(n.getOne()); // One being right. 
    b.setParent(n); 
} 

下面是我目前使用的優先級隊列值進行排序最小到最大創建樹。

public Node createTree(PriorityQueue<Node> pq) 
{ 

    while(pq.size() > 1) 
    { 
     Node n = new Node(); 

     Node a = pq.poll(); 
     if(pq.size() > 0) 
     { 
      Node b = pq.poll(); 
      n = new Node(a.getFrequency() + b.getFrequency()); 
      n.setZero(a); 
      a.setWhich(0); 
      a.setParent(n); 
      n.setOne(b); 
      b.setWhich(1); 
      b.setParent(n); 
     } 
     else 
     { 
      n = new Node(a.getFrequency()); 
      n.setZero(a); 
      a.setWhich(0); 
      n.setParent(n); 
      n.setOne(null); 
     } 
     pq.add(n); 
    } 
    Node n = pq.poll(); 
    n.setParent(null); 
    setParents(n.getZero()); 
    setParents(n.getOne()); 
    return n; 
} 

我只需要確保每個節點都有父母，我不知道從哪裏開始從這裏。任何幫助？

Answer 1

對您的代碼的某些評論可能有所幫助

1。不要在你的研究樣本中使用getter和setter進行簡單的作業和閱讀，他們很難理解。

2。如果您準備一些物品，請勿將此製劑與他人混合使用

 n.setZero(a); 
     a.setWhich(0); 
     a.setParent(n); 
     n.setOne(b); 

3。據我所知，有機會獲得NPE

  if(pq.size() > 0) { 
       Node b = pq.poll(); 
      } 
    } 
    Node n = pq.poll(); 
    n.setParent(null);  <- n can be null 

4。 Java有所謂的枚舉不錯的功能，這

 a.setWhich(0); 
    b.setWhich(1); 

---

下面是如何設置從根

public void fixParents(Node parentNode) 
{ 
    if (parentNode.zero != null) { 
     parentNode.zero.parent = parentNode; 
     fixParents(parentNode.zero); 
    } 
    if (parentNode.one != null) { 
     parentNode.one.parent = parentNode; 
     fixParents(parentNode.one); 
    } 
} 

UPD

還有一個想法開始的父母。您在您的樹木建築功能中設置父母。所以你應該檢查父母是否正確，但不要重新設置它們。

public void checkParents(Node parentNode) throws Exception 
{ 
    if (parentNode.zero != null) { 
     if (parentNode.zero.parent != parentNode) { 
      throw new Exception(here include info about the parentNode.zero); 
     } 
     checkParents(parentNode.zero); 
    } 
    if (parentNode.one != null) { 
     if (parentNode.one.parent != parentNode) { 
      throw new Exception(here include info about the parentNode.one); 
     } 
     checkParents(parentNode.one); 
    } 
}