通過編號獲取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

回答

相關問題