Как судить, все элементы очереди равны NULL, не разрушая очередь - PullRequest
Новая
       4

Как судить, все элементы очереди равны NULL, не разрушая очередь

0 голосов
/ 07 октября 2019

Вот мотивация этого вопроса:

Для level traversal of binary tree, если я хочу вывести дерево, включающее узлы "NULL", например, дерево (NULL означает отсутствие узла)

1

NULL * 2

NULL, NULL, 3

должно быть выведено как: 1, NULL, 2, NULL, NULL, 3

Одной из модификаций следующего кода является добавление 

if (!front.left)
{
    q.push(NULL);
    q.push(NULL);
}

Так же, как и front.right, и мы должны оценить условие остановки: когда все элементы q равны NULL без разрушения q.

Если вы не понимаете модификацию, вы можете просто проигнорировать ее. И есть ли какой-либо другой хороший способ достичь такой цели обхода уровня двоичного дерева?

Код level traversal of binary tree: 

struct TreeNode
{
    int val = 0;
    TreeNode *left = NULL;
    TreeNode *right = NULL;
    TreeNode(int val) : val(val) {}
};

void levelOrder(TreeNode *node) {
    queue<TreeNode*> q;
    q.push(node);

    while (!q.empty())
    {
        TreeNode* front = q.front();
        printf("%d,", front->val);
        q.pop();
        if (front->left) q.push(front->left);
        if (front->right) q.push(front->right);
    }
}
...