как разобрать древовидную структуру данных?

Question

У меня есть древовидная структура данных, состоящая из узлов, которые мне нужно проанализировать в дереве выражений. Мои узлы выглядят так (упрощенно):

    public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Operation OperationType { get; set; }
        public object Value { get; set; }
    }

Каков наилучший / правильный способ найти основание дерева и работать в обратном направлении, создавая дерево выражений? Вы сначала разбираете влево или вправо?

Answer 1

Если вы хотите сначала добраться до нижней части дерева, тогда вы выполняете поиск по порядку или, возможно, по порядку. Поиск по порядку найдет сначала нижний, самый левый узел, за которым следует родительский узел этого узла, а затем правый дочерний узел родителя. Поиск «после заказа» будет «посещать» как левый дочерний узел, так и правый дочерний узел до посещения родительского узла.

Рассмотрим выражение «x + y». Поиск по порядку даст:

'x', '+', 'y'

, тогда как поиск по порядку выдаст:

'x', 'y', '+'

Answer 2

Как уже упоминалось, это не имеет значения, куда вы идете в первую очередь. Но самый обычный алгоритм обхода дерева . Если это дерево организовано так, как я думаю, рекомендовано сделать заказ:

(из википедии) Чтобы просмотреть непустое двоичное дерево в порядке следования, выполните следующие операции рекурсивно на каждом узле:

1. Пройдите по левому поддереву.
2. Посетите корень.
3. Пройдите по правому поддереву.

(Это также называется симметричным обходом.)

Answer 3

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