In questo tutorial imparerai a conoscere diverse tecniche di attraversamento degli alberi. Inoltre, troverai esempi funzionanti di diversi metodi di attraversamento dell'albero in C, C ++, Java e Python.
Attraversare un albero significa visitare ogni nodo dell'albero. Ad esempio, potresti voler aggiungere tutti i valori nell'albero o trovare quello più grande. Per tutte queste operazioni, dovrai visitare ogni nodo dell'albero.
Le strutture di dati lineari come array, stack, code e liste collegate hanno solo un modo per leggere i dati. Ma una struttura di dati gerarchica come un albero può essere attraversata in diversi modi.
Attraversamento dell'albero
Pensiamo a come possiamo leggere gli elementi dell'albero nell'immagine mostrata sopra.
Partendo dall'alto, da sinistra a destra
1 -> 12 -> 5 -> 6 -> 9
Partendo dal basso, da sinistra a destra
5 -> 6 -> 12 -> 9 -> 1
Sebbene questo processo sia piuttosto semplice, non rispetta la gerarchia dell'albero, ma solo la profondità dei nodi.
Invece, usiamo metodi di attraversamento che tengono conto della struttura di base di un albero, es
struct node ( int data; struct node* left; struct node* right; )
Il nodo struct puntato da left e right potrebbe avere altri figli left e right quindi dovremmo pensarli come sottoalberi invece che sotto-nodi.
Secondo questa struttura, ogni albero è una combinazione di
- Un nodo che trasporta dati
- Due sottoalberi
Sottostruttura sinistra e destra
Ricorda che il nostro obiettivo è visitare ogni nodo, quindi dobbiamo visitare tutti i nodi nel sottoalbero, visitare il nodo radice e visitare anche tutti i nodi nel sottoalbero destro.
A seconda dell'ordine in cui lo facciamo, possono esserci tre tipi di attraversamento.
Attraversamento in ordine
- Per prima cosa, visita tutti i nodi nella sottostruttura di sinistra
- Quindi il nodo radice
- Visita tutti i nodi nella sottostruttura giusta
inorder(root->left) display(root->data) inorder(root->right)
Preordina attraversamento
- Visita il nodo radice
- Visita tutti i nodi nella sottostruttura di sinistra
- Visita tutti i nodi nella sottostruttura giusta
display(root->data) preorder(root->left) preorder(root->right)
Attraversamento postale
- Visita tutti i nodi nella sottostruttura di sinistra
- Visita tutti i nodi nella sottostruttura giusta
- Visita il nodo radice
postorder(root->left) postorder(root->right) display(root->data)
Visualizziamo l'attraversamento in ordine. Partiamo dal nodo radice.
Sottostruttura sinistra e destra
Attraversiamo prima la sottostruttura sinistra. Dobbiamo anche ricordarci di visitare il nodo radice e il sottoalbero destro quando questo albero è finito.
Mettiamo tutto questo in una pila in modo che ricordiamo.
Pila
Ora passiamo alla sottostruttura indicata nella PARTE SUPERIORE della pila.
Anche in questo caso, seguiamo la stessa regola di inordine
Sottostruttura sinistra -> radice -> sottostruttura destra
Dopo aver attraversato la sottostruttura di sinistra, ci rimane
Stack finale
Poiché il nodo "5" non ha sottostrutture, lo stampiamo direttamente. Dopodiché stampiamo il suo genitore "12" e poi il figlio destro "6".
Mettere tutto su uno stack è stato utile perché ora che il sottoalbero sinistro del nodo radice è stato attraversato, possiamo stamparlo e andare al sottoalbero destro.
Dopo aver esaminato tutti gli elementi, otteniamo l'attraversamento in ordine come
5 -> 12 -> 6 -> 1 -> 9
Non dobbiamo creare lo stack da soli perché la ricorsione mantiene l'ordine corretto per noi.
Esempi di Python, Java e C / C ++
Python Java C 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);
