0

空のノード a で始まるハフマン二分木があります。

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

各ノードに親があることを確認する必要があるだけですが、ここからどこから始めればよいかわかりません..何か助けはありますか?

4

1 に答える 1

0

役立つかもしれないコードへのコメント

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には、このためのEnumsと呼ばれる優れた機能があります

     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

もう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);
    }
}
于 2013-04-17T06:48:04.107 に答える