資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++移除長度小於K的根到葉路徑上的節點
給定一棵樹，我們需要移除路徑長度小於給定值k的葉子節點，例如：
輸入 -
K = 4.
輸出 -
解釋
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.
我們將使用後序遍歷方式遍歷樹；然後，我們建立一個遞迴函式，如果葉子節點的路徑長度小於K，則移除該節點。
解決方案方法
在這種方法中，我們使用後序遍歷；我們嘗試遞迴地移除路徑長度小於k的葉子節點，以此類推。
示例
上述方法的C++程式碼
#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;
}輸出
E C F B D A H G I E C F B A
上述程式碼的解釋
在這個程式碼中，我們使用一個遞迴函式來遍歷樹並保持左右子樹的狀態。當我們到達葉子節點時，我們檢查到該節點的路徑長度。如果路徑長度小於k，則刪除該節點並返回NULL；否則，程式碼繼續執行。
結論
在本教程中，我們解決了一個問題：使用遞迴移除長度小於K的根到葉路徑上的節點。我們還學習了這個問題的C++程式和遞迴以及我們解決的完整方法。我們可以用其他語言（如C、Java、Python等）編寫相同的程式。希望本教程對您有所幫助。
更新於：2021年11月26日
瀏覽量：117
廣告