Создание двоичного дерева из строки в скобках

Question

Как мне использовать строку в скобках для создания двоичного дерева? Будет ли возможное решение также использовать стек каким-то образом?

Пример: строка: "(A(B)(C))" должна создать дерево, которое выглядит следующим образом:

  A
 / \
B   C

Что еще нужно отметить, это то, что () будет использоваться для обозначения того, что у узла не будет дочернего элемента в этой позиции. Для дальнейшей иллюстрации "(A()(B))", обозначает, что у узла «A» не будет левого дочернего элемента, но будет правый дочерний элемент с именем «B».

Answer 1

Один из способов сделать это - создать статический метод Parse для класса Node, который возвращает Node на основе входной строки. Логика будет что-то вроде:

1. Удалить внешнюю скобку
2. Удалите и присвойте Имя новому узлу
3. Определите строку, которая представляет левый узел (это можно сделать, посчитав открывающую и закрывающую скобки до тех пор, пока число не станет равным).
4. Назначить левый узел результату Node.Parse, используя строку "Left"
5. Назначить правый узел результату Node.Parse, используя строку "Right"

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

Например, класс Node ниже реализует метод Parse, который будет создавать узлы на основе вашего строкового ввода:

public class Node
{
    public string Name { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    /// <summary>
    /// Creates a Node based on a valid input string: "(Name(Left)(Right))", 
    /// where 'Left' and 'Right' are empty or valid strings like above.
    /// </summary>
    /// <param name="input">Input string to parse</param>
    /// <returns>Root node of the tree</returns>
    public static Node Parse(string input)
    {
        input = input?.Trim();

        // Some light validation
        if (string.IsNullOrEmpty(input) || input == "()") return null;

        if (input.Length < 7)
        {
            throw new ArgumentException(
                $"input '{input}' is not long enough to represent a valid " +
                "node. The minimum string length is 7 characters: (A()())");
        }

        if (!input.StartsWith("(") || !input.EndsWith(")"))
        {
            throw new FormatException(
                $"input '{input}' must be surrounded by parenthesis");
        }

        // Remove outer parenthesis so input is now: "Name(Left)(Right)"
        input = input.Substring(1, input.Length - 2);

        // Find the name and start of left node
        var leftNodeStart = input.IndexOf('(', 1);
        var root = new Node {Name = input.Substring(0, leftNodeStart)};

        // Remove name so input is now just: "(Left)(Right)"
        input = input.Substring(leftNodeStart);

        // Find the end of the left node by counting opening and closing parenthesis
        // When the opening count is equal to the closing count, we have our Left set
        var openParenthesisCount = 0;
        var closeParenthesisCount = 0;
        var leftNodeLength = 0;

        for (int i = 0; i < input.Length - 1; i++)
        {
            if (input[i] == '(') openParenthesisCount++;
            else if (input[i] == ')') closeParenthesisCount++;

            if (openParenthesisCount == closeParenthesisCount)
            {
                leftNodeLength = i + 1;
                break;
            }
        }

        // Recursive calls to create Left and Right children
        root.Left = Node.Parse(input.Substring(0, leftNodeLength));
        root.Right = Node.Parse(input.Substring(leftNodeLength));

        return root;
    }

    public void Print()
    {
        PrintTree();
    }        

    private static class Connector
    {
        public const string Empty = "  ";
        public const string Single = "╚═";
        public const string Double = "╠═";
        public const string Extension = "║";
    }

    private static class Position
    {
        public const string Empty = "";
        public const string Left = "Left : ";
        public const string Right = "Right: ";
    }

    private void PrintTree(string indent = "", string position = Position.Empty,
        bool extendParentConnector = false, string connector = Connector.Empty)
    {
        // Extend the parent's connector if necessary by
        // adding a "║" under the parent node's connector
        if (extendParentConnector && indent.Length > position.Length + 2)
        {
            var replaceIndex = indent.Length - position.Length - 2;
            indent = indent.Remove(replaceIndex, 1)
                .Insert(replaceIndex, Connector.Extension);
        }
        Console.ForegroundColor = ConsoleColor.DarkMagenta;
        Console.Write(indent + connector);

        Console.ForegroundColor = position == Position.Left
            ? ConsoleColor.DarkCyan
            : ConsoleColor.DarkYellow;

        Console.Write(position);
        Console.BackgroundColor = ConsoleColor.DarkGray;
        Console.ForegroundColor = ConsoleColor.DarkBlue;
        Console.WriteLine($" {Name} ");
        Console.ResetColor();

        var nextIndent = indent + new string(' ', position.Length + 2);
        var extendParent = connector == Connector.Double;

        Left?.PrintTree(nextIndent, Position.Left, extendParent,
            Right == null ? Connector.Single : Connector.Double);

        Right?.PrintTree(nextIndent, Position.Right, extendParent, Connector.Single);
    }
}   

При использовании это будет выглядеть так:

static void Main(string[] args)
{
    var nodeString = "(A(B(C(L()())(M()()))(D()()))(E(F(G(H()())())(I()(J()())))(K()())))";

    var rootNode = Node.Parse(nodeString);

    rootNode.Print();

    Console.Write("\nDone! Press any key to exit...");
    Console.ReadKey();
}

И вывод выглядит так:

Answer 2

Предполагая, что ваша входная строка правильно сформирована, вы действительно можете использовать стеки для построения древовидной структуры. Я использовал стек флагов, который работает вместе со стеком родительских узлов, чтобы отслеживать, был ли обработан левый дочерний элемент для каждого родительского элемента (либо оставлен пустым, либо назначен дочерний элемент). Этот стек флагов также изменяется для пустых скобок, обозначающих пустой дочерний элемент.

using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        PrintTree(ParseTree("(A(B(E)(F))(C(G)(H)))"), 0);
    }

    static Node ParseTree(string str) {
        var parent = new Stack<Node>();
        var hasLeft = new Stack<bool>();
        Node root = null;

        for (int i = 0; i < str.Length; i++) {
            if (str[i] == '(') {
                if (str[++i] == ')') {
                    hasLeft.Pop();
                    hasLeft.Push(true);
                }
                else {
                    var node = new Node(str[i]);

                    if (parent.Count > 0) {
                        if (hasLeft.Peek()) {
                            parent.Peek().right = node;
                        }
                        else {
                            parent.Peek().left = node;
                            hasLeft.Pop();
                            hasLeft.Push(true);
                        }
                    }
                    else {
                        root = node;
                    }

                    parent.Push(node);
                    hasLeft.Push(false);
                }
            }
            else if (str[i] == ')') {
                parent.Pop();
                hasLeft.Pop();
            }
        }

        return root;
    }

    static void PrintTree(Node root, int depth) {
        if (root != null) {
            Console.WriteLine(new String(' ', depth) + root.val);

            if (root.left != null || root.right != null) {
                Console.WriteLine(new String(' ', depth) +  "────┐");
            }

            PrintTree(root.left, depth + 4);
            PrintTree(root.right, depth + 4);
        }
    }
}

class Node {
    public Node left;
    public Node right;
    public char val;

    public Node(char val) {
        this.val = val;
    }
}

Выход:

A
────┐
    B
    ────┐
        E
        F
    C
    ────┐
        G
        H

Попробуйте!