Koku šķērsošanas metodes ietver dažādus veidus, kā apmeklēt visus koka mezglus. Atšķirībā no lineārajām datu struktūrām (masīvs, saistītais saraksts, rindas, skursteņi utt.), kurām ir tikai viens loģisks veids, kā tos šķērsot, kokus var šķērsot dažādos veidos. Šajā rakstā mēs apspriedīsim visas koku šķērsošanas metodes, kā arī to izmantošanas veidus.

Satura rādītājs

• Koka šķērsošanas nozīme
• Koku šķērsošanas metodes
• Pasūtījuma šķērsošana
• Iepriekšpasūtīšanas šķērsošana
• Pasta pasūtījumu šķērsošana
• Līmeņa pasūtījumu izbraukšana
• Citi koku apceļojumi
• Bieži uzdotie jautājumi (FAQ) par koku šķērsošanas metodēm

Koka šķērsošanas nozīme:

Koku šķērsošana attiecas uz katra koka mezgla apmeklējuma vai piekļuves procesu tieši vienreiz noteiktā secībā. Koka šķērsošanas algoritmi palīdz mums apmeklēt un apstrādāt visus koka mezglus. Tā kā koks nav lineāra datu struktūra, ir vairāki mezgli, kurus mēs varam apmeklēt pēc noteikta mezgla apmeklējuma. Ir vairāki koku šķērsošanas paņēmieni, kas nosaka secību, kādā jāapmeklē koka mezgli.

Koku šķērsošanas metodes:

Koka datu struktūru var šķērsot šādos veidos:

• Pirmā dziļuma meklēšana vai DFS
  • Pasūtījuma šķērsošana
  • Iepriekšpasūtīšanas šķērsošana
  • Pasta pasūtījumu šķērsošana
• Līmeņa secības šķērsošana vai pirmā meklēšana pēc platuma vai BFS

Pasūtījuma šķērsošana :

Pasūtījuma šķērsošana apmeklē mezglu šādā secībā: Pa kreisi -> Sakne -> Pa labi

Inorder Traversal algoritms:

Kārtība (koks)

• Pārejiet pa kreiso apakškoku, t.i., izsauciet Inorder(pa kreisi->apakškoks)
• Apmeklējiet sakni.
• Pārejiet pa labo apakškoku, t.i., izsauciet Inorder(labais->apakškoks)

Inorder Traversal izmantošanas veidi:

• Bināro meklēšanas koku (BST) gadījumā Inorder traversal dod mezglus nesamazināmā secībā.
• Lai iegūtu BST mezglus nepalielinošā secībā, var izmantot Inorder traversal variantu, kurā Inorder traversal ir apgriezts.
• Kārtības šķērsošanu var izmantot, lai novērtētu izteiksmju kokos saglabātās aritmētiskās izteiksmes.

Koda fragments Inorder Traversal:

// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->pa kreisi);  // Pēc tam izdrukājiet node cout datus<< node->datus<< ' ';  // Now recur on right child  printInorder(node->pa labi); }>

// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->pa kreisi);  // Pēc tam izdrukājiet mezgla printf('%d ', node->data) datus;  // Tagad atkārtojas labajā bērnā printInorder(node->right); }>

void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>

# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>

// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>

// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>

Inorder traversal of binary tree is 4 2 5 1 3>

Laika sarežģītība: O(N)
Palīgtelpa: Ja neņemam vērā funkciju izsaukšanas kaudzes lielumu, tad O(1), pretējā gadījumā O(h), kur h ir koka augstums.

Iepriekšpasūtīšanas šķērsošana :

Priekšpasūtīšanas caurlaide apmeklē mezglu šādā secībā: Sakne -> pa kreisi -> pa labi

Algoritms priekšpasūtīšanas apritei:

Priekšpasūtījums (koks)

• Apmeklējiet sakni.
• Pārejiet pa kreiso apakškoku, t.i., izsauciet Preorder(left->subtree)
• Pārejiet pa labo apakškoku, t.i., izsauciet Preorder(labais->apakškoks)

Priekšpasūtīšanas caurlaides izmantošana:

• Priekšpasūtīšanas šķērsošana tiek izmantota, lai izveidotu koka kopiju.
• Priekšpasūtīšanas šķērsošana tiek izmantota arī, lai izteiksmju kokā iegūtu prefiksu izteiksmes.

Koda fragments priekšpasūtījuma iziešanai:

// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->datus<< ' ';  // Then recur on left subtree  printPreorder(node->pa kreisi);  // Tagad atkārtojas labajā apakškokā printPreorder(node->right); }>

// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->dati);  // Pēc tam atkārtojas kreisajā apakškokā printPreorder(node->left);  // Tagad atkārtojas labajā apakškokā printPreorder(node->right); }>

// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>

# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>

// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>

// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>

Preorder traversal of binary tree is 1 2 4 5 3>

Laika sarežģītība: O(N)
Palīgtelpa: Ja neņemam vērā funkciju izsaukšanas kaudzes lielumu, tad O(1), pretējā gadījumā O(h), kur h ir koka augstums.

Pasta pasūtījumu šķērsošana :

Pēc pasūtījuma šķērsošana apmeklē mezglu šādā secībā: Pa kreisi -> Pa labi -> Sakne

Algoritms pēc pasūtījuma iziešanai:

Algoritms Pasta pasūtījums (koks)

asv, cik pilsētu

• Pārejiet pa kreiso apakškoku, t.i., izsauciet Postorder(pa kreisi->apakškoks)
• Pārejiet pa labo apakškoku, t.i., izsauciet Postorder(labais->apakškoks)
• Apmeklējiet sakni

Mailorder Traversal lietojumi:

• Lai izdzēstu koku, tiek izmantota postorder traversal. Skat jautājums par koka dzēšanu sīkākai informācijai.
• Postorder traversal ir arī noderīga, lai iegūtu izteiksmes koka postfix izteiksmi.
• Postorder šķērsošana var palīdzēt atkritumu savākšanas algoritmos, jo īpaši sistēmās, kurās tiek izmantota manuāla atmiņas pārvaldība.

Koda fragments Maillorder Traversal:

// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->pa kreisi);  // Tad atkārtojas labajā apakškokā printPostorder(node->right);  // Tagad nodarbojas ar node cout<< node->datus<< ' '; }>

// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->pa kreisi);  // Tad atkārtojas labajā apakškokā printPostorder(node->right);  // Tagad nodarbojieties ar mezglu printf('%d ', node->data); }>

// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  System.out.print(node.key + ' '); }>

# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>

// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>

// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>

Postorder traversal of binary tree is 4 5 2 3 1>

Līmeņa pasūtījumu izbraukšana :

Līmeņa pasūtījumu izbraukšana pirms nākamā līmeņa apmeklēšanas pilnībā apmeklē visus mezglus, kas atrodas tajā pašā līmenī.

Algoritms līmeņa pasūtījuma apbraukšanai:

Līmeņa kārtība (koks)

• Izveidojiet tukšu rindu Q
• Ievietojiet koka saknes mezglu rindā uz Q
• Cilpa, kamēr Q nav tukšs
  • Atvienojiet mezglu no Q un apmeklējiet to
  • Ievietojiet rindā atceltā mezgla kreiso atvasināto punktu, ja tāds pastāv
  • Ievietojiet rindā atņemtā mezgla pareizo atvasinājumu, ja tāds pastāv

Līmeņu secības lietojumi:

• Līmeņu secības iziešana galvenokārt tiek izmantota kā pirmā meklēšanas platums, lai meklētu vai apstrādātu mezglus pa līmeņiem.
• Līmeņa pasūtījuma šķērsošana tiek izmantota arī Koku serializācija un deserializācija .

Koda fragments līmeņa pasūtījuma iziešanai:

// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueq;  // Iekļauts saknes rindā un inicializēts augstums q.push(root);  while (q.empty() == false) { // Izdrukā rindas priekšpusi un noņem to no rindas Node* node = q.front();  cout<< node->datus<< ' ';  q.pop();  // Enqueue left child  if (node->pa kreisi != NULL) q.push(node->left);  // Ierindot labo atvasi if (node->right != NULL) q.push(node->right);  } }>

// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->dati);  // Rindā atstāto bērnu if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Rindā labo atvasināto if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Atvienot mezglu un padarīt to temp_node temp_node = deQueue(queue, &front);  } }>

// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuerinda = jauns LinkedList();  queue.add(sakne);  while (!queue.isEmpty()) { // poll() noņem pašreizējo galveni.  Mezgls tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Ielikt rindā kreiso bērnu if (tempNode.left != null) { queue.add(tempNode.left);  } // Iestatīt pareizo bērnu rindā if (tempNode.right != null) { queue.add(tempNode.right);  } } }>

# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Izdrukājiet rindas priekšpusi un # noņemiet to no rindas print(queue[0].data, end=' ') node = queue.pop(0) # Ja node.left nav None: queue.append(node.left) # Iekļaut pareizo atvasināto rindu, ja node.right nav Nav: queue.append(node.right)>

// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuerinda = jauna rinda();  rinda.Rinda(sakne);  while (rinda.Skaits != 0) { Mezgls tempMezgls = rinda.Dequeue();  Console.Write(tempNode.data + ' ');  // Ielikt rindā kreiso bērnu if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Iestatīt pareizo atvasināto rindu if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>

// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Citi koku apceļojumi:

1. Robežu šķērsošana
2. Diagonālā šķērsošana

1. Robežu šķērsošana :

Robežu šķērsošana kokā ietilpst:

• kreisā robeža (mezgli kreisajā pusē, izņemot lapu mezglus)
• lapas (sastāv tikai no lapu mezgliem)
• labā robeža (mezgli labajā pusē, izņemot lapu mezglus)

Robežu šķērsošanas algoritms:

Robežas šķērsošana (koks)

• Ja saknes vērtība nav nulle:
  • Drukājiet saknes datus
  • PrintLeftBoundary(root->left) // Drukājiet kreisos robežmezglus
  • PrintLeafNodes(root->left) // Drukājiet kreisā apakškoka lapu mezglus
  • PrintLeafNodes(root->right) // Drukājiet labā apakškoka lapu mezglus
  • PrintRightBoundary(root->right) // Drukāt labos robežmezglus

Robežu šķērsošanas izmantošana:

• Robežu šķērsošana palīdz vizualizēt binārā koka ārējo struktūru, sniedzot ieskatu tā formā un robežās.
• Robežu šķērsošana nodrošina veidu, kā piekļūt šiem mezgliem un tos modificēt, ļaujot veikt tādas darbības kā robežmezglu apgriešana vai pārvietošana.

2. Diagonālā šķērsošana

Koka šķērsgriezumā pa diagonāli visi mezgli vienā diagonālē tiks drukāti pa vienam.

Diagonālās šķērsošanas algoritms:

DiagonalTraversal (koks):

• Ja saknes vērtība nav nulle:
  • Izveidojiet tukšu karti
  • DiagonalTraversalUtil(root, 0, M) // Zvana palīga funkcija ar sākotnējo diagonāles līmeni 0
  • Katram atslēgas vērtību pārim (diagonalLevel, mezgli) M:
    • Katram mezglam mezglos:
    • Drukāt mezgla datus

DiagonalTraversalUtil(mezgls, diagonalLevel, M):

• Ja mezgls ir nulle:
• Atgriezties
• Ja diagonalLevel nav M:
  • Izveidojiet jaunu sarakstu M, kas paredzēts diagonalLevel
• Pievienot mezgla datus sarakstam M[diagonalLevel]
• DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Travers kreiso bērnu ar paaugstinātu diagonāles līmeni
• DiagonalTraversalUtil(node->right, diagonalLevel, M) // Travers pa labi ar bērnu ar tādu pašu diagonāles līmeni

Diagonālās šķērsošanas izmantošana:

• Diagonālā šķērsošana palīdz vizualizēt bināro koku hierarhisko struktūru, īpaši uz kokiem balstītās datu struktūrās, piemēram, bināros meklēšanas kokos (BST) un kaudzes kokos.
• Diagonālo šķērsošanu var izmantot, lai aprēķinātu ceļa summas pa diagonālēm binārā kokā.

Bieži uzdotie jautājumi (FAQ) par koku šķērsošanas metodēm:

1. Kādi ir koku šķērsošanas paņēmieni?

Koku šķērsošanas metodes ir metodes, ko izmanto, lai apmeklētu un apstrādātu visus koka datu struktūras mezglus. Tie ļauj sistemātiski piekļūt katram mezglam tieši vienu reizi.

2. Kādi ir izplatītākie koku šķērsošanas veidi?

Izplatītākie koku šķērsošanas veidi ir: šķērsošana pēc kārtas, priekšpasūtīšanas šķērsošana, pēcpasūtīšanas šķērsošana, līmeņa secības šķērsošana (meklēšana pēc platuma).

3. Kas ir Inorder traversal?

Inorder traversal ir dziļuma pirmā šķērsošanas metode, kurā mezgli tiek apmeklēti šādā secībā: kreisais apakškoks, pašreizējais mezgls, labais apakškoks.

4. Kas ir priekšpasūtīšanas šķērsošana?

Priekšpasūtīšanas šķērsošana ir dziļuma pirmā šķērsošanas metode, kurā mezgli tiek apmeklēti šādā secībā: pašreizējais mezgls, kreisais apakškoks, labais apakškoks.

5. Kas ir pasta pasūtījuma šķērsošana?

Postorder traversal ir dziļuma pirmā šķērsošanas metode, kurā mezgli tiek apmeklēti šādā secībā: kreisais apakškoks, labais apakškoks, pašreizējais mezgls.

6. Kas ir līmeņa pasūtījuma šķērsošana?

Līmeņa secības šķērsošana, kas pazīstama arī kā pirmā meklēšana (BFS), apmeklē mezglus pēc līmeņa, sākot no saknes un pārejot uz nākamo līmeni, pirms šķērsot dziļāk.

7. Kad man vajadzētu izmantot katru šķērsošanas paņēmienu?

Kārtības šķērsošana bieži tiek izmantota binārajiem meklēšanas kokiem, lai iegūtu mezglus sakārtotā secībā.

Priekšpasūtīšanas šķērsošana ir noderīga, lai izveidotu koka kopiju.

Postorder traversal parasti tiek izmantots izteiksmju kokos, lai novērtētu izteiksmes.

Līmeņu secības šķērsošana ir noderīga, lai atrastu īsāko ceļu starp mezgliem.

8. Kā ieviest koku šķērsošanas algoritmus?

Koku šķērsošanas algoritmus var ieviest rekursīvi vai iteratīvi atkarībā no konkrētajām prasībām un izmantotās programmēšanas valodas.

9. Vai koku šķērsošanas algoritmus var pielietot citām kokiem līdzīgām struktūrām?

Jā, koku šķērsošanas algoritmus var pielāgot, lai šķērsotu citas kokiem līdzīgas struktūras, piemēram, bināros kaudzes, n-ārus kokus un grafikus, kas attēloti kā koki.

10. Vai, izvēloties šķērsošanas tehniku, ir jāņem vērā veiktspējas apsvērumi?

Veiktspējas apsvērumi ir atkarīgi no tādiem faktoriem kā koka izmērs un forma, pieejamā atmiņa un īpašas darbības, kas tiek veiktas šķērsošanas laikā. Kopumā šķērsošanas tehnikas izvēle var ietekmēt noteiktu darbību efektivitāti, tāpēc ir svarīgi izvēlēties savam konkrētajam lietošanas gadījumam piemērotāko metodi.

Dažas citas svarīgas apmācības:

• DSA apmācība
• Sistēmas projektēšanas apmācība
• Programmatūras izstrādes ceļvedis
• Ceļvedis, lai kļūtu par produktu vadītāju
• Uzziniet SAP
• Apgūstiet SEO