이진 트리가 주어지고 작업은 반복 및 재귀 접근 방식을 사용하여 이진 트리에서 사용 가능한 전체 노드 수를 계산하는 것입니다. 전체 노드는 자식이 모두 있고 자식이 없는 노드는 null입니다. 전체 노드에서는 정확히 두 개의 자식이 있는 노드를 고려합니다.
이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 이진 트리에는 각 노드가 최대 두 개의 자식을 가질 수 있다는 특수한 조건이 있습니다. 이진 트리는 검색이 정렬된 배열만큼 빠르고 삽입 또는 삭제 작업이 연결 목록만큼 빠르기 때문에 정렬된 배열과 연결 목록의 이점이 있습니다. 리프가 아닌 노드는 자식이 0개 이상 있고 자식이 2개 미만이므로 부모 노드라고도 합니다.
이진 트리의 구조는 다음과 같습니다. -
예
입력 -
출력 - 개수는 2입니다.
설명 - 주어진 트리에는 2개의 노드, 즉 정확히 2개의 자식이 있는 10과 20 또는 전체 노드가 있는 다른 노드가 하나 있거나 자식이 없습니다.
반복
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
데이터 부분, 왼쪽 포인터 및 오른쪽 포인터를 포함하는 노드의 구조를 만듭니다.
-
이진 트리에 노드를 삽입하는 함수를 만듭니다.
-
전체 노드를 계산하는 함수를 만듭니다.
-
함수 내에서 IF !node를 확인하고 트리에 노드가 없으므로 반환합니다.
-
전체 노드 수를 저장할 임시 변수 수 선언
-
대기열 유형 변수 생성 qu
-
대기열의 노드를 qu.push(node)
로 푸시합니다. -
!qu.empty()
동안 루프 -
임시 변수를 생성하고 Node 유형의 temp라고 하고 queue.front()로 초기화합니다.
-
qu.pop()을 사용하여 요소 팝
-
IF(!temp-> left AND temp-> right)를 확인한 다음 카운트를 1씩 증가시킵니다.
-
IF(temp->left !=NULL)를 확인한 다음 qu.push(temp->left)
를 수행합니다. -
IF(temp->right !=NULL)를 확인한 다음 qu.push(temp->right)
-
개수 반환
-
결과를 인쇄하십시오.
예
// 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를 확인하고 트리에 노드가 없으므로 반환합니다.
-
절반 노드의 개수를 저장할 임시 변수 개수 선언
-
IF (루트 -> 왼쪽 AND 루트 -> 오른쪽)를 확인한 다음 카운트를 1 증가
-
세트 카운트 =count + recursive_call_to_this_function(root->left) +recursive_call_to_this_function(root->right)
-
개수 반환
-
결과를 인쇄하십시오.
예
// 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