이진 트리의 경계 순회

이진 트리는 각 노드가 왼쪽 자식과 오른쪽 자식이라고 하는 최대 두 개의 자식을 갖는 트리 데이터 구조입니다.

경계 순회 이진 트리는 일반적인 프로그래밍 문제입니다. 이진 트리가 주어지고 이진 트리의 경계 노드를 루트에서 시작하여 시계 반대 방향으로 인쇄해야 합니다.

boundary traversal of binary tree은 중복 노드 없이 왼쪽 경계, 잎, 오른쪽 경계를 포함하지만 노드의 값은 중복을 포함할 수 있습니다.
경계에는 주로 왼쪽 경계와 오른쪽 경계의 두 가지 유형이 있습니다. 왼쪽 경계는 루트에서 맨 왼쪽 노드까지의 경로이고 오른쪽 경계는 루트에서 맨 오른쪽 노드까지의 경로입니다. 루트 노드에 왼쪽 및 오른쪽 하위 트리가 포함되어 있지 않으면 루트 노드 자체가 왼쪽 경계 또는 오른쪽 경계로 간주됩니다.

참고: 이 정의는 하위 트리가 아닌 입력 이진 트리에만 적용됩니다.

이 이진 트리를 고려하십시오.



가장 왼쪽 노드는 왼쪽 하위 트리가 있는 경우 먼저 왼쪽 하위 트리로 이동하여 도달할 수 있는 리프 노드입니다. 그렇지 않은 경우 오른쪽 하위 트리로 이동합니다. 리프 노드에 도달할 때까지 계속 내려갑니다. 주어진 이진 트리에서 빨간색 노드를 사용하여 왼쪽 경계가 표시됩니다.



가장 오른쪽 노드는 오른쪽 하위 트리가 있는 경우 먼저 오른쪽 하위 트리로 이동하여 도달할 수 있는 리프 노드입니다. 그렇지 않은 경우 왼쪽 하위 트리로 이동합니다. 리프 노드에 도달할 때까지 계속 내려갑니다. Right Boundary는 아래 주어진 이진 트리에서 빨간색 노드로 표시됩니다.



위 이진 트리의 리프는 빨간색을 사용하여 표시됩니다.



따라서 위의 이진 트리의 경계 순회는

1 -> 2 -> 3 -> 4 -> 5 ->7 -> 10 -> 11 -> 12 -> 8 -> 6



연산
아이디어는 이 문제를 네 부분으로 나누는 것입니다.

먼저 루트 노드를 인쇄합니다.

위에서 아래로 왼쪽 경계를 인쇄합니다.

inorder traverse와 동일한 순서로 리프 노드를 인쇄합니다.

오른쪽 경계를 아래에서 위로 인쇄합니다.

이 접근 방식은 간단해 보이지만 중복을 방지하기 위해 처리해야 하는 몇 가지 극단적인 경우가 있습니다.

루트 노드는 왼쪽 및 오른쪽 경계 순회 모두에 의해 인쇄됩니다. 먼저 루트 노드를 인쇄한 다음 루트의 왼쪽 자식에서 왼쪽 경계를 통과하고 루트의 오른쪽 자식에서 오른쪽 경계를 순회하여 이 반복을 피할 수 있습니다.

리프 노드는 이진 트리의 가장 왼쪽 및 가장 오른쪽 노드입니다. 리프 노드를 인쇄할 때 왼쪽 및 오른쪽 경계를 통과하는 동안 인쇄됩니다. 이를 방지하려면 왼쪽 및 오른쪽 경계를 통과할 때 리프 노드를 생략하십시오.

다음은 위의 논리를 그림으로 나타낸 것입니다.



C++

#include <iostream>
using namespace std;

// A binary tree structure. 
struct Node {
    int data;
    struct Node *left, *right;
};

// Utility function to create a new node in the Binary Tree.
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = nullptr;
    temp->right = nullptr;
    return temp;
}

// A Utility function to print leaf nodes of a given binary tree.
void printLeaves(Node* root)
{
    if (!root)
        return;

    printLeaves(root->left);

    // Print if it is a leaf node.
    if (!(root->left) && !(root->right))
        cout << root->data << " ";

    printLeaves(root->right);
}

// A Utility function to print all the left boundary nodes, except the leaf node. 
// Printng the nodes in Top=down manner.
void printBoundaryLeft(Node* root)
{
    if (!root)
        return;

    if (root->left) {

        // print the node before calling itself for left subtree ensuring top down manner
        cout << root->data << " ";
        printBoundaryLeft(root->left);
    }
    else if (root->right) {
        cout << root->data << " ";
        printBoundaryLeft(root->right);
    }
    // leave leaf node to remove duplicates.
}

// A utility function to print all the right boundary nodes, except the leaf node
// Printing the nodes in BOTTOM UP manner.
void printBoundaryRight(Node* root)
{
    if (!root)
        return;

    if (root->right) {
        // first call for right subtree, after then print this node ensuirng bottom up manner.
        printBoundaryRight(root->right);
        cout << root->data << " ";
    }
    else if (root->left) {
        printBoundaryRight(root->left);
        cout << root->data << " ";
    }
    // leave leaf node to remove duplicates.
}

// Main function to perform boundary traversal of a given binary tree
void printBoundary(Node* root)
{
    if (!root)
        return;

    // Step 1: PRint root node.
    cout << root->data << " ";

    // Step 2: Print the left boundary of the Binary Tree in top-down manner.
    printBoundaryLeft(root->left);

    // Step 3: Print all the leaf nodes
    printLeaves(root->left);
    printLeaves(root->right);

    // Step 4: Print the right boundary of the Binary Tree in bottom-up manner.
    printBoundaryRight(root->right);
}

int main()
{

    Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(3);
    root->left->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right = newNode(6);
    root->right->left = newNode(7);
    root->right->right = newNode(8);
           root->right->right->left = newNode(9);
           root->right->right->right = newNode(12);
           root->right->right->left->left = newNode(10);
           root->right->right->left->right = newNode(11);
    printBoundary(root);

    return 0;
}

산출



시간 복잡도

알고리즘의 시간 복잡도는 O(n)이며 여기서 n은 이진 트리의 노드 수입니다.

총 시간은 위의 네 단계를 수행하는 데 걸린 시간을 제출하는 것입니다.

루트 노드를 인쇄하는 데 걸리는 시간은 - O(1)

위에서 아래로 왼쪽 경계를 인쇄하는 데 걸리는 시간은 O(n)입니다.

리프 노드를 인쇄하는 데 걸리는 시간은 inorder traversal과 동일한 순서로 O(n)입니다.

아래에서 위로 오른쪽 경계를 인쇄하는 데 걸리는 시간은 O(n)입니다

.

여기서 n은 이진 트리의 노드 수로 정의됩니다.
공간 복잡성
알고리즘의 공간 복잡도는 O(n)이며 여기서 n은 이진 트리의 노드 수입니다.