C ++ Loại bỏ các nút trên rễ đến các đường dẫn lá có độ dài

Ví dụ, cho một cây và chúng ta cần loại bỏ nút lá của đường dẫn có độ dài nhỏ hơn k đã cho.

Đầu vào -

K = 4.

Đầu ra -

Giải thích

The paths were :
1. A -> B -> C -> E length = 4
2. A -> B -> C -> F length = 4
3. A -> B -> D length = 3
4. A -> G -> H length = 3
5. A -> B -> I length = 3
Now as you can see paths 3, 4, 5 have length of 3 which is less than given k so we remove the leaf nodes of these paths i.e. D, H, I.
Now for path 4 and 5 when H and I are removed we notice that now G is also a leaf node with path length 2 so we again remove node G and here our program ends.

Chúng tôi sẽ đi qua cây theo định dạng thứ tự sau; sau đó, chúng tôi tạo một hàm đệ quy loại bỏ các nút lá của chúng tôi nếu độ dài đường dẫn của chúng nhỏ hơn K.

Phương pháp tiếp cận để tìm giải pháp

Trong cách tiếp cận này, bây giờ chúng ta duyệt theo thứ tự sau; chúng tôi cố gắng loại bỏ đệ quy các nút lá có độ dài đường dẫn nhỏ hơn k và tiếp tục như vậy.

Ví dụ

Mã C ++ cho phương pháp tiếp cận trên

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char data;
    Node *left, *right;
};
Node *newNode(int data){ // inserting new node
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
Node *trimmer(Node *root, int len, int k){
    if (!root) // if root == NULL then we return
        return NULL;
    root -> left = trimmer(root -> left, len + 1, k); // traversing the left phase
    root -> right = trimmer(root -> right, len + 1, k); // traversing the right phase
    if (!root -> left && !root -> right && len < k){
        delete root;
        return NULL;
    }
    return root;
}
Node *trim(Node *root, int k){
    return trimmer(root, 1, k);
}
void printInorder(Node *root){
    if (root){
        printInorder(root->left);
        cout << root->data << " ";
        printInorder(root->right);
    }
}
int main(){
    int k = 4;
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('G');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->left->left->left = newNode('E');
    root->left->left->right = newNode('F');
    root->right->left = newNode('H');
    root->right->right = newNode('I');
    printInorder(root);
    cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

Đầu ra

E C F B D A H G I
E C F B A

Giải thích về Quy tắc trên

Trong đoạn mã này, chúng ta đang sử dụng một hàm đệ quy đang duyệt qua cây của chúng ta và giữ các thống kê của cây con bên trái và bên phải. Bây giờ chúng ta đến một nút lá; chúng tôi kiểm tra độ dài đường dẫn cho đến nút đó. Nếu độ dài đường dẫn nhỏ hơn, thì chúng ta xóa nút này, và sau đó chúng ta trả về NULL; nếu không, mã vẫn tiếp tục.

Kết luận

Trong hướng dẫn này, chúng tôi giải quyết vấn đề Xóa các nút trên đường dẫn gốc đến lá có độ dài