Traversarea copacilor

În acest tutorial, veți afla despre diferite tehnici de traversare a copacilor. De asemenea, veți găsi exemple de lucru ale diferitelor metode de traversare a copacilor în C, C ++, Java și Python.

Parcurgerea unui copac înseamnă vizitarea fiecărui nod din copac. S-ar putea, de exemplu, să doriți să adăugați toate valorile din arbore sau să o găsiți pe cea mai mare. Pentru toate aceste operații, va trebui să vizitați fiecare nod al arborelui.

Structurile de date liniare, cum ar fi matrici, stive, cozi și lista conectată, au un singur mod de a citi datele. Dar o structură ierarhică de date, cum ar fi un copac, poate fi parcursă în moduri diferite.

Traversarea copacului

Să ne gândim cum putem citi elementele arborelui din imaginea de mai sus.

Începând de sus, de la stânga la dreapta

 1 -> 12 -> 5 -> 6 -> 9

Începând de jos, de la stânga la dreapta

 5 -> 6 -> 12 -> 9 -> 1

Deși acest proces este oarecum ușor, nu respectă ierarhia arborelui, ci doar adâncimea nodurilor.

În schimb, folosim metode de traversare care iau în considerare structura de bază a unui arbore, adică

 struct node ( int data; struct node* left; struct node* right; )

Nodul struct indicat de stânga și dreapta ar putea avea alți copii din stânga și din dreapta, așa că ar trebui să ne gândim la ei ca sub-arbori în loc de sub-noduri.

Conform acestei structuri, fiecare copac este o combinație de

  • Un nod care transportă date
  • Două subarburi
Subarborele stânga și dreapta

Amintiți-vă că obiectivul nostru este să vizitați fiecare nod, așa că trebuie să vizităm toate nodurile din subarborele, să vizităm nodul rădăcină și să vizităm și toate nodurile din subarborele din dreapta.

În funcție de ordinea în care facem acest lucru, pot exista trei tipuri de traversare.

Trecere în ordine

  1. Mai întâi, vizitați toate nodurile din subarborele din stânga
  2. Apoi nodul rădăcină
  3. Vizitați toate nodurile din subarborele din dreapta
 inorder(root->left) display(root->data) inorder(root->right)

Trecere în avans

  1. Vizitați nodul rădăcină
  2. Vizitați toate nodurile din subarborele din stânga
  3. Vizitați toate nodurile din subarborele din dreapta
 display(root->data) preorder(root->left) preorder(root->right)

Traversarea postordinei

  1. Vizitați toate nodurile din subarborele din stânga
  2. Vizitați toate nodurile din subarborele din dreapta
  3. Vizitați nodul rădăcină
 postorder(root->left) postorder(root->right) display(root->data)

Să vizualizăm traversarea în ordine. Începem de la nodul rădăcină.

Subarborele stânga și dreapta

Parcurgem mai întâi subarborele stâng. De asemenea, trebuie să ne amintim să vizităm nodul rădăcină și subarborele drept atunci când acest arbore este terminat.

Să punem toate acestea într-un teanc, astfel încât să ne amintim.

Grămadă

Acum parcurgem subarborele arătat în partea de sus a stivei.

Din nou, urmăm aceeași regulă a inorderului

 Subarborele stâng -> rădăcină -> subarborele drept

După ce traversăm subarborele din stânga, rămânem cu

Stiva finală

Deoarece nodul "5" nu are subarburi, îl imprimăm direct. După aceea îi imprimăm părintele "12" și apoi copilul potrivit "6".

Așeza totul într-un teanc a fost util deoarece acum, după ce a fost traversat subarborele din stânga nodului rădăcină, îl putem imprima și merge în subarborele din dreapta.

După ce parcurgem toate elementele, obținem traversarea inorder ca

 5 -> 12 -> 6 -> 1 -> 9

Nu trebuie să creăm noi stiva, deoarece recursivitatea menține ordinea corectă pentru noi.

Exemple Python, Java și 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);

Articole interesante...