按号码获取TreeNode

Question

我正在用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"字符串并使用run，但这在java中似乎是不可能的。

Answer 1

按照您构建数据的方式，您需要的不是对节点n的引用(您已经得到了)，而是对它的父节点的引用。

所以对于.left.left.right

您需要切断最后一位，并使用getNode调用.left.left

这会给你的节点的父母节点。可以通过使用返回的父节点和切断的位(.right)来引用目标节点本身。

parent.right

同样，您可以通过parent.right =新节点重新分配节点。

顺便说一句，您不需要创建二进制字符串来实现您的方案。你只需要使用移位操作符和“按位”