Почему невозможно построить двоичное дерево с запросами на предзаказ, почтовый заказ и порядок заказа уровня?

Question

Предоставлено:

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

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

Answer 1

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

Tree 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 

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

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

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

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

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