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

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. Но для меня это не очень хороший код.

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

Answer 1

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

Там, не более специальный чехол. И углубление очищается, поэтому его легче понять.

В качестве альтернативы:

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

Answer 2

Try:

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

Answer 3

Одной из серьезных проблем с существующим кодом это происходит сбой при вызове на пустом дереве (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 детей (дети листовых узлов) и там не имеет смысла заставлять их ставить в очередь, когда мы позже просто не обрабатываем их.

Answer 4

Вы можете попробовать этот способ:

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(); 
    } 
} 

Answer 5

Я думаю, что выше фрагменты кода позволяют печатать обход заказа уровня в формате массива. Этот код может помочь написать решение в виде порядка уровня.

vector<vector<int>> levelOrder(TreeNode* root) { 
    vector<vector<int>> a ; 
    vector<int> b; 
    if (root == NULL) return a; 
    std::queue<TreeNode *> q; 
    q.push(root); 
    int nodeCount ; 
    TreeNode* temp; 
    while(true){ 
     nodeCount = q.size(); 
     if (nodeCount == 0) break; 
     while(!nodeCount){ 
      temp = q.front(); 
      b.push_back(temp->val); 
      q.pop(); 
      if(temp->left != NULL) q.push(temp->left); 
      if(temp->right!= NULL) q.push(temp->right); 
      nodeCount-- ; 
     } 
     a.push_back(b); 
     b.resize(0); 
    } 
    return a; 
} 

Выход:

[ [1], 
    [2,3], 
    [4,5] 
] 

Answer 6

решение My Java с использованием структуры данных очереди и BFS алгоритм:

void levelOrder(Node root) { 
     //LinkedList is class of Queue interface 
     Queue<Node> queue=new LinkedList<>(); 
     queue.add(root); 

     //Using BFS algorithm and queue used in BFS solution 
     while(!queue.isEmpty()) { 
       Node node=queue.poll(); 
       System.out.print(node.data+" "); 
       if(node.left!=null) 
       queue.add(node.left); 
       if(node.right!=null) 
       queue.add(node.right); 
       } 
    }