W tym samouczku poznasz różne techniki przechodzenia po drzewie. Znajdziesz również działające przykłady różnych metod przechodzenia po drzewie w językach C, C ++, Java i Python.
Przechodzenie po drzewie oznacza odwiedzanie każdego węzła w drzewie. Możesz na przykład chcieć dodać wszystkie wartości w drzewie lub znaleźć największą. Aby wykonać wszystkie te operacje, musisz odwiedzić każdy węzeł drzewa.
Liniowe struktury danych, takie jak tablice, stosy, kolejki i lista połączona, mają tylko jeden sposób odczytu danych. Ale hierarchiczna struktura danych, taka jak drzewo, może być przemierzana na różne sposoby.
Przechodzenie przez drzewo
Zastanówmy się, jak możemy odczytać elementy drzewa na powyższym obrazku.
Zaczynając od góry, od lewej do prawej
1 -> 12 -> 5 -> 6 -> 9
Zaczynając od dołu, od lewej do prawej
5 -> 6 -> 12 -> 9 -> 1
Chociaż proces ten jest dość łatwy, nie uwzględnia hierarchii drzewa, a jedynie głębokość węzłów.
Zamiast tego używamy metod przechodzenia, które uwzględniają podstawową strukturę drzewa, tj
struct node ( int data; struct node* left; struct node* right; )
Węzeł struct wskazywany przez lewy i prawy może mieć inne lewe i prawe dzieci, więc powinniśmy myśleć o nich jako o poddrzewach, a nie o węzłach podrzędnych.
Zgodnie z tą strukturą, każde drzewo jest połączeniem
- Węzeł przenoszący dane
- Dwa poddrzewa
Lewe i prawe poddrzewo
Pamiętaj, że naszym celem jest odwiedzenie każdego węzła, więc musimy odwiedzić wszystkie węzły w poddrzewie, odwiedzić węzeł główny i odwiedzić również wszystkie węzły w prawym poddrzewie.
W zależności od kolejności, w jakiej to robimy, mogą istnieć trzy rodzaje przechodzenia.
Przechodzenie w porządku
- Najpierw odwiedź wszystkie węzły w lewym poddrzewie
- Następnie węzeł główny
- Odwiedź wszystkie węzły w prawym poddrzewie
inorder(root->left) display(root->data) inorder(root->right)
Przechodzenie w przedsprzedaży
- Odwiedź węzeł główny
- Odwiedź wszystkie węzły w lewym poddrzewie
- Odwiedź wszystkie węzły w prawym poddrzewie
display(root->data) preorder(root->left) preorder(root->right)
Przechodzenie po zamówieniu
- Odwiedź wszystkie węzły w lewym poddrzewie
- Odwiedź wszystkie węzły w prawym poddrzewie
- Odwiedź węzeł główny
postorder(root->left) postorder(root->right) display(root->data)
Wizualizujmy przechodzenie w kolejności. Zaczynamy od węzła głównego.
Lewe i prawe poddrzewo
Najpierw przechodzimy przez lewe poddrzewo. Musimy również pamiętać, aby po ukończeniu tego drzewa odwiedzić węzeł główny i odpowiednie poddrzewo.
Połóżmy to wszystko na stosie, abyśmy pamiętali.
Stos
Teraz przechodzimy do poddrzewa wskazanego na GÓRZE stosu.
Ponownie kierujemy się tą samą zasadą porządku
Lewe poddrzewo -> root -> prawe poddrzewo
Po przejściu przez lewe poddrzewo zostajemy z
Ostateczny stos
Ponieważ węzeł „5” nie ma żadnych poddrzew, drukujemy go bezpośrednio. Następnie wypisujemy jego rodzica „12”, a następnie właściwe dziecko „6”.
Umieszczenie wszystkiego na stosie było pomocne, ponieważ teraz, gdy przeszło lewe poddrzewo węzła głównego, możemy je wydrukować i przejść do prawego poddrzewa.
Po przejściu przez wszystkie elementy otrzymujemy przechodzenie w kolejności jako
5 -> 12 -> 6 -> 1 -> 9
Nie musimy sami tworzyć stosu, ponieważ rekurencja utrzymuje odpowiednią kolejność.
Przykłady w Pythonie, Javie i C / C ++
Python Java C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
