이진 트리가 주어지고 반복 및 재귀 접근 방식을 사용하여 이진 트리에서 사용 가능한 절반 노드 수를 계산하는 작업이 주어집니다. 하프 노드는 자식이 하나만 있고 다른 자식이 null인 노드입니다. 하프 노드에서는 리프 노드를 고려하지 않습니다.
이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 이진 트리에는 각 노드가 최대 두 개의 자식을 가질 수 있다는 특수한 조건이 있습니다. 이진 트리는 검색이 정렬된 배열만큼 빠르고 삽입 또는 삭제 작업이 연결 목록만큼 빠르기 때문에 정렬된 배열과 연결 목록의 이점이 있습니다. 리프가 아닌 노드는 자식이 0개 이상 있고 자식이 2개 미만이므로 부모 노드라고도 합니다.
이진 트리의 구조는 다음과 같습니다. -
예
입력 -
출력 - 개수는 2입니다.
설명 - 주어진 트리에는 2개의 노드가 있습니다. 즉, 정확히 하나의 자식이 있는 40과 50 또는 절반의 노드가 있는 다른 노드에는 두 개의 자식이 있거나 자식이 없을 수 있습니다.
반복
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
데이터 부분, 왼쪽 포인터 및 오른쪽 포인터를 포함하는 노드의 구조를 만듭니다.
-
이진 트리에 노드를 삽입하는 함수를 만듭니다.
-
절반 노드를 계산하는 함수를 만듭니다.
-
함수 내에서 IF !node를 확인하고 트리에 노드가 없으므로 반환합니다.
-
절반 노드의 개수를 저장할 임시 변수 개수 선언
-
대기열 유형 변수 생성 qu
-
대기열의 노드를 qu.push(node)
로 푸시합니다. -
!qu.empty()
동안 루프 -
임시 변수를 생성하고 Node 유형의 temp라고 하고 queue.front()로 초기화합니다.
-
qu.pop()을 사용하여 요소 팝
-
IF (!temp-> leftAND temp-> right) OR (temp->left AND !temp->right)를 확인한 다음 카운트를 1씩 증가시킵니다.
-
IF(temp->left !=NULL)를 확인한 다음 qu.push(temp->left)
를 수행합니다. -
개수 반환
-
결과를 인쇄하십시오.
예시
// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
// If tree is empty
if (!node)
return 0;
int result = 0; // Initialize count of half nodes
// Do level order traversal starting from root
queue<Node *> myqueue;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if ((!temp->left && temp->right) || (temp->left && !temp->right)){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
count is: 2
재귀
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
데이터 부분, 왼쪽 포인터 및 오른쪽 포인터를 포함하는 노드의 구조를 만듭니다.
-
이진 트리에 노드를 삽입하는 함수를 만듭니다.
-
절반 노드를 계산하는 함수를 만듭니다.
-
함수 내에서 IF !node를 확인하고 트리에 노드가 없으므로 반환합니다.
-
절반 노드의 개수를 저장할 임시 변수 개수 선언
-
IF(루트 -> 왼쪽 =NULL AND 루트->오른쪽 !=NULL) OR(루트 -> 왼쪽 !=NULL AND 루트->오른쪽 ==NULL)을 확인한 다음 카운트를 1씩 증가시킵니다.
-
세트 카운트 =count + recursive_call_to_this_function(root->left) +recursive_call_to_this_function(root->right)
-
개수 반환
-
결과를 인쇄하십시오.
예시
// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
struct Node{
int data;
struct Node* left, *right;
};
int halfcount(struct Node* root){
if (root == NULL)
return 0;
int result = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right ==
NULL)){
result++;
}
result += (halfcount(root->left) + halfcount(root->right));
return result;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
count is: 2