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

C++의 선주문 순회에서 전체 k-ary 트리를 구성합니다.

k-ary 트리의 사전 순회를 순서대로 포함하는 배열 arr[]이 제공됩니다. 목표는 그것으로부터 동일한 k-ary 트리를 구성하고 그것의 후위 순회를 인쇄하는 것입니다. 전체 k-ary 트리는 루트 노드가 0 또는 k 자식, 즉 최대 k 자식을 갖는 트리입니다.

예를 들어

입력

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2

출력

preorder traversal에서 두 개의 자식으로 구성될 전체 k-ary 트리는 다음과 같습니다. -

C++의 선주문 순회에서 전체 k-ary 트리를 구성합니다.

설명

우리는 정수 값의 배열 또는 k 자식이 2인 트리의 사전순 순회가 제공됩니다. 따라서 형성된 트리는 다음 규칙에 따라 구성된 후위 순회를 3 6 1 2 1 7 5 2로 갖게 됩니다. 모든 LEFT 하위 트리 노드를 방문한 다음 모든 RIGHT 하위 트리 노드를 방문한 다음 모든 ROOT 노드를 방문합니다.

입력

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3

출력

preorder traversal에서 세 개의 자식으로 구성될 전체 k-ary 트리는 다음과 같습니다. -

C++의 선주문 순회에서 전체 k-ary 트리를 구성합니다.

설명

우리는 정수 값의 배열 또는 3인 k 자식이 있는 트리의 사전순 순회가 제공됩니다. 따라서 형성된 트리는 다음 규칙에 따라 구성되는 3 6 1 2 1 7 5 2와 같은 후위 순회를 갖습니다. 모든 LEFT 하위 트리 노드를 방문한 다음 모든 RIGHT 하위 트리 노드를 방문한 다음 모든 ROOT 노드를 방문합니다.

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

이 접근 방식에서는 먼저 첫 번째 요소를 루트 노드로 사용하여 주어진 배열에서 k-ary 트리를 구성합니다. 왼쪽 하위 트리가 비어 있으면 오른쪽 하위 트리도 비어 있습니다. 왼쪽 및 오른쪽 하위 트리를 재귀적으로 호출하고 연결합니다. 후위 순회를 위해 왼쪽 하위 트리, 오른쪽 하위 트리를 선택한 다음 노드의 가중치를 인쇄합니다.

  • postorder(루트->왼쪽)

    호출

  • postorder 호출(root−>right)

  • 루트->데이터

    인쇄

  • 사전 주문 순회를 포함하는 입력 배열로 arr[]을 사용합니다.

  • k를 변수 자식으로 사용합니다.

  • 시작 인덱스를 count=0으로 사용합니다.

  • Tree_Node* node =create_tree(arr, size, children, count)를 사용하여 트리를 구성합니다.

  • 함수 new_Node(int data)는 트리의 새 노드를 생성합니다.

  • 함수 create_tree(int arr[], int N, int k, int height, int&count)는 배열 arr[]에서 kary 트리를 생성합니다.

  • 노드 수가 <=0이면 NULL을 반환하면 트리를 구성할 수 없습니다.

  • newNode =new_Node(arr[count]), arr[]의 첫 번째 요소를 초기화합니다.

  • (newNode ==NULL) 결과가 true이면 트리가 불가능합니다.

  • for 루프를 사용하여 i=0에서 i로 트래버스

  • (count 1)이면 다음 인덱스의 카운트를 증가시키고 newNode−>root.push_back(create_tree(arr, N, k, height − 1, count))를 사용하여 이 노드를 트리에 추가합니다.

  • 그렇지 않으면 newNode−>root.push_back(NULL);

    을 사용하여 NULL을 푸시하여 트리를 종료하십시오.

  • 끝에서 노드에 대한 포인터를 반환합니다.

  • create_tree(int* arr, int N, int k, int count) 함수는 트리의 높이를 반환합니다.

  • 계산 높이=(int)ceil(log((double)N * (k − 1) + 1) / log((double)k));

  • 위에서 계산한 height에 있는 tree에 대한 return 문에서 create_tree(arr, N, k, height, count)를 호출합니다.

  • 함수 postorder_traversal(Tree_Node* node, int k)는 노드에 뿌리를 둔 k-ary 트리의 preordertraversal을 출력합니다.

  • 노드가 NULL이면 아무 것도 반환하지 않습니다.

  • for 루프를 사용하여 i=0에서 iroot[i], k);

  • 노드->for 루프 끝에 있는 주소를 인쇄합니다.

예시

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
   int address;
   vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
   Tree_Node* newNode = new Tree_Node;
   newNode−>address = data;
   return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
   if(N <= 0){
      return NULL;
   }
   Tree_Node* newNode = new_Node(arr[count]);
   if (newNode == NULL){
      cout<<"Code Dumped";
      return NULL;
   }
   for(int i = 0; i < k; i++){
      if (count < N − 1 && height > 1){
         count++;
         newNode−>root.push_back(create_tree(arr, N, k, height − 1, count));
      }else{
         newNode−>root.push_back(NULL);
      }
   }
   return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
   int height = (int)ceil(log((double)N * (k − 1) + 1) / log((double)k));
   return create_tree(arr, N, k, height, count);
}
void preorder_traversal(Tree_Node* node, int k){
   if (node == NULL){
      return;
   }
   for(int i = 0; i < k; i++){
      preorder_traversal(node−>root[i], k);
   }
   cout<<node−>address<< " ";
}
int main(){
   int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
   int size = 8;
   int children = 2;
   int count = 0;
   Tree_Node* node = create_tree(arr, size, children, count);
   cout<<"Construct the full k−ary tree from its preorder traversal are: ";
   preorder_traversal(node, children);
   return 0;
}

출력

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

Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2