home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

N-ary Tree Preorder Traversal ใน C++

สมมติว่าเรามีต้นไม้ n-ary หนึ่งต้น เราต้องหาการข้ามผ่านของโหนดก่อนการสั่งซื้อ

ดังนั้นหากอินพุตเป็นแบบ

N-ary Tree Preorder Traversal ใน C++

แล้วผลลัพธ์จะเป็น [1,3,5,6,2,4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดอาร์เรย์และ

  • กำหนดวิธีการที่เรียกว่า preorder() ซึ่งจะเริ่มต้น

  • ถ้ารูทเป็นโมฆะ −

    • กลับรายการว่าง

  • แทรกค่าของรูทที่ส่วนท้ายของ ans

  • สำหรับเด็กทุกคนในอาร์เรย์ลูกของรูท

    • สั่งซื้อล่วงหน้า(i)

  • กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Node {
public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
class Solution {
public:
   vector<int&g; ans;
   vector<int> preorder(Node* root) {
      if (!root)
         return {};
      ans.emplace_back(root->val);
      for (auto i : root->children)
         preorder(i);
      return ans;
   }
};
main(){
   Solution ob;
   Node *node5 = new Node(5), *node6 = new Node(6);
   vector<Node*> child_of_3 = {node5, node6};
   Node* node3 = new Node(3, child_of_3);
   Node *node2 = new Node(2), *node4 = new Node(4);l
   vector<Node*> child_of_1 = {node3, node2, node4};
   Node *node1 = new Node(1, child_of_1);
   print_vector(ob.preorder(node1));
}

อินพุต

Node *node5 = new Node(5), *node6 = new Node(6);
vector<Node*> child_of_3 = {node5, node6};
Node* node3 = new Node(3, child_of_3);
Node *node2 = new Node(2), *node4 = new Node(4);
vector<Node*> child_of_1 = {node3, node2, node4};
Node *node1 = new Node(1, child_of_1);

ผลลัพธ์

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