이진 트리에서 이진 검색 트리로 변환

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 구글 Microsoft VM웨어
이진 검색 트리 이진 트리 깊이 우선 검색 나무 트리 순회조회수 27

이진 트리에서 이진 검색 트리로의 변환 문제에서 우리는 이진 트리의 구조를 변경하지 않고 이진 트리를 이진 검색 트리로 변환했습니다. 나무.

입력

이진 트리에서 이진 검색 트리로 변환

산출

이진 트리에서 이진 검색 트리로 변환

선주문 : 13 8 6 47 25 51

암호알고리즘

이진 트리의 구조를 변경하고 이진 검색 트리로 변환 할 필요가 없습니다. 이진 검색 트리의 속성에 유의하십시오. 순회 이진 검색 트리는 정렬 된 데이터로 이어집니다. 이 속성을 사용하여 원하는 결과를 얻습니다.

아이디어는 Binary Tree의 inorder traversal을 정렬, 배열을 정렬 한 다음 배열과 이진 트리 (순서 형식)를 순회하고 이진 트리의 모든 노드를 배열의 해당 요소로 바꿉니다. 이진 트리를 이진 검색 트리로 변환합니다.

  1. inOrder라는 배열을 만듭니다.
  2. 주어진 이진 트리를 순서대로 순회하고 'inOrder'배열에 노드 값을 저장합니다.
  3. 배열을 정렬하십시오.
  4. 순서대로 배열과 바이너리 트리를 동시에 순회하고 바이너리 트리의 해당 노드 값을 inOrder 배열의 값으로 바꿉니다.
  5. 이진 트리는 이진 검색 트리로 변환됩니다.

시간 복잡성 = O (n log (n))
공간 복잡성 = O (n), 순서대로 순회를 저장하기 위해 배열을 사용 했으므로
여기서 n은 주어진 이진 트리의 노드 수입니다.

설명

위의 예에 표시된 이진 트리를 고려하십시오.

1 단계 및 2 단계

이진 트리의 순회 순회를 배열에 저장합니다.
inOrder [] = {47, 51, 25, 6, 13, 8}

단계 3

배열을 정렬하십시오.
순서 = {6, 8, 13, 25, 47, 51}

단계 4

배열과 이진 트리를 동시에 탐색하고 이진 트리의 요소를 정렬 된 inOrder 배열의 해당 요소로 바꿉니다.
바이너리 트리는 이제 다음과 같습니다.

이진 트리는 이진 검색 트리로 변환됩니다.

이진 트리에서 이진 검색 트리로의 변환을위한 JAVA 코드

import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // class to provide a wrapper around index
    // so that we can pass it by reference
    static class Index {
        int index;

        public Index(int index) {
            this.index = index;
        }
    }

    // function to print pre order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // function to traverse in binary tree in in-order form and store the elements
    // in a list
    private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
        if (root != null) {
            inOrderAndFormList(root.left, inorder);
            // store the current value in the list
            inorder.add(root.data);
            inOrderAndFormList(root.right, inorder);
        }
    }

    // function to traverse in binary tree in in-order form and
    // change the value of elements accordingly
    private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
        if (root != null) {
            inOrderAndChange(root.left, inOrder, index);
            // change the current element of Tree with current element of list
            root.data = inOrder.get(index.index);
            // increment index by 1
            index.index++;
            inOrderAndChange(root.right, inOrder, index);
        }
    }

    private static void convertToBST(Node root) {
        // create a list and store the inorder of the given Binary Tree
        ArrayList<Integer> inOrder = new ArrayList<>();
        inOrderAndFormList(root, inOrder);

        // Sort the list
        Collections.sort(inOrder);

        // traverse in binary tree and list simultaneously and change the required values
        inOrderAndChange(root, inOrder, new Index(0));
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(51);
        root.right = new Node(13);
        root.left.left = new Node(47);
        root.right.left = new Node(6);
        root.right.right = new Node(8);

        convertToBST(root);

        preOrder(root);
        System.out.println();
    }
}
13 8 6 47 25 51

이진 트리에서 이진 검색 트리로 변환하기위한 C ++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
    }
};

// global variable index
int index = 0;

void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
    if (root != NULL) {
        inOrderAndFormList(root->left, inOrder);
        // store the current value in the list
        inOrder.push_back(root->data);
        inOrderAndFormList(root->right, inOrder);
    }
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
    if (root != NULL) {
        inOrderAndChange(root->left, inOrder);
        
        // change the current element of Tree with current element of list
        root->data = inOrder[index];
        index++;
        
        inOrderAndChange(root->right, inOrder);
    }
}

void convertToBST(Node *root) {
    // create a list and store the inorder of the given Binary Tree
    vector<int> inOrder;
    inOrderAndFormList(root, inOrder);

    // Sort the list
    sort(inOrder.begin(), inOrder.end());

    // traverse in binary tree and list simultaneously and change the required values
    index = 0;
    inOrderAndChange(root, inOrder);
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(51);
    root->right = new Node(13);
    root->left->left = new Node(47);
    root->right->left = new Node(6);
    root->right->right = new Node(8);

    convertToBST(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
13 8 6 47 25 51

참조

Translate »