Обход уровня порядка двоичного дерева

Question

Обход уровня порядка двоичного дерева

void traverse(Node* root)
{
    queue<Node*> q;

    Node* temp_node= root;

    while(temp_node)
    {
        cout<<temp_node->value<<endl;

        if(temp_node->left)
            q.push(temp_node->left);

        if(temp_node->right)
            q.push(temp_node->right);

        if(!q.empty())
        {
            temp_node = q.front();
            q.pop();
        }
        else
            temp_node = NULL;
   }
 }

Приведенный выше код - мой код обхода ордера уровня. Этот код прекрасно работает для меня, но мне не нравится то, что я явно инициализирую temp_node = NULL или использую break. Но он не кажется мне хорошим кодом.

Есть ли более аккуратная реализация, чем эта, или как мне сделать этот код лучше?

8

c++ algorithm binary-tree breadth-first-search tree-traversal

задан Coding Mash 9 November 2012 в 07:11

2 ответа

Попробуйте:

void traverse(Node* root)
{
    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node* temp_node = q.front();
        q.pop();
        if (temp_node == NULL)
        {   continue;
        }

        cout << temp_node->value << endl;

        q.push(temp_node->left);
        q.push(temp_node->right);
   }
 }

1

ответ дан 5 December 2019 в 08:21

Другие вопросы по тегам:

c++ algorithm binary-tree breadth-first-search tree-traversal

Похожие вопросы:

score 13 · Accepted Answer

void traverse(Node* root)
{
    queue<Node*> q;

    if (root) {
        q.push(root);
    }
    while (!q.empty())
    {
        const Node * const temp_node = q.front();
        q.pop();
        cout<<temp_node->value<<"\n";

        if (temp_node->left) {
            q.push(temp_node->left);
        }
        if (temp_node->right) {
            q.push(temp_node->right);
        }
    }
}

Вот, не более частный случай. И отступ очищается, чтобы его было легче понять.

Альтернативно:

void traverse(Node* root)
{
    queue<Node*> q;

    if (!root) {
        return;
    }
    for (q.push(root); !q.empty(); q.pop()) {
        const Node * const temp_node = q.front();
        cout<<temp_node->value<<"\n";

        if (temp_node->left) {
            q.push(temp_node->left);
        }
        if (temp_node->right) {
            q.push(temp_node->right);
        }
    }
}

Сделано как цикл for. Лично мне нравится дополнительная переменная. Имя переменной является более удобным сокращением, чем постоянное повторение «q.front()».