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

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;

有没有一种方法可以使用简单的代数在数值上有效地填充 tree 向量，大致如下：

//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，关键是要识别它在图中的位置，才能识别它的parent，是左还是右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

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

k 是左 child if k%2 == 1

我想剩下的很简单

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

Are there any efficient ways to populate a balanced tree structure

c++

algorithm

tree

binary-tree