c++ - 将二叉树存储在缺失位置为空值的数组中

Question

我想将二叉树存储在数组中，在缺失的节点处为空值。

例如:

输入:

      1
     / \
    2   3
   / \   \
  4   5   6

输出:{1,2,3,4,5,0,6}

我已经尝试对数组中的二叉树进行线性遍历，但我希望在树的缺失节点位置为 null。

std::vector< int > levelorder( tree *root){
    queue<tree*> q; 
    tree* temp;
    q.push(root);
    while(!q.empty()){
        temp=q.front();
        q.pop();
        arr.push_back(temp->data);
        if(temp->left && temp->right)
        {
            q.push(temp->left);
            q.push(temp->right);
        }
        else if(temp->left && !temp->right)
        {
            q.push(temp->left);
            arr.insert(0);
        }
        else if(temp->right && !temp->left)
        {
            q.push(temp->right);
            arr.push_back(0);
        }

    }
    return arr;
}

int main() 
{ 

    tree *root = newNode(1);  
    root->left = newNode(2);  
    root->right = newNode(3);  
    root->left->left = newNode(4);  
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    cout<<"Level Order traversal of binary tree is :"<<endl; 
    levelorder(root);
    for(int i =0; i<arr.size(); i++)
    {
        cout<< arr[i]<<" ";
    } 

    return 0; 
}

我得到输出:{1,2,3,0,4,5,6}但我希望输出为:{1,2,3,4,5,0,6}

Answer 1

算法

以下代码支持丢失子树，并在不存在有意义的节点时立即停止:

std::vector<int> levelorder(tree *root){
    int null_in_queue = 0;
    std::queue<tree*> q;
    std::vector<int> arr;
    q.push(root);
    while(q.size() != null_in_queue){
        tree* temp=q.front();
        q.pop();
        if(!temp)
        {
           arr.push_back(0);
           q.push(nullptr);
           q.push(nullptr);
           null_in_queue++; // One was removed, two were added
        }
        else
        {
            arr.push_back(temp->data);
            q.push(temp->left);
            q.push(temp->right);
            if (!temp->left) null_in_queue++;
            if (!temp->right) null_in_queue++;
        }
    }
    return arr;
}

它将虚拟节点(nullptr)插入队列并统计虚拟节点的数量。当只剩下虚拟节点时，它终止。

复杂度

该算法的时间和内存复杂度为O(n)，其中n 是输出数组的大小。这个数组的大小最多是一棵完整树的节点数(减一)，直到最深的节点。对于深度为 d 的树，该算法的复杂度为 O(2^d)。

详情:循环中的代码是常数(摊销的)并且q vector 包含节点和虚拟节点，其中最多包含2^(d+1)个节点(额外的一行虚拟节点将在算法完成之前添加)。这意味着整个算法将在 O(2^(d+1)) ~ O(2*2^d) ~ O(2^d) 内执行。