Thứ tự Traversal của cây nhị phân

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

Mã được đăng ở trên là mã truyền tải đơn hàng cấp của tôi. Mã này hoạt động tốt cho tôi nhưng Một điều tôi không thích là tôi đang khởi tạo rõ ràng temp_node = NULL hoặc tôi sử dụng lệnh ngắt. Nhưng nó không có vẻ là một mã tốt cho tôi.

Có triển khai gọn gàng hơn điều này hay làm cách nào để tôi có thể làm cho mã này tốt hơn?

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

Không có trường hợp đặc biệt nào khác. Và thụt đầu dòng được làm sạch để nó có thể được hiểu dễ dàng hơn.

Hoặc:

Xong lên như một vòng lặp for. Cá nhân, tôi thích biến phụ. Tên biến là viết tắt đẹp hơn là nói 'q.front() `mọi lúc.

Answer 2

Hãy thử:

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

Một vấn đề nghiêm trọng với mã hiện tại của bạn là nó bị treo khi nó được gọi là trên một cây rỗng (root = NULL).

Bạn cần quyết định xem bạn có muốn có NULL con trỏ trong hàng đợi hay không.

Nếu không, bạn chỉ có thể enqueue không NULL giá trị.

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

Ngoài ra nếu bạn quyết định có NULL trong hàng đợi bạn có thể làm:

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

Phương pháp đầu tiên được ưa chuộng như một cây lớn có rất nhiều NULL trẻ em (trẻ em của các nút lá) và có là không có điểm trong việc họ enqueued trong hàng đợi khi chúng tôi sau đó chỉ không xử lý chúng.

Answer 4

Bạn có thể thử cách này:

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

Tôi nghĩ rằng đoạn mã trên cho phép in traversal trật tự mức ở định dạng mảng. Mã này có thể giúp viết giải pháp dưới dạng thứ tự cấp.

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

Output:

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

Answer 6

Giải pháp của tôi Java sử dụng cấu trúc dữ liệu Queue và thuật toán 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); 
       } 
    }