Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 BST에서 주어진 합계를 가진 쌍 찾기

<시간/>

이 튜토리얼에서는 이진 탐색 트리에서 주어진 숫자와 합이 같은 쌍을 찾는 프로그램을 작성할 것입니다.

우리는 쌍을 찾기 위해 두 개의 다른 목록에 나무의 값과 값을 저장할 것입니다. 문제를 해결하는 단계를 살펴보겠습니다.

  • 이진 트리에 대한 구조체 노드를 만듭니다.

  • 이진 검색 트리에 새 노드를 삽입하는 함수를 작성하십시오.

    • 이진 검색 트리에서 루트보다 작은 모든 요소는 더 작고 오른쪽이 더 큽니다.

  • 두 개의 빈 목록을 초기화하여 트리의 왼쪽 및 오른쪽 노드를 저장합니다.

  • 왼쪽 또는 오른쪽 노드가 NULL이거나 두 목록이 모두 비어 있지 않을 때까지 이진 검색 트리를 반복합니다.

    • 모든 요소를 ​​왼쪽 노드 목록에 저장하는 루프를 작성하십시오.

    • 모든 요소를 ​​올바른 노드 목록에 저장하는 루프를 작성하십시오.

    • 각 목록에서 마지막 노드를 가져옵니다.

    • 두 값을 확인하십시오.

      • 왼쪽 노드 값이 오른쪽 노드 값보다 크거나 같으면 루프를 끊습니다.

      • 두 값의 합이 주어진 숫자와 같으면 루프를 인쇄하고 끊습니다.

      • 두 값의 합이 주어진 숫자보다 작으면 왼쪽 목록에서 마지막 노드를 삭제하고 노드의 오른쪽으로 이동합니다.

      • 두 값의 합이 주어진 숫자보다 크면 오른쪽 목록에서 마지막 노드를 삭제하고 노드의 왼쪽으로 이동합니다.

예시

코드를 봅시다.

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node *left, *right, *root;
   Node(int data) {
      this->data = data;
      left = NULL;
      right = NULL;
      root = NULL;
   }
};
Node* insertNewNode(Node *root, int data){
   if (root == NULL) {
      root = new Node(data);
      return root;
   }
   if (root->data < data) {
      root->right = insertNewNode(root->right, data);
   }
   else if (root->data > data) {
      root->left = insertNewNode(root->left, data);
   }
   return root;
}
void findThePairs(Node *node, int target) {
   vector<Node*> left_side_nodes;
   vector<Node*> right_side_nodes;
   Node *current_left = node;
   Node *current_right = node;
   while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
      while (current_left != NULL) {
         left_side_nodes.push_back(current_left);
         current_left = current_left->left;
      }
      while (current_right != NULL) {
         right_side_nodes.push_back(current_right);
         current_right = current_right->right;
      }
      Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
      Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
      int left_side_value = left_side_node->data;
      int right_side_value = right_side_node->data;
      if (left_side_value >= right_side_value) {
         break;
      }
      if (left_side_value + right_side_value < target) {
         left_side_nodes.pop_back();
         current_left = left_side_node->right;
      }
      else if (left_side_value + right_side_value > target) {
         right_side_nodes.pop_back();
         current_right = right_side_node->left;
      }
      else {
         cout << left_side_node->data << " " << right_side_node->data << endl;
         break;
      }
   }
}
int main() {
   Node *root = NULL;
   root = insertNewNode(root, 25);
   root = insertNewNode(root, 20);
   root = insertNewNode(root, 30);
   root = insertNewNode(root, 15);
   root = insertNewNode(root, 21);
   root = insertNewNode(root, 19);
   root = insertNewNode(root, 31);
   findThePairs(root, 36);
}

출력

위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

15 21

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.