通过编号获取TreeNode

我从java中的二叉树创建堆。我的实现如下所示：通过编号获取TreeNode

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中似乎不可能。

来源

2014-06-29 MrLoh

你已经结构化的数据，你需要的是不节点n（您已获得）的参考的方式，但它的父级的引用。

所以对于.left.left.right

需要切断的最后一位，并调用getNode与.left.left

，这将使你的节点的父节点。目标节点本身可以通过返回的父节点，并使用你切断位（.right）

parent.right

而且这样你可以通过重新分配= parent.right新的节点指-Node

顺便说一句，你不需要开发出实现您的方案中的二进制字符串。你只需要使用移位运算符和“按位与”

来源

2014-06-29 20:33:25 ac3

那么，为什么我需要去的家长，什么是只是要孩子的问题？而且我怎样才能最好的返回父母和左边或右边的数字，因为在Java中没有元组。（对不起，我是新来的java） – MrLoh

哦，gotcha。我需要改变父母的权利，以切实改变父母的权利。我可以直接去n/2的父节点，用n％2得到左值或右值。 – MrLoh

是的，这或多或少是你要做的，但我感觉你混合的东西，并做了超过必要的事情。例如，如果你正在使用二进制方案，那么getNode（n >> 1）将会给你你的父母，并且（n＆1）会告诉你它是你的孩子的左边还是右边。两者都是按位运算符 - 在python中应该相同。我没有看到你已经接受了答案，但无论如何，很高兴知道这与你正在寻找的东西差不多。是的，一种新语言需要一些时间才能习惯。 – ac3

通过编号获取TreeNode

回答

相关问题