c++ - 向完整树中添加节点

Question

我正在尝试用 C++ 从头开始​​制作完整的树:

1st node = root
2nd node = root->left
3rd node = root->right
4th node = root->left->left
5th node = root->left->right
6th node = root->right->left
7th node = root->right->right

如果树看起来像这样:

                 NODE
              /        \
          NODE          NODE
       /        \    /        \
    NODE      NODE  NODE      NODE
    /
NEXT NODE HERE

我将如何检测下一个节点的去向，以便我可以只使用一个函数来添加新节点？例如，第 8 个节点将放置在 root->left->left->left

目标是通过一个简单的 for 循环将 100 个节点放入树中，其中包含 insert(Node *newnode) 而不是一次执行一个。它会变成丑陋的东西，例如:

100th node = root->right->left->left->right->left->left

Answer 1

使用队列数据结构来完成构建完整的二叉树。 STL提供std::queue .

示例代码，其中函数将根据您的要求在循环中使用。我假设队列已经创建(即为其分配内存):

// Pass double pointer for root, to preserve changes
void insert(struct node **root, int data, std::queue<node*>& q)
{
    // New 'data' node
    struct node *tmp = createNode(data);

    // Empty tree, initialize it with 'tmp'
    if (!*root)
        *root = tmp;
    else
    {
        // Get the front node of the queue.
        struct node* front = q.front();

        // If the left child of this front node doesn’t exist, set the
        // left child as the new node.
        if (!front->left)
            front->left = tmp;

        // If the right child of this front node doesn’t exist, set the
        // right child as the new node.
        else if (!front->right)
            front->right = tmp;

        // If the front node has both the left child and right child, pop it.
        if (front && front->left && front->right)
            q.pop();
    }

    // Enqueue() the new node for later insertions
    q.push(tmp);
}