Program C++ untuk mengalih keluar nod yang tidak memenuhi laluan dan lebih besar daripada atau sama dengan k

Dalam masalah ini, kami mempunyai pokok binari yang laluannya dari nod akar ke nod daun ditakrifkan sepenuhnya. Jumlah semua nod dari nod akar ke nod daun mestilah lebih besar daripada atau sama dengan nilai malar k. Oleh itu, kita perlu mengalih keluar semua nod dalam laluan tersebut yang jumlahnya kurang daripada k, supaya laluan yang tinggal dalam pokok akan lebih besar daripada k. Perkara penting yang perlu diingat di sini ialah nod mungkin sebahagian daripada banyak laluan, jadi nod tersebut hanya dialih keluar jika jumlah semua laluan yang menuju ke nod itu

Dari nod akar ke nod daun, kita boleh mengira jumlahnya. Apabila panggilan rekursif ke nod selesai dan kawalan kembali, kita boleh menyemak sama ada jumlah laluan kiri dan kanan

Andaikan kita ada 150 K dan pokok seperti ini -

                  10
                  /\
                 20 30
                /\   /\
              5  35 40 45
                 /\     /\
               50  55 60  65
                   /\  /  /
                 70 80 90 100

Jika kita melihat bahawa jumlah akar laluan->kiri->kiri ialah 10 + 20 + 5, iaitu 25, kurang daripada 150, kita perlu memangkasnya dan mengeluarkan 5. Selepas itu, mari kita nilai 10->30->40. Ia kurang daripada 150, jadi 40 dipadamkan.

Sekarang kita melihat laluan lain 10->20->35->50, jumlah 115 adalah kurang daripada 150, jadi kita padamkan 50. Sekarang laluan kita yang tinggal ialah

10->20->35->55->70 ;
10->20->35->55->80 ;
10->30->45->60->90 ;
10->30->45->65->100 ;

Jumlah semua laluan adalah lebih daripada 150, jadi kita tidak perlu memangkas lagi.

Contoh

Berikut ialah program C++ yang menunjukkan cara mengalih keluar nod yang tidak berada dalam mana-mana laluan dan jumlahnya lebih besar daripada atau sama dengan sebarang nilai malar k -

#include <iostream>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
Node* removeNodesWithPathSumLessThanK(Node* root, int k, int& sum) {
   if(root == NULL) return NULL;
   int leftSum, rightSum;
   leftSum = rightSum = sum + root->value;
   root->left = removeNodesWithPathSumLessThanK(root->left, k, leftSum);
   root->right = removeNodesWithPathSumLessThanK(root->right, k, rightSum);
   sum = max(leftSum, rightSum);
   if(sum < k) {
      free(root);
      root = NULL;
   }
   return root;
}
void printInorderTree(Node* root) {
   if(root) {
      printInorderTree(root->left);
      cout << root->value << " ";
      printInorderTree(root->right);
   }
}
int main() {
   int k = 150;
   Node* root = new Node(10);
   root->left = new Node(20);
   root->right = new Node(30);
   root->left->left = new Node(5);
   root->left->right = new Node(35);
   root->right->left = new Node(40);
   root->right->right = new Node(45);
   root->left->right->left = new Node(50);
   root->left->right->right = new Node(55);
   root->right->right->left = new Node(60);
   root->right->right->right = new Node(65);
   root->left->right->right->left = new Node(70);
   root->left->right->right->right = new Node(80);
   root->right->right->left->left = new Node(90);
   root->right->right->right->left = new Node(100);
   int sum = 0;
   cout << "Inorder tree before: ";
   printInorderTree(root);
   root = removeNodesWithPathSumLessThanK(root, k, sum);
   cout << "\nInorder tree after: ";
   printInorderTree(root);
   return 0;
}

Output

Inorder tree before: 5 20 50 35 70 55 80 10 40 30 90 60 45 100 65 
Inorder tree after: 20 35 70 55 80 10 30 90 60 45 100 65 

Pokok kami yang telah dipangkas sepenuhnya -

                  10
                  / \
                 20  30
                 \     \
                 35     45
                  \     /\
                  55   60 65
                  /\    /  /
                 70 80 90 100

Kesimpulan

Seperti yang dapat kita lihat, selepas pemerhatian awal, kita boleh menggunakan DFS dan mengalih keluar nod dengan mengira jumlah nod itu apabila fungsi rekursif kembali daripada setiap panggilan. Secara keseluruhannya, ini adalah pemerhatian dan metodologi yang mudah.

Atas ialah kandungan terperinci Program C++ untuk mengalih keluar nod yang tidak memenuhi laluan dan lebih besar daripada atau sama dengan k. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!