Почему невозможно построить бинарное дерево с заданными обходами по предзаказу, после заказа и уровню заказа?

Question

Дано:

1. Предварительный заказ.
2. Обход после заказа.
3. Уровень порядка обхода.

Нельзя построить двоичное дерево с 12, 23 или 31, или даже если дано 123! Почему это? и почему InOrder Traversal очень важен для создания оригинального дерева?

Answer 1

Мы не можем построить дерево без обхода в порядке. Зачем? Допустим, вам дан только предварительный и пост-обходной обходы. Простой пример показан ниже.
Рассмотрим два разных дерева,

ДЕРЕВО 1:

root=a;  
root->left=b;  
root->left->right=c;  

Дерево 2:

root=a;  
root->right=b;  
root->right->left=c;  

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

pre-order - a b c  
post-order - c b a  

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

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

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

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

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