資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 編寫程式計算樹的大小 - 遞迴
在這個問題中，我們給定一棵樹，我們的任務是建立一個程式，使用遞迴來計算樹的大小。
樹的大小是樹中存在的節點總數。
讓我們舉個例子來理解這個問題，
上面這棵樹的大小是 5。
為了找到樹的大小，我們將不得不加上左子樹和右子樹的大小，然後加 1。遞迴函式將被呼叫到樹的左右兩個子樹。如果沒有找到子樹，則返回 0。
上面例子使用此方法解決
為了找到樹的大小，
size(3) = size(5) + size(7) + 1
size(3) = (size(1) + size(9) + 1) + 1 + 1
size(3) = (1 + 1 + 1) + 1 + 1
size(3) = 5
程式說明我們解決方案的工作原理，
示例
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int findSize(node* node) {
if (node == NULL)
return 0;
else
return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(7);
root->left->left = insertNode(1);
root->left->right = insertNode(5);
root->right->left = insertNode(2);
cout<<"The size of the given tree is "<<findSize(root);
return 0;
}輸出
The size of the given tree is 6
更新於: 2020-04-20
2K+ 次檢視
廣告