0

Java で二分木からヒープを作成しています。私の実装は次のようになります。

public class Heap <P extends Comparable<P>,D> {
  // ATTRIBUTES
  private TreeNode<P,D> root;
  private int size;

  // CONSTRUCTOR
  PriorityQueue() {
    this.root = null;
    this.last = null;
    this.size = 0;
  }

  class TreeNode<P,D> {
    // ATTRIBUTES
    P priority;
    D data;
    TreeNode<P,D> left;
    TreeNode<P,D> right;

    // CONSTRUCTOR
    TreeNode(P priority, D data, TreeNode<P,D> left, TreeNode<P,D> right) {
      this.priority = priority;
      this.data = data;
      this.left = left;
      this.right = right;
    }
    TreeNode(P priority, D data) {
      this(priority, data, null, null);
    }
}

ここで、ノードの n 番目の要素を取得したいと考えています。n をバイナリ文字列に変換し、最初の 1 をポップしてから、0 ごとに左に、1 ごとに右に移動するのが賢明だと思いました。

root.left.left.rightそれはそれほど難しくないように思えますが、今私の問題は、 9 番目の要素に到達するような出力をどのように作成するかです。コピーを取得したいだけではなく、簡単です (以下のgetNode(int n)関数を参照)。そのノードへの参照が必要なので、たとえばその場所に新しいノードを追加できます。

public TreeNode<P,D> getNode(int n) {
  String binString = Integer.toBinaryString(n);
  char[] binChars = binString.substring(1, binString.length()).toCharArray();
  TreeNode<P,D> node = this.root;
  for( char c : getNodePath(n) ){
    if( c == '0' ){
      node = node.left;
    } else if( c == '1' ){
      node = node.right;
    }
  }
  return node;
}

それはJavaでも可能ですか？Python では".left.left.right"String を作成して を使用するだけrunですが、Java ではそれができないようです。

4

1 に答える 1

0

データを構造化した方法では、必要なのはノード n (既に取得している) への参照ではなく、その親への参照です。

.left.left.right の場合

最後のビットを切り取り、 getNode を .left.left で呼び出す必要があります

これにより、ノードの親ノードが得られます。返された親ノードを使用し、切り取ったビット (.right) を使用して参照できるターゲット ノード自体

親の権利

また、そのようにして、parent.right = new-node によってノードを再割り当てできます

ところで、スキームを実装するためにバイナリ文字列を作成する必要はありません。シフト演算子と「ビットごとの AND」を使用するだけです。

于 2014-06-29T20:33:25.240 に答える