如何在java中为二叉树添加索引?

syqv5f0l  于 2021-06-27  发布在  Java
关注(0)|答案(1)|浏览(363)

在我的例子中,我想通过将深度作为输入来创建一个二叉树。

class BTreeNode<T> {
    BTreeNode<T> left,right;
    int index;
    T value;

    BTreeNode(T value, int index){
        this.index = index;
        this.value = value;
    }
}

class Tree<T> {
    int depth;
    BTreeNode<T> root;

    public static <K> eTree<K> create(int depth){
      if(depth > 0) {
          Tree<K> newtree = new SparseTree<>();
          newtree.root = new BTreeNode<>(null,0);
          newtree.addLevel(newtree.root, 0, depth);
          return newtree;
       } 
      else {
          throw new Error();
       }
    }

    private void addLevel(BTreeNode<T> node, int depth, int deepest){
        if(depth == deepest - 1) {
            return;
        }
        // ???
        node.left = new BTreeNode<>(node.value,node.index+1);
        node.right = new BTreeNode<>(node.value,node.index+2);
        addLevel(node.left,depth + 1,deepest);
        addLevel(node.right,depth + 1,deepest);
    }
}

然后,我想为树中的每个节点相应地添加一个索引。例如,对于具有7个节点(深度==3)的树,每个节点的索引将为0 1 2 3 4 5 6。我可以在代码中做些什么来实现这一点?我做了几次尝试,但都失败了。有什么建议吗?谢谢!

xmjla07d

xmjla07d1#

因为

index_left = 2*index_father+1
index_right = 2*index_father+2

你可以这样做

private void addLevel(BTreeNode<T> node, int depth, int deepest, int index){
    if(depth == deepest - 1) {
        return;
    }
    node.left = new BTreeNode<>(node.value,index*2+1);
    node.right = new BTreeNode<>(node.value,index*2+2);
    addLevel(node.left,depth + 1,deepest, index*2+1);
    addLevel(node.right,depth + 1,deepest,index*2+2);
}

相关问题