Как представить строку в виде двоичного дерева в Java?

Question

Привет, я новичок в программировании, и мне нужно проверить, сбалансировано ли данное двоичное дерево или нет в Java. чтобы сделать это, я хотел попытаться достичь самого глубокого узла с обеих сторон и проверить разницу в высоте, но дело в том, что деревья заданы так: AAAxxxAxx, где A - это узлы, а x - это ноль, поэтому этот пример будет выглядеть примерно так:

       A

    A     A

 A

Проблема в том, что я понятия не имею, как представить строку в виде двоичного дерева. У меня была идея, и я попытался добавить каждого персонажа в Arraylist, но вскоре после этого сдался. извините, если мой вопрос тупой или что-то, но я действительно понятия не имею, что делать. Буду признателен за любые советы или помощь, или если у кого-то есть лучшее представление о том, как проверить, сбалансировано ли дерево, пожалуйста, дайте мне знать. заранее спасибо.

Answer 1

Обычный способ представления двоичного дерева в массиве:

• Если позиция root равна i
• Левый дочерний элемент равен 2*i+1
• Правый дочерний элемент равен 2*i+2
• Для дерева уровня N требуется 2^N-1 пространство памяти.
• Если текущий узел равен i, то его родительский элемент равен (i-1)/2

Пример:

           2
      7        5
    2   6    X    9
   X X 5 11      4  X

Массив должен быть: {2, 7, 5, 2, 6, -1, 9, -1, -1, 5, 11, -1, - 1, 4, -1}

Есть и другие способы, но это очень распространено. Я надеюсь, что это отвечает на ваш вопрос, потому что это немного неясно.

Для кода следуйте этой ссылке .

Answer 2

Кажется, что входная строка представляет обход дерева по предварительному порядку.

Таким образом, алгоритм обычно использует рекурсию или стек, чтобы развернуть эту строку в фактическую древовидную структуру на основе узлов.

Вот код:

import java.util.*; 

class Node {
    char val;
    Node left = null;
    Node right = null;

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

    static Node fromString(String str) {
        Stack<Node> stack = new Stack<Node>();
        Node node = new Node(' ');
        Node stub = node;
        boolean goRight = false;

        for (int i = 0, n = str.length() ; i < n ; i++) { 
            char c = str.charAt(i); 
            if (c == 'x') {
                if (goRight) {
                    node.right = null;
                    node = stack.pop();
                } else {
                    node.left = null;
                    goRight = true;
                }
            } else {
                Node child = new Node(c);
                if (goRight) {
                    node.right = child;
                    node = node.right;
                    goRight = false;
                } else {
                    node.left = child;
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return stub.left;
    }
}

Вы можете назвать его так:

Node root = Node.fromString("AAAxxxAxx");

Это приведет к следующей структуре объекта:

{
    "val": 'A',
    "left": {
        "val": 'A',
        "left": { "val": 'A' }
    }, 
    "right": { "val": 'A' }
}