Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

พิมพ์ระดับการสั่งซื้อข้ามผ่านบรรทัดต่อบรรทัดในการเขียนโปรแกรม C++


จากไบนารีทรี ฟังก์ชันจะต้องค้นหาระดับการข้ามผ่านของต้นไม้ทีละบรรทัด

การข้ามผ่านลำดับระดับ:Left Root Right ซึ่งหมายความว่าก่อนอื่นให้พิมพ์ลูกด้านซ้ายของโหนดมากกว่าค่าของ root จากนั้นไปที่ชายด์ที่ถูกต้อง แต่ที่นี่เราต้องทำทีละบรรทัดซึ่งจะเริ่มจากด้านซ้ายและจะสิ้นสุดที่ด้านขวา โหนดของไบนารีทรีที่กำหนด

พิมพ์ระดับการสั่งซื้อข้ามผ่านบรรทัดต่อบรรทัดในการเขียนโปรแกรม C++

ต้นไม้ไบนารีที่ให้ไว้ด้านบนจะสร้างผลลัพธ์ต่อไปนี้ -

Level 0: 3
Level 1: 2 1
Level 2: 10 20 30

อัลกอริทึม

START
Step 1 -> create a structure of a node as
   struct node
      struct node *left, *right
      int data
   End
Step 2 -> function to create a node
   node* newnode(int data)
   node *temp = new node
   temp->data = data
   temp->left = temp->right= NULL
   return temp
step 3 -> function for inorder traversal
   void levelorder(node *root)
   IF root = NULL
      Return
   End
   queue<node *> que
   que.push(root)
   Loop While que.empty() = false
      int count = que.size()
      Loop While count > 0
         node *node = que.front()
         print node->data
         que.pop()
      IF node->left != NULL
         que.push(node->left)
      End
      IF node->right != NULL
         que.push(node->right)
      End
      Decrement count by 1
   End
End
Step 4 -> In main() function
   Create tree using node *root = newnode(3)
   Call levelorder(root)
STOP

ตัวอย่าง

#include <iostream>
#include <queue>
using namespace std;
//it will create a node structure
struct node{
   struct node *left;
   int data;
   struct node *right;
};
void levelorder(node *root){
   if (root == NULL)
      return;
   queue<node *> que;
   que.push(root);
   while (que.empty() == false){
      int count = que.size();
      while (count > 0){
         node *node = que.front();
         cout << node->data << " ";
         que.pop();
         if (node->left != NULL)
            que.push(node->left);
         if (node->right != NULL)
            que.push(node->right);
         count--;
      }
   }
}
//it will create a new node
node* newnode(int data){
   node *temp = new node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
int main(){
   // it will generate the binary tree
   node *root = newnode(3);
   root->left = newnode(2);
   root->right = newnode(1);
   root->left->left = newnode(10);
   root->left->right = newnode(20);
   root->right->right = newnode(30);
   levelorder(root);
   return 0;
}

ผลลัพธ์

หากเรารันโปรแกรมข้างต้น มันจะสร้างผลลัพธ์ดังต่อไปนี้

3 2 1 10 20 30