二叉树的唯一编号节点

如何在生成二叉树后为每个节点设置索引？二叉树的唯一编号节点

 (a)    (1) 
    (x) (r) =>  (2) (3) 
    (o)(t)(t)(x)  (4)(5)(6)(7)

因此，我可以在特定节点上使用诸如getIndex()之类的调用来返回其索引。

我的树类：

public class BT<E>{ 
    E value; 
    BT<E> left, right; 
    int Index; 

    public BT(E value) 
    { 
     this.value=value; 
    } 

    public BT (E value, BT left, BT right) 
    { 
     this.value = value; 
     this.left = left; 
     this.right = right; 
    }

来源

2015-08-14 RK2015

如果在完全创建树之后再次遍历树，或者在创建树时第一遍期间尝试初始化此索引，那么您还可以吗？ – NoseKnowsAll

简单地遍历你的树一层一层。 – talex

@NoseKnows所有我需要它完成树完全创建后完成。 – RK2015

广度优先遍历。

Queue<BT> queue = new LinkedList<BT>() ; 

public void breadth(BT root) { 
    if (root == null) 
     return; 

    queue.clear(); 
    queue.add(root); 
    int index = 0; 
    while(!queue.isEmpty()){ 
     BT node = queue.remove(); 
     node.Index = index; 
     index++; 
     if(node.left != null) queue.add(node.left); 
     if(node.right != null) queue.add(node.right); 
    } 

}

改编自here。

来源

2015-08-14 16:51:28 Alex

所以你要实现一个程序getIndex(int index)它必须返回你的节点与该索引？

如果是这样，你正在寻找一种有效的方法来表示二叉树。你可以遍历树每次调用getIndex但这不会是有效的...

一个有效的解决方案是将完整二叉树的存储阵列，因为O（1）访问它提供。将索引为n的节点n存储在索引为2*n和(2*n) - 1的子节点中。但是这里的限制是树必须是完整的，并且数组的大小不是可变的（如果二叉树变得太大，应该创建一个更大的数组（通常是两倍大）并且应该复制所有元素）。

这是一个方便的解决方案，因为：

节点连接在O（1）但像addNode()的过程将变得为O摊销（1）。 （*）
节点不必记住它的子节点 - >this.left变为this.left()，执行如下提供的left()。

left()程序的可能实现。

static int[] binaryTreeArray = new int[maxTreeSize]; // BT of integers for example 
... 
public int left() { // returns integer or ... (type of your nodes) 
    return binaryTreeArray[(this.Index)*2]; // O(1) 
}

（*）的addNode()样的程序将在o增加节点（1）（binaryTreeArray[index] = nodeValue;）的大部分时间，但是当binaryTreeArray已满，必须作出更大的数组，它是通常的两倍大（复制O（n））。可以证明，这具有O（1）的摊销成本，但对于这个答案这没有增值。

来源

2015-08-14 16:58:46 HyperZ

如果您在树完全创建后执行此操作，则使用级别遍历遍历的某些内容将可用。这不是非常有效的，但它是直接的递归：

/* Method to set index based on level-order traversal of tree */ 
public void initIndices(BT root) { 
    int maxIndexSoFar = 0; 
    for (int d = 1; d <= root.height(); ++d) 
     maxIndexSoFar = setIndexAtLevel(root, d, maxIndexSoFar); 
} 

/* Method to set index of all nodes at a given level */ 
private int setIndexAtLevel(BT node, int level, int index) { 
    if (tree == null) 
     return index; 
    if (level == 1) { 
     index++; 
     node.setIndex(index); 
     return index; 
    } 
    else if (level > 1) { 
     int newIndex = setIndexAtLevel(node.left, level-1, index); 
     newIndex = setIndexAtLevel(node.right, level-1, newIndex); 
     return newIndex; 
    } 
    return -1; 
}

我将离开你创建height()方法和setIndex()方法。公平的警告，我没有测试过，所以请原谅。

来源

2015-08-14 17:08:56 NoseKnowsAll

二叉树的唯一编号节点

回答

相关问题