정수 값과 변수 x가 주어지고 작업은 이진 트리를 구성하고 주어진 값 x와 동일한 합계를 갖는 쌍을 찾는 것입니다.
예를 들어
입력
int x =5, 값을 입력한 후 생성될 트리는 다음과 같습니다. -
출력
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
설명
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).
입력
int x =8, 값을 입력한 후 생성될 트리는 다음과 같습니다. -
출력
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
설명
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
-
데이터 부분과 왼쪽 및 오른쪽 하위 트리를 가리키는 왼쪽 및 오른쪽 포인터를 포함하는 노드의 구조를 만듭니다.
-
정수 값을 입력하고 이를 이용하여 좌, 우 포인터를 통해 노드에 데이터를 입력하여 바이너리 트리를 생성합니다.
-
x의 합계 값을 갖는 쌍을 계산하는 데 사용할 x 값을 입력합니다.
-
쌍의 합이 x인지 여부를 확인하는 부울 함수를 만듭니다.
-
함수 내에서 루트가 NULL인지 확인한 다음 False를 반환합니다.
-
root가 ptr과 같지 않고 root의 데이터 + ptr의 데이터가 x와 같은지 확인하고 True를 반환합니다.
-
루트, ptr 및 값 x의 왼쪽 포인터와 x, ptr 및 x의 오른쪽 포인터를 전달하여 검사 함수를 재귀적으로 호출합니다. 이제 조건이 true를 반환하는지 확인한 다음 true를 반환합니다.
-
그렇지 않으면 false를 반환합니다.
-
합계가 x인 쌍의 개수를 계산하는 total_pairs 함수를 만듭니다.
-
함수 내에서 ptr이 NULL인지 확인한 다음 0을 반환합니다.
-
root, ptr 및 x를 인수로 전달하여 함수 검사를 호출합니다. 함수가 true를 반환하면 총 쌍의 값을 1씩 증가시킵니다.
-
루트, ptr의 왼쪽 포인터, x 및 total을 전달하여 함수 total_pairs를 재귀적으로 호출하고 루트, ptr, x 및 total의 오른쪽 포인터도 전달합니다.
-
변수 total에 저장된 정수 값으로 결과를 출력합니다.
예시
#include <bits/stdc++.h>
using namespace std;
struct tree_node {
int data;
tree_node *left, *right;
};
tree_node* create_node(int data){
tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
newNode−>data = data;
newNode−>left = newNode−>right = NULL;
}
bool check(tree_node* root, tree_node* ptr, int x){
if(root==NULL){
return false;
}
if (root != ptr && ((root−>data + ptr−>data) == x)){
return true;
}
if (check(root−>left, ptr, x) || check(root−>right, ptr, x)){
return true;
}
return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
if(ptr == NULL){
return;
}
if(check(root, ptr, x) == true){
total++;
}
total_pairs(root, ptr−>left, x, total);
total_pairs(root, ptr−>right, x, total);
}
int main(){
int x = 5;
int total = 0;
tree_node* root = create_node(5);
root−>left = create_node(2);
root−>right = create_node(3);
root−>left−>left = create_node(1);
root−>left−>right = create_node(4);
root−>right−>left = create_node(6);
total_pairs(root, root, x, total);
total = total / 2;
cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs in a binary tree whose sum is equal to a given value x are: 2