二叉树的唯一编号节点

Question

生成二叉树后如何为每个节点设置索引？

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

所以我可以在特定节点上使用诸如 getIndex() 之类的调用来 return 它的索引。

我的树class:

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;
   }

Answer 1

广度优先遍历。

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。

Answer 2

所以你要实现一个过程 getIndex(int index) 必须 return 你是具有该索引的节点？[=23=]

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

一个有效的解决方案是将 complete 二叉树存储在一个数组中，因为它提供了 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) 的摊销成本，但对于此答案没有附加值。

Answer 3

如果您在完全创建树之后执行此操作，那么使用级别顺序遍历的方法将起作用。它不是非常有效，但它是直接的递归：

/* 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() 方法。公平警告，我根本没有测试过这个，所以请原谅任何打字错误。

二叉树的唯一编号节点

Uniquely number nodes of a Binary Tree

java

tree

recursion

binary-tree