logo

TechCodeview

Medžio apėjimo metodai – duomenų struktūrų ir algoritmų vadovėliai

Medžio apėjimo technika apima įvairius būdus aplankyti visus medžio mazgus. Skirtingai nuo linijinių duomenų struktūrų (masyvas, susietas sąrašas, eilės, krūvos ir kt.), kurios turi tik vieną loginį būdą jas eiti, medžius galima pereiti įvairiais būdais. Šiame straipsnyje aptarsime visus medžių perėjimo būdus ir jų naudojimą.



Turinys

Medžio perėjimo reikšmė:

Medžių perėjimas reiškia apsilankymo arba prieigos prie kiekvieno medžio mazgo procesą tiksliai vieną kartą tam tikra tvarka. Medžio apėjimo algoritmai padeda mums aplankyti ir apdoroti visus medžio mazgus. Kadangi medis nėra linijinė duomenų struktūra, yra keli mazgai, kuriuos galime aplankyti apsilankę tam tikrame mazge. Egzistuoja keli medžio perėjimo būdai, kurie nusprendžia, kokia tvarka turi būti lankomi medžio mazgai.

Medžio apvažiavimo būdai:



Medžio duomenų struktūrą galima pereiti šiais būdais:

  • Pirmoji gilumo paieška arba DFS
    • Inorder Traversal
    • Išankstinis užsakymas „Traversal“.
    • Pašto užsakymų pervežimas
  • „Level Order Traversal“ arba „Breadth First Search“ arba BFS

Inorder Traversal :

Inorder traveral aplanko mazgą tokia tvarka: Kairė -> Šaknis -> Dešinė




Inorder Traversal algoritmas:

Tvarka (medis)

  • Pereikite kairįjį pomedį, t. y. iškvieskite Inorder(left-> submede)
  • Aplankykite šaknį.
  • Pereikite dešinįjį pomedį, t. y. iškvieskite Inorder (dešinė-> pomedis)

„Inorder Traversal“ naudojimas:

  • Dvejetainių paieškos medžių (BST) atveju Inorder traversal pateikia mazgus nemažėjančia tvarka.
  • Norint gauti BST mazgus ne didėjančia tvarka, galima naudoti Inorder traversal variantą, kai Inorder traversal yra atvirkštinė.
  • Inorder traversal gali būti naudojamas vertinant aritmetines išraiškas, saugomas išraiškų medžiuose.

Inorder Traversal kodo fragmentas:

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->kairėje);  // Tada išspausdinkite mazgo cout duomenis<< node->duomenis<< ' ';  // Now recur on right child  printInorder(node->teisė); }>
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->kairėje);  // Tada atspausdinkite mazgo duomenis printf('%d ', node->data);  // Dabar kartojasi dešinėje antrinėje pusėje 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); }>
Išvestis 
Inorder traversal of binary tree is 4 2 5 1 3>

Laiko sudėtingumas: O(N)
Pagalbinė erdvė: Jei neatsižvelgsime į funkcijų iškvietimų krūvos dydį, tada O (1), kitaip O (h), kur h yra medžio aukštis.

Išankstinis užsakymas „Traversal“. :

Išankstinis užsakymas aplanko mazgą tokia tvarka: Šaknis -> Kairė -> Dešinė

Išankstinio užsakymo judėjimo algoritmas:

Išankstinis užsakymas (medis)

k artimiausio kaimyno algoritmas
  • Aplankykite šaknį.
  • Pereikite kairįjį pomedį, t. y. iškvieskite išankstinį užsakymą (left-> submede)
  • Pereikite dešinįjį pomedį, t. y. iškvieskite Preorder(right-> submede)

Išankstinio užsakymo perėjimo naudojimas:

  • Išankstinis užsakymas naudojamas medžio kopijai sukurti.
  • Išankstinis užsakymas taip pat naudojamas norint gauti priešdėlio išraiškas išraiškų medyje.

Išankstinio užsakymo kodo fragmentas:

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->duomenis<< ' ';  // Then recur on left subtree  printPreorder(node->kairėje);  // Dabar pasikartokite dešiniajame pomedyje 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->duomenys);  // Tada pasikartokite kairiajame pomedyje printPreorder(node->left);  // Dabar pasikartokite dešiniajame pomedyje 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); }>
Išvestis 
Preorder traversal of binary tree is 1 2 4 5 3>

Laiko sudėtingumas: O(N)
Pagalbinė erdvė: Jei neatsižvelgsime į funkcijų iškvietimų krūvos dydį, tada O (1), kitaip O (h), kur h yra medžio aukštis.

Pašto užsakymų pervežimas :

Postorder perėjimas aplanko mazgą tokia tvarka: Kairė -> Dešinė -> Šaknis

Postorder Traversal algoritmas:

Algoritmas Pašto orderis (medis)

  • Pereikite kairįjį pomedį, t. y. iškvieskite Postorder(left-> submede)
  • Pereikite dešinįjį pomedį, t. y. iškvieskite Postorder (dešinė-> pomedis)
  • Aplankykite šaknį

Mailorder Traversal naudojimo būdai:

  • Postorder traversal naudojamas medžiui ištrinti. Matyti klausimas dėl medžio ištrynimo dėl detalių.
  • Postorder traversal taip pat naudinga norint gauti išraiškos medžio postfikso išraišką.
  • Postorder perkėlimas gali padėti šiukšlių surinkimo algoritmuose, ypač sistemose, kuriose naudojamas rankinis atminties valdymas.

Mailorder Traversal kodo fragmentas:

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->kairėje);  // Tada pasikartokite dešiniajame pomedyje printPostorder(mazgas->dešinė);  // Dabar susidorokite su mazgo cout<< node->duomenis<< ' '; }>
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->kairėje);  // Tada pasikartokite dešiniajame pomedyje printPostorder(mazgas->dešinė);  // Dabar susitvarkykite su mazgu 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 + ' '); }>
Išvestis 
Postorder traversal of binary tree is 4 5 2 3 1>

Lygio tvarka :

Lygio tvarka visiškai aplanko visus mazgus, esančius tame pačiame lygyje, prieš apsilankydami kitame lygyje.

iškviesti js funkciją iš html

Lygio užsakymo apėjimo algoritmas:

Lygio tvarka (medis)

  • Sukurkite tuščią eilę Q
  • Įveskite medžio šaknies mazgą į Q
  • Ciklas, kol Q nėra tuščias
    • Nuimkite mazgą iš Q ir apsilankykite jame
    • Įtraukite į eilę kairįjį pašalinto mazgo antrinį elementą, jei toks yra
    • Į eilę įtraukite į eilę pašalinto mazgo dešinįjį antrinį elementą, jei toks yra

Lygių tvarkos naudojimas:

  • „Level Order Traversal“ dažniausiai naudojama kaip „Breadth First Search“ ieškant arba apdoroti mazgų pagal lygį.
  • Lygio užsakymo perėjimas taip pat naudojamas Medžių serializavimas ir deserializavimas .

Lygio užsakymo peržiūros kodo fragmentas:

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;  // Eilės šaknis ir inicijavimo aukštis q.push(root);  while (q.empty() == false) { // Spausdinti eilės priekį ir pašalinti jį iš eilės Node* node = q.front();  cout<< node->duomenis<< ' ';  q.pop();  // Enqueue left child  if (node->left != NULL) q.push(mazgas->left);  // Eilės dešinysis vaikas if (mazgas->dešinė != NULL) q.push(mazgas->dešinė);  } }>>Cduomenys);  // Eilės kairysis vaikas if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Eilės dešinysis vaikas if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Ištraukite mazgą į eilę ir padarykite jį temp_node temp_node = deQueue(queue, &front);  } }>>Java
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): # Spausdinkite eilės priekį ir # pašalinkite ją iš eilės print(queue[0].data, end=' ') node = queue.pop(0) # Eilės kairėje pusėje, jei node.left nėra Nėra: queue.append(node.left) # Į eilę į dešinę antrinę eilę, jei node.right nėra Nėra: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queueeilė = nauja eilė();  eilė.Enqueue(root);  while (eilė.Skaičius != 0) { Mazgas tempMazgas = eilė.Dequeue();  Console.Write(tempNode.data + ' ');  // Eilės kairysis vaikas if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Eilės dešinysis antrinis 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);  }  } }>

Kiti medžių apvažiavimai:

  1. Ribų perėjimas
  2. Įstrižainė

1. Ribų perėjimas :

Ribų perėjimas iš medžio apima:

  • kairioji riba (mazgai kairėje, išskyrus lapų mazgus)
  • lapai (sudaryta tik iš lapų mazgų)
  • dešinė riba (mazgai dešinėje, išskyrus lapų mazgus)

Ribų perėjimo algoritmas:

BoundaryTraversal (medis)

  • Jei šaknis nėra nulis:
    • Spausdinkite šaknies duomenis
    • SpausdintiLeftBoundary(root->left) // Spausdinti kairiuosius kraštinius mazgus
    • PrintLeafNodes(root->left) // Spausdinti kairiojo pomedžio lapų mazgus
    • Spausdinti lapų mazgus(root->right) // Spausdinti dešiniojo pomedžio lapų mazgus
    • PrintRightBoundary(root->right) // Spausdinkite dešiniuosius kraštinius mazgus

Ribų perėjimo naudojimas:

  • Ribų perėjimas padeda vizualizuoti išorinę dvejetainio medžio struktūrą, suteikdama įžvalgų apie jo formą ir ribas.
  • Ribų perėjimas suteikia galimybę pasiekti ir modifikuoti šiuos mazgus, įgalinant tokias operacijas kaip ribinių mazgų genėjimas arba perkėlimas.

2. Įstrižainė

Medžio įstrižainėje visi mazgai vienoje įstrižainėje bus spausdinami po vieną.

Įstrižainės praėjimo algoritmas:

DiagonalTraversal (medis):

  • Jei šaknis nėra nulis:
    • Sukurkite tuščią žemėlapį
    • DiagonalTraversalUtil(root, 0, M) // Iškvieskite pagalbinę funkciją su pradiniu įstrižainės lygiu 0
    • Kiekvienai rakto ir verčių porai (diagonalLevel, mazgai) M:
      • Kiekvienam mazgui mazguose:
      • Spausdinti mazgo duomenis

DiagonalTraversalUtil(mazgas, diagonalLevel, M):

  • Jei mazgas yra nulinis:
  • Grįžti
  • Jei diagonalLevel nėra M:
    • Sukurkite naują sąrašą M, skirtą diagonalLevel
  • Pridėti mazgo duomenis prie sąrašo M[diagonalLevel]
  • DiagonalTraversalUtil(mazgas->left, diagonalLevel + 1, M) // Eiti kairįjį vaiką su padidintu įstrižainės lygiu
  • DiagonalTraversalUtil(mazgas->dešinėn, įstrižainės lygis, M) // Eiti į dešinę antrinę dalį su tuo pačiu įstrižainės lygiu

Įstrižainės pravažiavimo naudojimas:

  • Įstrižainė padeda vizualizuoti dvejetainių medžių hierarchinę struktūrą, ypač medžių duomenų struktūrose, tokiose kaip dvejetainiai paieškos medžiai (BST) ir krūvos medžiai.
  • Įstrižainė gali būti naudojama apskaičiuojant kelio sumas išilgai įstrižainių dvejetainiame medyje.

Dažnai užduodami klausimai (DUK) apie medžio apėjimo metodus:

1. Kokie yra medžių kirtimo būdai?

Medžio perėjimo metodai yra metodai, naudojami aplankyti ir apdoroti visus medžio duomenų struktūros mazgus. Jie leidžia sistemingai pasiekti kiekvieną mazgą tiksliai vieną kartą.

2. Kokie yra įprasti medžių kirtimo tipai?

Įprasti medžių perėjimo tipai yra šie: perėjimas į eilę, išankstinis užsakymas, apvažiavimas po užsakymo, eilinis lygis (paieška pagal plotį)

bash patikrinkite, ar nustatytas aplinkos kintamasis

3. Kas yra Inorder traversal?

Inorder traversal – tai giluminio apėjimo metodas, kai mazgai lankomi tokia tvarka: kairysis pomedis, dabartinis mazgas, dešinysis pomedis.

4. Kas yra išankstinis užsakymas?

Išankstinio užsakymo perkėlimas yra giluminio apėjimo metodas, kai mazgai lankomi tokia tvarka: dabartinis mazgas, kairysis pomedis, dešinysis pomedis.

5. Kas yra pašto perlaidos pervežimas?

Postorder traversal – tai giluminio apėjimo metodas, kai mazgai lankomi tokia tvarka: kairysis pomedis, dešinysis pomedis, dabartinis mazgas.

6. Kas yra lygio užsakymo perėjimas?

Lygio eilės tvarka, taip pat žinoma kaip Breadth-First Search (BFS), aplanko mazgus lygiu pagal lygį, pradedant nuo šaknies ir pereinant į kitą lygį, o tada pereinant giliau.

7. Kada turėčiau naudoti kiekvieną perėjimo techniką?

Inorder traversal dažnai naudojamas dvejetainiams paieškos medžiams, kad mazgai būtų surūšiuoti.

Išankstinis užsakymas yra naudingas kuriant medžio kopiją.

Postorder traversal paprastai naudojamas išraiškų medžiuose, siekiant įvertinti išraiškas.

Lygio tvarkos perėjimas yra naudingas ieškant trumpiausio kelio tarp mazgų.

8. Kaip įdiegti medžio apėjimo algoritmus?

Medžio apėjimo algoritmai gali būti įgyvendinami rekursyviai arba iteratyviai, priklausomai nuo konkrečių reikalavimų ir naudojamos programavimo kalbos.

9. Ar medžių perėjimo algoritmus galima pritaikyti kitoms į medį panašioms struktūroms?

Taip, medžių perėjimo algoritmai gali būti pritaikyti kirsti kitas į medžius panašias struktūras, tokias kaip dvejetainiai krūvos, n-ariniai medžiai ir grafikai, vaizduojami kaip medžiai.

10. Ar renkantis perėjimo techniką atsižvelgiama į efektyvumą?

Našumo aspektai priklauso nuo tokių veiksnių, kaip medžio dydis ir forma, turima atmintis ir konkrečios operacijos, atliekamos važiuojant. Apskritai, perėjimo technikos pasirinkimas gali turėti įtakos tam tikrų operacijų efektyvumui, todėl svarbu pasirinkti tinkamiausią būdą konkrečiam naudojimo atvejui.

Kai kurios kitos svarbios pamokos:

  • DSA mokymo programa
  • Sistemos projektavimo pamoka
  • Programinės įrangos kūrimo planas
  • Planas tapti produktų vadovu
  • Išmokite SAP
  • Išmok SEO