级别订单插入二叉树？

Question

假设给出了一个级别顺序遍历输出.如何从填充了正确位置的数据构建二叉树？

请注意,我不是试图从给定的遍历输出中绘制树,而是从数组中读取遍历数据,然后通过C中的实际编码填充二叉树.

例如:

设a [] = {A,B,C,D,E,F,G}; //数组中的遍历输出

所以级别顺序树看起来像这样:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

假设有一个树节点结构,如下所示:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

现在我正在尝试读取[]值并对此树进行编码,使其看起来像图.有许多级别顺序遍历的例子,但是在二叉树构造的实际编码中找不到任何相关的东西.这有点像"遍历的逆转".

另请注意,这不是功课,但如果有更多人注意到这一点我没有标记问题.:)

Answer 1

这就像BFS,因此您可以使用队列.

请注意,您始终指定左孩子,然后立即分配正确的孩子.所以从包含root的队列开始.在每次迭代时,从队列中弹出节点,然后从数组(或流)中读取接下来的两个值.使第一个成为弹出节点的左子节点并将其推入队列.然后使第二个成为正确的孩子并将其推入队列.依此类推,直到数组(或流)中没有剩余元素.

Answer 2

对于一个完整的(或填充)二叉树很容易的水平遍历转换成任何遍历因为一个节点的位置处的儿童n是在 2n和2n+1当阵列是1-索引并在2n+1和2n+2当阵列是0索引.

因此,您可以轻松地使用该公式将其转换为您最喜欢的遍历顺序,以便将节点插入树中(如预订).

例如递归的伪代码:

void fill( TreeNode* node, char a[], int arrayLength, int n ){
    // n is the position of the current "node" in the array
    if( n < arrayLength ){
        node->data = a[n];
        fill( node->left, a, arrayLength, 2n+1 );
        fill( node->right, a, arrayLength, 2n+2 );
    }
}

Answer 3

一种可能的方案:

char a[SIZE] = {A,B,C,D,E,F,G}; 
    node* func(int index){
        if(index < SIZE){
            node *tmp = new node();
            tmp->data = a[index];
            tmp->left = func(2*index + 1);
            tmp->right = func(2*index + 2);
        }
        return tmp;
    }

树的堆栈跟踪:

                                     A->a[0]
          B->func(2*0 + 1)=[1]                              C->func(2*0 + 2)=[2]
D->func(2*1 + 1)=[3]    E->func(2*1 + 2)=[4]        F->func(2*2 + 1)=[5]     G->func(2*2 + 2)=[6]