c++ - 是否有任何有效的方法来填充平衡树结构

Question

我有一个平衡的二叉树结构:

节点 0 在深度 0 是根。 根的左 child 是1，右 child 是2，依此类推。

请看图片:

树的总深度为 N。此 N 是问题的唯一参数。 N 层的节点被指定为叶节点。

我正在使用以下节点结构存储这棵树。

struct node_s{
    int n, depth, parent;//n is node number
    int nodescendents;//number of descendents of the current node
    std::vector<int> descendents;//Descendents in ascending order
    int lchild, rchild;//Immediate left child and right child
    std::vector<int> lchildleaves;//leaf nodes that descend from the immediate 
                                                      //left child
    std::vector<int> rchildleaves;//leaf nodes that descend from the immediate 
                                                      //right child
};

我打算将树本身存储为:

std::vector<node_s> tree;

有没有一种方法可以使用简单的代数以数字方式有效地填充树 vector ，大致如下:

//Creating the nth node, beginning from 0th node, then 1st node and so on
nodes_s node;
//populate all data structures of the nth node
//precisely, here, there are loops, algebraic calculations, etc., that can help 
//populate all of the node_s data members.
tree.push_back(node);

目前我能想到的唯一方法是显式构建一个图并运行某种 Dijkstra 算法来计算每个节点的这些数据结构值。

Answer 1

对于节点k，关键点是识别它在图中的位置，以便识别它的父节点，它是左 child 还是右 child 。

对于节点k，它的秩r[k]等于floor(log2(k+1))，它在秩中的位置等于p[k] = k - 2^r[k] + 1

则k由对(r[k], p[k])定位

相反，k = 2^r[k] + p[k] - 1

然后它的父节点位于 (r[k]-1, floor(p[k]/2)) -> node index = 2^r + p - 1

如果 k%2 == 1，则 k 是左 child

我想剩下的很简单