C++의 이진 트리에서 잎이 아닌 노드 계산

이진 트리가 주어지고 작업은 이진 트리에서 사용할 수 있는 잎이 아닌 노드의 수를 계산하는 것입니다.

이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 이진 트리에는 각 노드가 최대 두 개의 자식을 가질 수 있다는 특수한 조건이 있습니다. 이진 트리는 검색이 정렬된 배열만큼 빠르고 삽입 또는 삭제 작업이 연결 목록만큼 빠르기 때문에 정렬된 배열과 연결 목록의 이점이 있습니다. 리프가 아닌 노드는 자식이 0개 이상 있고 자식이 2개 미만이므로 부모 노드라고도 합니다.

이진 트리의 구조는 다음과 같습니다. -

예를 들어

입력 -

출력 - 잎이 아닌 노드의 수는 다음과 같습니다. 3

설명 − 주어진 트리에서 27, 14, 35는 0개 이상의 자식과 2개 미만의 자식을 가지므로 잎이 아닌 노드로 사용됩니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 왼쪽 노드에 대한 포인터, 오른쪽 노드에 대한 포인터 및 노드에 저장된 데이터 부분을 포함하는 이진 트리의 구조를 만듭니다.

• 이 함수가 호출될 때마다 노드를 삽입할 함수를 만듭니다. 이를 위해 새 노드에 데이터를 삽입하고 새 노드의 오른쪽 및 왼쪽 포인터도 NULL로 설정하고 노드를 반환합니다.

• 이진 트리에서 잎이 아닌 노드의 수를 계산하는 재귀 함수를 만듭니다.

  • 루트가 NULL이거나 루트의 왼쪽이 NULL이고 루트의 오른쪽이 NULL인지 확인하면 0을 반환합니다.
  • Return 1 + 왼쪽 포인터로 이 함수에 대한 재귀 호출 + 오른쪽 포인터로 이 함수에 대한 재귀 호출

• 카운트 인쇄

예시

#include <iostream>
using namespace std;
// Node's structure
struct Node {
   int data;
   struct Node* left;
   struct Node* right;
};
// To define the new node
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
// Count the non leaf nodes.
int nonleaf(struct Node* root){
   if (root == NULL || (root->left == NULL && root->right == NULL)){
      return 0;
   }
   return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// Main function
int main(){
   struct Node* root = newNode(10);
   root->left = newNode(21);
   root->right = newNode(33);
   root->left->left = newNode(48);
   root->left->right = newNode(51);
   cout << nonleaf(root);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

count of non-leaf nodes is: 2