Рубрики

Обход границы двоичного дерева

Для заданного двоичного дерева выведите граничные узлы двоичного дерева против часовой стрелки, начиная с корня. Например, обход границы следующего дерева: «20 8 4 10 14 25 22»

Мы разбиваем проблему на 3 части:
1. Напечатайте левую границу сверху вниз.
2. Напечатайте все листовые узлы слева направо, которые снова можно разделить на две части:
… .. 2.1 Распечатать все листовые узлы левого поддерева слева направо.
… .. 2.2 Вывести все листовые узлы правого поддерева слева направо.
3. Напечатайте правую границу снизу вверх.

Нам нужно позаботиться о том, чтобы узлы не печатались снова. Например, самый левый узел также является листовым узлом дерева.

Исходя из вышеизложенного, ниже приведена реализация:

C ++

/ * C программа для обхода границы
двоичного дерева * /

  
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка
и указатель на правого ребенка * /

struct node {

    int data;

    struct node *left, *right;

};

  
// Простая функция для печати листовых узлов двоичного дерева

void printLeaves(struct node* root)

{

    if (root == NULL)

        return;

  

    printLeaves(root->left);

  

    // Распечатать его, если это листовой узел

    if (!(root->left) && !(root->right))

        printf("%d ", root->data);

  

    printLeaves(root->right);

}

  
// Функция для печати всех левых граничных узлов, кроме листового узла.
// Печать узлов в порядке сверху вниз

void printBoundaryLeft(struct node* root)

{

    if (root == NULL)

        return;

  

    if (root->left) {

  

        // для обеспечения порядка сверху вниз печатаем узел

        // перед вызовом себя для левого поддерева

        printf("%d ", root->data);

        printBoundaryLeft(root->left);

    }

    else if (root->right) {

        printf("%d ", root->data);

        printBoundaryLeft(root->right);

    }

    // ничего не делаем, если это листовой узел, таким образом мы избегаем

    // дублирует в выводе

}

  
// Функция для печати всех правых граничных узлов, кроме листового узла
// Печать узлов в нижнем направлении

void printBoundaryRight(struct node* root)

{

    if (root == NULL)

        return;

  

    if (root->right) {

        // чтобы обеспечить порядок снизу вверх, сначала вызовите право

        // поддерево, затем распечатать этот узел

        printBoundaryRight(root->right);

        printf("%d ", root->data);

    }

    else if (root->left) {

        printBoundaryRight(root->left);

        printf("%d ", root->data);

    }

    // ничего не делаем, если это листовой узел, таким образом мы избегаем

    // дублирует в выводе

}

  
// Функция для обхода границы заданного двоичного дерева

void printBoundary(struct node* root)

{

    if (root == NULL)

        return;

  

    printf("%d ", root->data);

  

    // Распечатать левую границу сверху вниз.

    printBoundaryLeft(root->left);

  

    // Распечатать все листовые узлы

    printLeaves(root->left);

    printLeaves(root->right);

  

    // Распечатать правую границу снизу вверх

    printBoundaryRight(root->right);

}

  
// Вспомогательная функция для создания узла

struct node* newNode(int data)

{

    struct node* temp = (struct node*)malloc(sizeof(struct node));

  

    temp->data = data;

    temp->left = temp->right = NULL;

  

    return temp;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Построим дерево, указанное на диаграмме выше

    struct node* root = newNode(20);

    root->left = newNode(8);

    root->left->left = newNode(4);

    root->left->right = newNode(12);

    root->left->right->left = newNode(10);

    root->left->right->right = newNode(14);

    root->right = newNode(22);

    root->right->right = newNode(25);

  

    printBoundary(root);

  

    return 0;

}

Джава

// Java-программа для печати обхода границы двоичного дерева

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка
и указатель на правого ребенка * /

class Node {

    int data;

    Node left, right;

  

    Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

    Node root;

  

    // Простая функция для печати листовых узлов двоичного дерева

    void printLeaves(Node node)

    {

        if (node == null)

            return;

  

        printLeaves(node.left);

        // Распечатать его, если это листовой узел

        if (node.left == null && node.right == null)

            System.out.print(node.data + " ");

        printLeaves(node.right);

    }

  

    // Функция для печати всех левых граничных узлов, кроме листового узла.

    // Печать узлов в порядке сверху вниз

    void printBoundaryLeft(Node node)

    {

        if (node == null)

            return;

  

        if (node.left != null) {

            // для обеспечения порядка сверху вниз печатаем узел

            // перед вызовом себя для левого поддерева

            System.out.print(node.data + " ");

            printBoundaryLeft(node.left);

        }

        else if (node.right != null) {

            System.out.print(node.data + " ");

            printBoundaryLeft(node.right);

        }

  

        // ничего не делаем, если это листовой узел, таким образом мы избегаем

        // дублирует в выводе

    }

  

    // Функция для печати всех правых граничных узлов, кроме листового узла

    // Печать узлов в нижнем направлении

    void printBoundaryRight(Node node)

    {

        if (node == null)

            return;

  

        if (node.right != null) {

            // чтобы обеспечить порядок снизу вверх, сначала вызовите право

            // поддерево, затем распечатать этот узел

            printBoundaryRight(node.right);

            System.out.print(node.data + " ");

        }

        else if (node.left != null) {

            printBoundaryRight(node.left);

            System.out.print(node.data + " ");

        }

        // ничего не делаем, если это листовой узел, таким образом мы избегаем

        // дублирует в выводе

    }

  

    // Функция для обхода границы заданного двоичного дерева

    void printBoundary(Node node)

    {

        if (node == null)

            return;

  

        System.out.print(node.data + " ");

  

        // Распечатать левую границу сверху вниз.

        printBoundaryLeft(node.left);

  

        // Распечатать все листовые узлы

        printLeaves(node.left);

        printLeaves(node.right);

  

        // Распечатать правую границу снизу вверх

        printBoundaryRight(node.right);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

        tree.root.right = new Node(22);

        tree.root.right.right = new Node(25);

        tree.printBoundary(tree.root);

    }

}

python3

# Python3 программа для двоичного обхода двоичного дерева

  
# Узел двоичного дерева

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Простая функция для печати листовых узлов двоичного дерева

def printLeaves(root):

    if(root):

        printLeaves(root.left)

          

        # Распечатать его, если это листовой узел

        if root.left is None and root.right is None:

            print(root.data),

  

        printLeaves(root.right)

  
# Функция для печати всех левых граничных узлов, кроме
# листовой узел. Распечатать узлы в порядке сверху вниз

def printBoundaryLeft(root):

      

    if(root):

        if (root.left):

              

            # чтобы обеспечить порядок сверху вниз, выведите узел

            # перед вызовом себя для левого поддерева

            print(root.data)

            printBoundaryLeft(root.left)

          

        elif(root.right):

            print (root.data)

            printBoundaryLeft(root.right)

          

        # ничего не делать, если это листовой узел, таким образом мы

        # избегать дубликатов в выводе

  

  
# Функция для печати всех правых граничных узлов, кроме
# листовой узел. Распечатать узлы в нижнем направлении

def printBoundaryRight(root):

      

    if(root):

        if (root.right):

            # чтобы обеспечить порядок снизу вверх, сначала позвоните

            # правильное поддерево, затем распечатать этот узел

            printBoundaryRight(root.right)

            print(root.data)

          

        elif(root.left):

            printBoundaryRight(root.left)

            print(root.data)

  

        # ничего не делать, если это листовой узел, таким образом мы

        # избегать дубликатов в выводе

  

  
# Функция для обхода границы данного двоичного дерева

def printBoundary(root):

    if (root):

        print(root.data)

          

        # Распечатать левую границу сверху вниз

        printBoundaryLeft(root.left)

  

        # Распечатать все листовые узлы

        printLeaves(root.left)

        printLeaves(root.right)

  

        # Распечатать правую границу снизу вверх

        printBoundaryRight(root.right)

  

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(20)

root.left = Node(8)

root.left.left = Node(4)

root.left.right = Node(12)

root.left.right.left = Node(10)

root.left.right.right = Node(14)

root.right = Node(22)

root.right.right = Node(25)

printBoundary(root)

  
# Этот код предоставлен
# Никхил Кумар Сингх (nickzuck_007)

C #

// C # программа для печати обхода границы
// двоичного дерева

using System;

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и указатель
правый ребенок * /

public class Node {

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG {

    public Node root;

  

    // Простая функция для печати листа

    // узлы двоичного дерева

    public virtual void printLeaves(Node node)

    {

        if (node == null)

            return;

  

        printLeaves(node.left);

  

        // Распечатать его, если это листовой узел

        if (node.left == null && node.right == null) {

            Console.Write(node.data + " ");

        }

        printLeaves(node.right);

    }

  

    // Функция для печати всей левой границы

    // узлы, кроме листового узла. Распечатать

    // узлы в порядке сверху вниз

    public virtual void printBoundaryLeft(Node node)

    {

        if (node == null)

            return;

  

        if (node.left != null) {

  

            // для обеспечения порядка сверху вниз печатаем узел

            // перед вызовом себя для левого поддерева

            Console.Write(node.data + " ");

            printBoundaryLeft(node.left);

        }

        else if (node.right != null) {

            Console.Write(node.data + " ");

            printBoundaryLeft(node.right);

        }

  

        // ничего не делать, если это листовой узел,

        // таким образом мы избегаем дубликатов в выводе

    }

  

    // Функция для печати всей правой границы

    // узлы, кроме листового узла. Распечатать

    // узлы снизу вверх

    public virtual void printBoundaryRight(Node node)

    {

        if (node == null)

            return;

  

        if (node.right != null) {

            // обеспечить порядок снизу вверх,

            // первый вызов для правого поддерева,

            // затем печатаем этот узел

            printBoundaryRight(node.right);

            Console.Write(node.data + " ");

        }

        else if (node.left != null) {

            printBoundaryRight(node.left);

            Console.Write(node.data + " ");

        }

        // ничего не делать, если это листовой узел,

        // таким образом мы избегаем дубликатов в выводе

    }

  

    // Функция для обхода границы

    // данного двоичного дерева

    public virtual void printBoundary(Node node)

    {

        if (node == null)

            return;

  

        Console.Write(node.data + " ");

  

        // Распечатать левую границу в

        // сверху вниз.

        printBoundaryLeft(node.left);

  

        // Распечатать все листовые узлы

        printLeaves(node.left);

        printLeaves(node.right);

  

        // Распечатать правую границу в

        // снизу вверх

        printBoundaryRight(node.right);

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        GFG tree = new GFG();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

        tree.root.right = new Node(22);

        tree.root.right.right = new Node(25);

        tree.printBoundary(tree.root);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

20 8 4 10 14 25 22

Сложность времени: O (n), где n — количество узлов в двоичном дереве.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Обход границы двоичного дерева

0.00 (0%) 0 votes