資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中二叉樹完整節點計數（迭代和遞迴）
給定一個二叉樹，任務是使用迭代和遞迴方法計算二叉樹中完整節點的數量。完整節點是指同時具有左右兩個子節點，且子節點均不為空的節點。請注意，在完整節點中，我們只考慮恰好有兩個子節點的節點。
二叉樹是一種用於資料儲存的特殊資料結構。二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。二叉樹結合了有序陣列和連結串列的優點，搜尋速度與排序陣列一樣快，插入或刪除操作速度與連結串列一樣快。非葉子節點也稱為父節點，因為它們有超過0個子節點，但少於兩個子節點。
二叉樹的結構如下所示：
例如
輸入：
輸出：計數為2
解釋：在給定的樹中，有2個節點（即10和20）恰好有兩個子節點或完整節點，其他節點只有一個子節點或沒有子節點。
迭代法
下面程式中使用的方法如下：
建立一個包含資料部分、左指標和右指標的節點結構。
建立一個函式，用於將節點插入二叉樹。
建立一個函式來計算完整節點。
在函式內部，檢查IF !node，則返回，因為樹中沒有節點。
宣告一個臨時變數count來儲存完整節點的數量
建立一個佇列型別變數，例如qu
將節點壓入佇列中，例如qu.push(node)
迴圈，直到!qu.empty()
建立一個臨時變數，例如Node型別的temp，並將其初始化為queue.front()
使用qu.pop()彈出元素
檢查IF (!temp->left AND temp->right)，則將count加1
檢查IF (temp->left != NULL)，則執行qu.push(temp->left)
檢查IF (temp->right != NULL)，則qu.push(temp->right)
返回count
列印結果。
示例
// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
// Check if tree is empty
if (!node){
return 0;
}
queue<Node *> myqueue;
// traverse using level order traversing
int result = 0;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}輸出
如果執行上述程式碼，我們將得到以下輸出：
count is: 2
遞迴法
下面程式中使用的方法如下：
建立一個包含資料部分、左指標和右指標的節點結構。
建立一個函式，用於將節點插入二叉樹。
建立一個函式來計算完整節點。
在函式內部，檢查IF !node，則返回，因為樹中沒有節點。
宣告一個臨時變數count來儲存完整節點的數量
檢查IF (root->left AND root->right)，則將count加1
設定count = count + 遞迴呼叫此函式(root->left) + 遞迴呼叫此函式(root->right)
返回count
列印結果。
示例
// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of full Nodes
int fullcount(struct Node* root){
if (root == NULL){
return 0;
}
int result = 0;
if (root->left && root->right){
result++;
}
result += (fullcount(root->left) +
fullcount(root->right));
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}輸出
如果執行上述程式碼，我們將得到以下輸出：
count is: 2
1K+瀏覽量
