부모를 나무에 설정하십시오.

Question

빈 노드로 시작하는 허프만 이진 트리가 있습니다.

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. 간단한 과제물과 읽기를 위해 학습 샘플에 게터와 세터를 사용하지 마십시오. 이해하기 어렵습니다.

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. 자바는 여기에 루트

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

한 번 더 생각부터 부모를 설정하는 방법은이

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

---

에 대한 열거 형이라는 좋은 기능이 있습니다. 당신은 나무 건물 기능에 부모를 설정했습니다. 따라서 부모님은 옳았는지 확인하고 다시 설정하지 않는 것이 좋습니다.

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); 
    } 
}