8 
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;
   }
 }

上記の投稿されたコードは、私のレベル オーダー トラバーサル コードです。このコードは私にとってはうまく機能しますが、私が気に入らないことの 1 つは、明示的に初期化temp_node = NULLしているか、ブレークを使用していることです。しかし、それは私には良いコードではないようです。

これよりもきちんとした実装はありますか、またはこのコードをより良くするにはどうすればよいですか?

4

8 に答える 8

14 
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()' と言うよりも簡潔です。

于 2010-08-28T06:49:49.217 に答える
3

この方法を試すことができます：

struct Node
{
    char data;
    Node* left;
    Node* right;
};
void LevelOrder(Node* root)
{
    if(root == NULL) return;
    queue<Node*> Q;
    Q.push(root);
    while(!Q.empty())
    {
        Node* current = Q.front();
        cout<< current->data << " ";
        if(current->left != NULL) Q.push(current->left);
        if(current->right != NULL) Q.push(current->right);
        Q.pop();
    }
}
于 2016-05-07T10:19:31.793 に答える
2

既存のコードの重大な問題の 1 つは、空のツリー ( root = NULL) で呼び出すとクラッシュすることです。

NULLキューにポインターを含めるかどうかを決定する必要があります。

そうでない場合は、非値のみをキューに入れることができNULLます。

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

    // no tree no level order.
    if(root == NULL) {
        return;
    }

    // push the root to start with as we know it is not NULL.
    q.push(root);

    // loop till there are nodes in the queue.
    while(!q.empty()) {
        // dequeue the front node.
        Node *tmpNode = q.front();
        q.pop();

        // print it..we are sure it is not NULL.
        cout<<tmpNode->value<<" ";

        // enqueue left child if it exists.
        if(tmpNode->left) {
            q.push(tmpNode->left);
        }
        // enqueue right child if it exists.
        if(tmpNode->right) {
            q.push(tmpNode->right);
        }
    }
}

またはNULL、キューに入れることにした場合は、次のことができます。

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

    // push the root..even if it is NULL.
    q.push(root);

    // loop till the queue is not empty.
    while(!q.empty()) {
        // dequeue the front node.
        Node *tmpNode = q.front();
        q.pop();

        // the dequeued pointer can be NULL or can point to a node.
        // process the node only if it is not NULL.     
        if(tmpNode) {       
            cout<<tmpNode->value<<" ";
            q.push(tmpNode->left);
            q.push(tmpNode->right);
        }
    }   
}

大きなツリーには多くのNULL子 (葉ノードの子) があり、後でそれらを処理しない場合にそれらをキューに入れても意味がないため、最初の方法が推奨されます。

于 2011-03-15T07:16:49.460 に答える
1

試す：

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);
   }
 }
于 2010-08-28T07:13:00.503 に答える