Рубрики

Проблема с пользовательским деревом

Вам предоставляется набор ссылок, например,

a ---> b
b ---> c
b ---> d
a ---> e 

Распечатайте дерево, которое будет формироваться, когда каждая пара этих ссылок, имеющих одинаковый символ с начальной и конечной точкой, соединяется вместе. Вы должны поддерживать точность относительно высоты узлов, то есть узлы на высоте n от корня должны быть напечатаны в той же строке или столбце. Для набора ссылок, приведенного выше, напечатанное дерево должно быть —

-->a
   |-->b
   |   |-->c
   |   |-->d
   |-->e

Обратите внимание, что эти ссылки не должны формировать одно дерево; они могли сформировать, гм, лес. Рассмотрим следующие ссылки

a ---> b
a ---> g
b ---> c
c ---> d
d ---> e
c ---> f
z ---> y
y ---> x
x ---> w

Выход будет следующий лес.

-->a
   |-->b
   |   |-->c
   |   |   |-->d
   |   |   |   |-->e
   |   |   |-->f
   |-->g

-->z
   |-->y
   |   |-->x
   |   |   |-->w

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

Решение: Идея состоит в том, чтобы поддерживать два массива: один массив для узлов дерева и другой для самих деревьев (мы называем этот массив массивов). Элемент массива узлов содержит объект TreeNode, соответствующий соответствующему символу. Элемент массива леса содержит объект Tree, соответствующий соответствующему корню дерева.

Должно быть очевидно, что решающей частью здесь является создание леса, после того как он будет создан, распечатать его в требуемом формате просто. Для создания леса используется следующая процедура:

Do following for each input link,
1. If start of link is not present in node array
     Create TreeNode objects for start character
     Add entries of start in both arrays. 
2. If end of link is not present in node array
     Create TreeNode objects for start character
     Add entry of end in node array.
3. If end of link is present in node array.
     If end of link is present in forest array, then remove it
     from there.
4. Add an edge (in tree) between start and end nodes of link.

Должно быть понятно, что эта процедура выполняется за линейное время как по количеству узлов, так и по ссылкам — она делает только один проход по ссылкам. Это также требует линейного пространства с точки зрения размера алфавита.

Ниже приводится реализация Java вышеупомянутого алгоритма. В следующей реализации символы предполагаются только строчными буквами от «а» до «z».

Джава

// Java-программа для создания собственного дерева из заданного набора ссылок.

    
// Основной класс, который представляет дерево и имеет метод main

public class Tree {

      

    private TreeNode root;

    

    / * Возвращает массив деревьев из ввода ссылок. Предполагается, что ссылки

       be Строки вида "<s> <e>", где начинаются <s> и <e>

       и конечные точки для ссылки. Возвращаемый массив имеет размер 26

       и имеет ненулевые значения в индексах, соответствующих корням деревьев

       на выходе * /

    public Tree[] buildFromLinks(String [] links) {

            

        // Создаем два массива для узлов и леса

        TreeNode[] nodes = new TreeNode[26];  

        Tree[] forest = new Tree[26];          

    

        // Обрабатываем каждую ссылку

        for (String link : links) {

                

            // Находим два конца текущей ссылки

            String[] ends = link.split(" ");

            int start = (int) (ends[0].charAt(0) - 'a'); // Начать узел

            int end   = (int) (ends[1].charAt(0) - 'a'); // Конечный узел

                          

            // Если начало ссылки ранее не было видно, добавьте два массива

            if (nodes[start] == null

            {                

                nodes[start] = new TreeNode((char) (start + 'a'));   

                  

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

                // последний символ ссылки. Например, давайте сначала посмотрим

                // a ---> b, затем c ---> a. Сначала мы добавим «а» в массив деревьев

                // и когда мы видим ссылку c ---> a, мы удаляем ее из массива деревьев.

                forest[start] = new Tree(nodes[start]);                                            

            

               

            // Если конец ссылки не виден ранее, добавьте его в массив узлов

            if (nodes[end] == null)                             

                nodes[end] = new TreeNode((char) (end + 'a'));                                 

              

            // Если конец ссылки виден раньше, удалить его из леса, если

            // он существует там.

            else forest[end] = null

   

            // Установить отношения между родителями и детьми между началом и концом

            nodes[start].addChild(nodes[end], end);

        }        

        return forest;

    }

    

    // Конструктор

    public Tree(TreeNode root) { this.root = root;  }  

     

    public static void printForest(String[] links)

    {

        Tree t = new Tree(new TreeNode('\0'));

        for (Tree t1 : t.buildFromLinks(links)) {

           if (t1 != null)  

           {  

              t1.root.printTreeIdented("");

              System.out.println("");

           }  

        }

    }        

    

    // Метод драйвера для тестирования

    public static void main(String[] args) {

        String [] links1 = {"a b", "b c", "b d", "a e"};

        System.out.println("------------ Forest 1 ----------------");

        printForest(links1);       

          

        String [] links2 = {"a b", "a g", "b c", "c d", "d e", "c f",

                            "z y", "y x", "x w"};

        System.out.println("------------ Forest 2 ----------------");

        printForest(links2);      

    }

}

  
// Класс для представления узла дерева

class TreeNode {    

    TreeNode []children;

    char c;

      

    // Добавляет дочерний элемент 'n' к этому узлу

    public void addChild(TreeNode n, int index) { this.children[index] = n;}  

      

    // Конструктор

    public TreeNode(char c) { this.c = c;  this.children = new TreeNode[26];}

      

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

    public void printTreeIdented(String indent) {        

            System.out.println(indent + "-->" + c);

            for (TreeNode child : children) {

              if (child != null)  

                child.printTreeIdented(indent + "   |");

            }        

    }    

}

C #

// C # программа для создания собственного дерева
// из заданного набора ссылок.

using System;

  
// Основной класс, представляющий дерево
// и имеет основной метод

class Tree

{

    public TreeNode root;

      

    / * Возвращает массив деревьев из ввода ссылок.

    Предполагается, что ссылки являются строками вида

    «<s> <e>», где начинаются <s> и <e> и

    конечные точки для ссылки. Возвращенный массив

    размером 26 и имеет ненулевые значения в индексах

    соответствует корням деревьев в выводе * /

    public Tree[] buildFromLinks(String [] links) 

    {

              

        // Создаем два массива для узлов и леса

        TreeNode[] nodes = new TreeNode[26]; 

        Tree[] forest = new Tree[26];         

      

        // Обрабатываем каждую ссылку

        foreach (String link in links) 

        {

            char []sep = {' ',' '};

              

            // Находим два конца текущей ссылки

            String[] ends = link.Split(sep);

            int start = (int) (ends[0][0] - 'a'); // Начать узел

            int end = (int) (ends[1][0] - 'a'); // Конечный узел

                          

            // Если начало ссылки не было видно раньше,

            // добавляем два обоих массива

            if (nodes[start] == null

            {             

                nodes[start] = new TreeNode((char) (start + 'a')); 

                  

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

                // этот символ является последним символом ссылки.

                // Например, давайте сначала увидим a ---> b,

                // тогда c ---> a. Сначала мы добавляем «а» в массив

                // деревьев и когда мы видим ссылку c ---> a,

                // мы удаляем его из массива деревьев.

                forest[start] = new Tree(nodes[start]);                                         

            

              

            // Если конец ссылки не виден раньше,

            // добавляем его в массив узлов

            if (nodes[end] == null)                             

                nodes[end] = new TreeNode((char) (end + 'a'));                                 

              

            // Если конец ссылки виден раньше,

            // удалить его из леса, если он там существует.

            else forest[end] = null

  

            // Установить отношения между родителями и детьми

            // между началом и концом

            nodes[start].addChild(nodes[end], end);

        }     

        return forest;

    }

      

    // Конструктор

    public Tree(TreeNode root) { this.root = root; } 

      

    public static void printForest(String[] links)

    {

        Tree t = new Tree(new TreeNode('\0'));

        foreach (Tree t1 in t.buildFromLinks(links)) 

        {

            if (t1 != null

            

                t1.root.printTreeIdented("");

                Console.WriteLine("");

            

        }

    }     

      

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

    public static void Main(String[] args) {

        String [] links1 = {"a b", "b c", "b d", "a e"};

        Console.WriteLine("------------ Forest 1 ----------------");

        printForest(links1);     

          

        String [] links2 = {"a b", "a g", "b c", "c d", "d e",

                            "c f", "z y", "y x", "x w"};

        Console.WriteLine("------------ Forest 2 ----------------");

        printForest(links2);     

    }

}

  
// Класс для представления узла дерева

public class TreeNode 

    TreeNode []children;

    char c;

      

    // Добавляет дочерний элемент 'n' к этому узлу

    public void addChild(TreeNode n, int index) 

    

        this.children[index] = n;

    

      

    // Конструктор

    public TreeNode(char c)

    

        this.c = c; this.children = new TreeNode[26];

    }

      

    // Рекурсивный метод для печати дерева с отступами

    // корнем с этим узлом.

    public void printTreeIdented(String indent) 

    {     

        Console.WriteLine(indent + "-->" + c);

        foreach (TreeNode child in children)

        {

            if (child != null

                child.printTreeIdented(indent + " |");

        }     

    

}

  
// Этот код предоставлен Rajput-Ji


Выход:

------------ Forest 1 ----------------
-->a
   |-->b
   |   |-->c
   |   |-->d
   |-->e

------------ Forest 2 ----------------
-->a
   |-->b
   |   |-->c
   |   |   |-->d
   |   |   |   |-->e
   |   |   |-->f
   |-->g

-->z
   |-->y
   |   |-->x
   |   |   |-->w

Упражнение:
В приведенной выше реализации предполагается, что конечные точки входных ссылок состоят из набора только из 26 символов. Расширить реализацию, где конечные точки являются строками любой длины.

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

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

Проблема с пользовательским деревом

0.00 (0%) 0 votes