logo

TechCodeview

Tehnike prečkanja dreves – Vadnice za strukturo podatkov in algoritme

Tehnike prečkanja dreves vključujejo različne načine za obisk vseh vozlišč drevesa. Za razliko od linearnih podatkovnih struktur (matrika, povezan seznam, čakalne vrste, skladi itd.), ki imajo le en logičen način za prečkanje, je po drevesih mogoče prečkati na različne načine. V tem članku bomo razpravljali o vseh tehnikah prečkanja drevesa skupaj z njihovo uporabo.



Kazalo

Pomen prečkanja drevesa:

Prehod drevesa se nanaša na postopek obiska ali dostopa do vsakega vozlišča drevesa točno enkrat v določenem vrstnem redu. Algoritmi prečkanja drevesa nam pomagajo obiskati in obdelati vsa vozlišča drevesa. Ker drevo ni linearna podatkovna struktura, obstaja več vozlišč, ki jih lahko obiščemo po obisku določenega vozlišča. Obstaja več tehnik prečkanja drevesa, ki določajo vrstni red, v katerem naj bodo vozlišča drevesa obiskana.

Tehnike prečkanja dreves:



Drevesno podatkovno strukturo je mogoče prečkati na naslednje načine:

  • Depth First Search ali DFS
    • Prehod po vrstnem redu
    • Prehod pred naročilom
    • Prevoz poštnega naročila
  • Level Order Traversal ali Breadth First Search ali BFS

Prehod po vrstnem redu :

Prehod po vrstnem redu obišče vozlišče v vrstnem redu: Levo -> Koren -> Desno




Algoritem za prehod po vrstnem redu:

zgodovina različic androida

Vrstni red (drevo)

  • Prečkaj levo poddrevo, tj. pokliči Inorder(left->subtree)
  • Obiščite koren.
  • Prečkaj desno poddrevo, tj. pokliči Inorder(right->subtree)

Uporaba Inorder Traversal:

  • V primeru binarnih iskalnih dreves (BST) prečkanje po vrstnem redu daje vozlišča v nepadajočem vrstnem redu.
  • Če želite dobiti vozlišča BST v nenaraščajočem vrstnem redu, lahko uporabite različico prečkanja po vrstnem redu, kjer je prečkanje po vrstnem redu obrnjeno.
  • Prehod po vrstnem redu je mogoče uporabiti za ovrednotenje aritmetičnih izrazov, shranjenih v izraznih drevesih.

Delček kode za prehod po vrstnem redu:

C++ 
// 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->levo);  // Nato natisnite podatke vozlišča cout<< node->podatke<< ' ';  // Now recur on right child  printInorder(node->prav); }>
C 
// 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->levo);  // Nato natisni podatke vozlišča printf('%d ', node->data);  // Zdaj se ponovi na desnem podrejenem printInorder(node->right); }>
Java 
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); }>
Python3 
# 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)>
C# 
// 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); }>
Javascript 
// 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); }>
Izhod 
Inorder traversal of binary tree is 4 2 5 1 3>

Časovna zapletenost: O(N)
Pomožni prostor: Če ne upoštevamo velikosti sklada za klice funkcij, potem O(1), sicer O(h), kjer je h višina drevesa.

Prehod pred naročilom :

Prehod po prednaročilu obišče vozlišče v vrstnem redu: Koren -> Levo -> Desno

Algoritem za prehod pred naročilom:

Prednaročilo (drevo)

  • Obiščite koren.
  • Prečkajte levo poddrevo, tj. pokličite Preorder(left->subtree)
  • Prečkaj desno poddrevo, tj. pokliči Preorder(right->subtree)

Uporaba prehoda prednaročila:

  • Prehod pred naročilom se uporablja za ustvarjanje kopije drevesa.
  • Prehod pred naročilom se uporablja tudi za pridobivanje predponskih izrazov v izraznem drevesu.

Delček kode za prehod pred naročilom:

C++ 
// 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->podatke<< ' ';  // Then recur on left subtree  printPreorder(node->levo);  // Zdaj se ponovi na desnem poddrevesu printPreorder(node->right); }>
C 
// 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->podatkov);  // Nato se ponovi na levem poddrevesu printPreorder(node->left);  // Zdaj se ponovi na desnem poddrevesu printPreorder(node->right); }>
Java 
// 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); }>
Python3 
# 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)>
C# 
// 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); }>
Javascript 
// 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); }>
Izhod 
Preorder traversal of binary tree is 1 2 4 5 3>

Časovna zapletenost: O(N)
Pomožni prostor: Če ne upoštevamo velikosti sklada za klice funkcij, potem O(1), sicer O(h), kjer je h višina drevesa.

Prevoz poštnega naročila :

Prehod po naročilu obišče vozlišče v vrstnem redu: Levo -> Desno -> Koren

Algoritem za prehod po naročilu:

Algoritem Poštna nakaznica (drevo)

  • Prečkajte levo poddrevo, tj. pokličite Postorder(left->subtree)
  • Prečkaj desno poddrevo, tj. pokliči Postorder(right->subtree)
  • Obiščite koren

Uporaba Mailorder Traversal:

  • Prehod po naročilu se uporablja za brisanje drevesa. glej vprašanje za izbris drevesa za podrobnosti.
  • Prehod po vrstnem redu je koristen tudi za pridobitev izraza postfix izraznega drevesa.
  • Prehod po naročilu lahko pomaga pri algoritmih zbiranja smeti, zlasti v sistemih, kjer se uporablja ročno upravljanje pomnilnika.

Delček kode za prehod po pošti:

C++ 
// 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->levo);  // Nato se ponovi na desnem poddrevesu printPostorder(node->right);  // Sedaj obravnavajte vozlišče cout<< node->podatke<< ' '; }>
C 
// 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->levo);  // Nato se ponovi na desnem poddrevesu printPostorder(node->right);  // Sedaj obravnavamo vozlišče printf('%d ', node->data); }>
Java 
// 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 + ' '); }>
Python3 
# 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=' '),>
C# 
// 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 + ' '); }>
Javascript 
// 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 + ' '); }>
Izhod 
Postorder traversal of binary tree is 4 5 2 3 1>

Level Order Traversal :

Level Order Traversal v celoti obišče vsa vozlišča, prisotna na isti ravni, preden obišče naslednjo raven.

Algoritem za prehod nivojev:

LevelOrder(drevo)

  • Ustvarite prazno čakalno vrsto Q
  • Postavite korensko vozlišče drevesa v Q
  • Zanka, medtem ko Q ni prazen
    • Odstranite vozlišče iz vrste Q in ga obiščite
    • Postavite v čakalno vrsto levega podrejenega vozlišča, če obstaja
    • Postavite v čakalno vrsto pravega podrejenega vozlišča, ki je izločeno iz čakalne vrste, če obstaja

Uporaba vrstnega reda ravni:

  • Level Order Traversal se večinoma uporablja kot iskanje najprej v širino za iskanje ali obdelavo vozlišč po ravni.
  • Level Order traversal se uporablja tudi za Serializacija in deserializacija drevesa .

Odrezek kode za prečkanje vrstnega reda ravni:

C++ 
// 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;  // Postavi koren v čakalno vrsto in inicializiraj višino q.push(root);  while (q.empty() == false) { // Natisni začetek čakalne vrste in ga odstrani iz čakalne vrste Node* node = q.front();  cout<< node->podatke<< ' ';  q.pop();  // Enqueue left child  if (node->levo != NULL) q.push(vozlišče->levo);  // V čakalno vrsto postavi desnega podrejenega if (node->right != NULL) q.push(node->right);  } }>
C 
// 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->podatki);  // Postavi v čakalno vrsto levega podrejenega if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // V čakalno vrsto postavi desni podrejeni if ​​(temp_node->right) enQueue(queue, &rear, temp_node->right);  // Izključi vozlišče iz čakalne vrste in ga naredi za temp_node temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuečakalna vrsta = nov LinkedList();  queue.add(root);  medtem ko (!queue.isEmpty()) { // poll() odstrani trenutno glavo.  Vozlišče tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Postavi v čakalno vrsto levega podrejenega if (tempNode.left != null) { queue.add(tempNode.left);  } // V čakalno vrsto postavi desnega podrejenega if (tempNode.right != null) { queue.add(tempNode.right);  } } }>
Python3 
# 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): # Natisni začetek čakalne vrste in # ga odstrani iz čakalne vrste print(queue[0].data, end=' ') node = queue.pop(0) # V čakalno vrsto postavi levega otroka, če node.left ni None: queue.append(node.left) # V čakalno vrsto postavi desnega otroka, če node.right ni None: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuečakalna vrsta = nova čakalna vrsta();  queue.Enqueue(root);  medtem ko (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Postavi v čakalno vrsto levega podrejenega if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // V čakalno vrsto postavi desnega podrejenega if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>
JavaScript 
// 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);  }  } }>

Drugi prehodi dreves:

  1. Prehod meje
  2. Diagonalno prečenje

1. Prehod meje :

Prehod meje drevesa vključuje:

  • leva meja (vozlišča na levi brez listnih vozlišč)
  • listi (sestavljeni so samo iz listnih vozlov)
  • desna meja (vozlišča na desni brez listnih vozlišč)

Algoritem za prehod meje:

BoundaryTraversal(drevo)

  • Če koren ni nič:
    • Natisnite korenske podatke
    • PrintLeftBoundary(root->left) // Natisni leva mejna vozlišča
    • PrintLeafNodes(root->left) // Natisne listna vozlišča levega poddrevesa
    • PrintLeafNodes(root->right) // Natisne listna vozlišča desnega poddrevesa
    • PrintRightBoundary(root->right) // Natisni desna mejna vozlišča

Uporaba prečkanja meje:

  • Prehod meja pomaga vizualizirati zunanjo strukturo binarnega drevesa, kar zagotavlja vpogled v njegovo obliko in meje.
  • Prehod meje ponuja način za dostop in spreminjanje teh vozlišč, kar omogoča operacije, kot je obrezovanje ali prestavljanje mejnih vozlišč.

2. Diagonalno prečenje

V Diagonalnem prehodu drevesa bodo vsa vozlišča v eni diagonali natisnjena eno za drugim.

Algoritem za diagonalno prečkanje:

Diagonalni prehod (drevo):

  • Če koren ni nič:
    • Ustvarite prazen zemljevid
    • DiagonalTraversalUtil(root, 0, M) // Pokliči pomočno funkcijo z začetno diagonalno stopnjo 0
    • Za vsak par ključ-vrednost (diagonalna raven, vozlišča) v M:
      • Za vsako vozlišče v vozliščih:
      • Natisnite podatke vozlišča

DiagonalTraversalUtil (vozlišče, diagonalna raven, M):

  • Če je vozlišče nič:
  • Vrnitev
  • Če diagonalLevel ni prisoten v M:
    • Ustvarite nov seznam v M za diagonalLevel
  • Dodajanje podatkov vozlišča na seznam na M[diagonalna raven]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Premik levega otroka s povečano diagonalno stopnjo
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Premik desnega podrejenega z enako diagonalno ravnjo

Uporaba diagonalnega prehoda:

  • Diagonalno prečkanje pomaga pri vizualizaciji hierarhične strukture binarnih dreves, zlasti v drevesnih podatkovnih strukturah, kot so binarna iskalna drevesa (BST) in kopična drevesa.
  • Diagonalno prečkanje je mogoče uporabiti za izračun vsot poti vzdolž diagonal v binarnem drevesu.

Pogosto zastavljena vprašanja (FAQ) o tehnikah prečkanja dreves:

1. Kaj so tehnike prečkanja dreves?

Tehnike prečkanja drevesa so metode, ki se uporabljajo za obisk in obdelavo vseh vozlišč v strukturi drevesnih podatkov. Omogočajo vam dostop do vsakega vozlišča natanko enkrat na sistematičen način.

2. Katere so običajne vrste prečkanja drevesa?

Običajne vrste prečkanja drevesa so: prečkanje po vrstnem redu, prečkanje po predvrstnem redu, prečkanje po vrstnem redu, prečkanje po vrstnem redu ravni (iskanje najprej v širino)

3. Kaj je prečkanje vrstnega reda?

Inorder traversal je metoda prehoda najprej v globino, kjer se vozlišča obiščejo v vrstnem redu: levo poddrevo, trenutno vozlišče, desno poddrevo.

4. Kaj je prehod prednaročila?

Prehod po prednaročilu je metoda prehoda najprej v globino, pri kateri so vozlišča obiskana v vrstnem redu: trenutno vozlišče, levo poddrevo, desno poddrevo.

5. Kaj je prehod poštnega naloga?

Prehod po vrstnem redu je metoda prečkanja najprej v globino, kjer se vozlišča obiščejo v vrstnem redu: levo poddrevo, desno poddrevo, trenutno vozlišče.

6. Kaj je prečkanje reda ravni?

Prehod po vrstnem redu ravni, znan tudi kot iskanje najprej v širino (BFS), obišče vozlišča nivo za nivojem, začenši od korena in se premakne na naslednjo raven, preden prečka globlje.

7. Kdaj naj uporabim posamezno tehniko prečkanja?

Prehod po vrstnem redu se pogosto uporablja za binarna iskalna drevesa, da dobimo vozlišča v razvrščenem vrstnem redu.

Prehod pred naročilom je uporaben za ustvarjanje kopije drevesa.

Prehod po vrstnem redu se običajno uporablja v izraznih drevesih za vrednotenje izrazov.

Prehod vrstnega reda ravni je koristen za iskanje najkrajše poti med vozlišči.

8. Kako implementiram algoritme za prečkanje dreves?

Algoritme za prečkanje dreves je mogoče izvajati rekurzivno ali iterativno, odvisno od posebnih zahtev in uporabljenega programskega jezika.

9. Ali je mogoče algoritme prečkanja dreves uporabiti za druge drevesne strukture?

Da, algoritme za prečkanje dreves je mogoče prilagoditi za prečkanje drugih drevesnih struktur, kot so binarne kopice, n-arna drevesa in grafi, predstavljeni kot drevesa.

10. Ali je pri izbiri tehnike prečkanja treba upoštevati učinkovitost?

Upoštevanje zmogljivosti je odvisno od dejavnikov, kot so velikost in oblika drevesa, razpoložljiv pomnilnik in posebne operacije, ki se izvajajo med prečkanjem. Na splošno lahko izbira tehnike prečkanja vpliva na učinkovitost določenih operacij, zato je pomembno izbrati najprimernejšo metodo za vaš specifični primer uporabe.

Nekaj ​​drugih pomembnih vaj:

  • Vadnica DSA
  • Vadnica za načrtovanje sistema
  • Načrt razvoja programske opreme
  • Načrt, kako postati produktni vodja
  • Naučite se SAP
  • Naučite se SEO