資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式檢查給定的二叉樹是否為滿二叉樹
給定一棵二叉樹，任務是檢查它是否為滿二叉樹。如果每個節點都有零個或兩個子節點，則稱二叉樹為滿二叉樹。
例如
輸入-1
輸出
1
解釋：除了葉子節點之外，每個節點都有兩個子節點，因此它是一棵滿二叉樹。
輸入-2：
輸出
0
解釋：節點 2 只有一個子節點，因此它不是一棵滿二叉樹。
解決此問題的方法
要檢查給定的二叉樹是否為滿二叉樹，我們可以遞迴地檢查左子樹和右子樹。
- 輸入具有節點及其子節點的給定二叉樹。
- 布林函式 isFullBinaryTree(Node*root) 以根節點作為輸入，如果它是滿二叉樹則返回 True，否則返回 false。
- 在基本條件下，如果根節點為空或為空，則返回 True。
- 如果左子樹和右子樹為空或為空，則返回 True。
- 現在讓我們遞迴地檢查每個左子樹和右子樹並返回輸出。
示例
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isFullBinaryTree(struct treenode * root) {
if (root == NULL) {
return true;
}
if (root -> left == NULL and root -> right == NULL) {
return true;
} else if (root -> left and root -> right) {
return (isFullBinaryTree(root -> left) and isFullBinaryTree(root -> right));
}
return false;
}
int main() {
struct treenode * root = NULL;
root = createNode(1);
root -> left = createNode(2);
root -> right = createNode(3);
root -> left -> right = createNode(4);
root -> left -> left = createNode(5);
root -> right -> left = createNode(6);
if (isFullBinaryTree(root)) {
cout << "1" << endl;
} else {
cout << "0" << endl;
}
return 0;
}執行以上程式碼將生成以下輸出：
輸出
0
解釋：由於給定二叉樹中的所有葉子節點都沒有子節點，因此它不是滿二叉樹。所以，我們得到輸出為 0。
更新於： 2021年2月23日
1K+ 瀏覽量
廣告