Kiedy używać strategii przemierzania zamówień przedpremierowych, na zamówienie i po zamówieniu
Zanim zrozumiesz, w jakich okolicznościach użyć zamówienia przedprzedażowego, na zamówienie i po zamówieniu dla drzewa binarnego, musisz dokładnie zrozumieć, jak działa każda strategia przechodzenia. Użyj poniższego drzewa jako przykładu.
Korzeń drzewa to 7 , skrajny lewy węzeł to 0 , skrajny prawy węzeł to 10 .
Przechodzenie w przedsprzedaży :
Podsumowanie: Zaczyna się od korzenia ( 7 ), kończy się w prawym węźle ( 10 )
Sekwencja przejścia: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
Przechodzenie w kolejności :
Podsumowanie: zaczyna się w węźle położonym najbardziej po lewej stronie ( 0 ), kończy się w węźle najbardziej po prawej ( 10 )
Sekwencja przejścia: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Przechodzenie po zamówieniu :
Podsumowanie: Zaczyna się od węzła znajdującego się najbardziej po lewej stronie ( 0 ), kończy się na korzeniu ( 7 )
Sekwencja przejścia: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Kiedy korzystać z opcji zamówienia przedpremierowego, na zamówienie lub po zamówieniu?
Strategia przejścia wybrana przez programistę zależy od specyficznych potrzeb projektowanego algorytmu. Celem jest szybkość, więc wybierz strategię, która najszybciej dostarczy Ci węzły, których potrzebujesz.
Jeśli wiesz, że musisz zbadać korzenie przed sprawdzeniem jakichkolwiek liści, wybierasz zamówienie w przedsprzedaży, ponieważ napotkasz wszystkie korzenie przed wszystkimi liśćmi.
Jeśli wiesz, że musisz zbadać wszystkie liście przed jakimikolwiek węzłami, wybierasz zamówienie końcowe , ponieważ nie marnujesz czasu na sprawdzanie korzeni w poszukiwaniu liści.
Jeśli wiesz, że drzewo ma nieodłączną sekwencję w węzłach i chcesz spłaszczyć drzewo z powrotem do jego pierwotnej sekwencji, należy użyć przechodzenia w kolejności . Drzewo zostanie spłaszczone w ten sam sposób, w jaki zostało utworzone. Przechodzenie przed lub po zamówieniu może nie spowodować powrotu drzewa do sekwencji, która została użyta do jego utworzenia.
Algorytmy rekurencyjne dla zamówień w przedsprzedaży, na zamówienie i na zamówienie (C ++):
struct Node{
int data;
Node *left, *right;
};
void preOrderPrint(Node *root)
{
print(root->name); //record root
if (root->left != NULL) preOrderPrint(root->left); //traverse left if exists
if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}
void inOrderPrint(Node *root)
{
if (root.left != NULL) inOrderPrint(root->left); //traverse left if exists
print(root->name); //record root
if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}
void postOrderPrint(Node *root)
{
if (root->left != NULL) postOrderPrint(root->left); //traverse left if exists
if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
print(root->name); //record root
}