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

PHPz
Lepaskan: 2023-09-14 11:25:07
ke hadapan
892 orang telah melayarinya

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
Salin selepas log masuk

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 ;
Salin selepas log masuk

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;
}
Salin selepas log masuk

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 
Salin selepas log masuk

Pokok kami yang telah dipangkas sepenuhnya -

                  10
                  / \
                 20  30
                 \     \
                 35     45
                  \     /\
                  55   60 65
                  /\    /  /
                 70 80 90 100
Salin selepas log masuk

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!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!