Puun läpikulkutekniikat sisältää erilaisia ​​tapoja käydä puun kaikissa solmuissa. Toisin kuin lineaarisissa tietorakenteissa (Array, Linked List, Queues, Stacks jne.), joilla on vain yksi looginen tapa kulkea ne, puita voidaan kulkea eri tavoin. Tässä artikkelissa keskustelemme kaikista puiden läpikulkutekniikoista ja niiden käytöstä.

Sisällysluettelo

• Puun kulkemisen merkitys
• Puun läpikulkutekniikat
• Inorder Traversal
• Ennakkotilaa Traversal
• Postimääräyksen läpikulku
• Tasojärjestyksen läpikäynti
• Muut puun läpikäymiset
• Usein kysytyt kysymykset (FAQ) Tree Traversal Techniques

Puun kulkemisen merkitys:

Puun läpikulku viittaa prosessiin, jossa käydään puun jokaisessa solmussa täsmälleen kerran tietyssä järjestyksessä. Puun läpikulkualgoritmit auttavat meitä vierailemaan ja käsittelemään puun kaikkia solmuja. Koska puu ei ole lineaarinen tietorakenne, on olemassa useita solmuja, joissa voimme vierailla tietyssä solmussa käymisen jälkeen. On olemassa useita puun läpikulkutekniikoita, jotka päättävät järjestyksen, jossa puun solmuissa käydään.

Puun läpikulkutekniikat:

Puutietorakennetta voidaan kulkea seuraavilla tavoilla:

• Syvyys ensimmäinen haku tai DFS
  • Inorder Traversal
  • Ennakkotilaa Traversal
  • Postimääräyksen läpikulku
• Level Order Traversal tai Breadth First Search tai BFS

Inorder Traversal :

Inorder Traversal vierailee solmussa järjestyksessä: Vasen -> Juuri -> Oikea

Inorder Traversal -algoritmi:

Järjestys (puu)

• Kävele vasemman alipuun läpi, eli kutsu Inorder(vasen->alipuu)
• Vieraile juurella.
• Kulje oikeanpuoleisen alipuun läpi, eli kutsu Inorder(oikea->alipuu)

Inorder Traversalin käyttötarkoitukset:

• Binäärihakupuiden (BST) tapauksessa Inorder traversal antaa solmut ei-laskevassa järjestyksessä.
• Jos haluat saada BST:n solmut ei-nousevassa järjestyksessä, voidaan käyttää Inorder-läpikulkujen muunnelmaa, jossa Inorder-läpikulku on käänteinen.
• Inorder-läpikulkua voidaan käyttää lausekepuihin tallennettujen aritmeettisten lausekkeiden arvioimiseen.

Koodikatkelma järjestyksen läpikulkua varten:

// 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->vasen);  // Tulosta sitten solmun cout tiedot<< node->tiedot<< ' ';  // Now recur on right child  printInorder(node->oikea); }>

// 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->vasen);  // Tulosta sitten solmun tiedot printf('%d ', node->data);  // Nyt toistaa oikealla alikirjoituksella Inorder(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>

Aika monimutkaisuus: PÄÄLLÄ)
Aputila: Jos emme ota huomioon pinon kokoa funktiokutsuille, niin O(1) muuten O(h), missä h on puun korkeus.

Ennakkotilaa Traversal :

Ennakkotilauksen läpikulku vierailee solmussa seuraavassa järjestyksessä: Juuri -> Vasen -> Oikea

Ennakkotilauksen läpikäymisen algoritmi:

Ennakkotilaus (puu)

• Vieraile juurella.
• Kävele vasemman alipuun läpi, eli kutsu Preorder(vasen->alipuu)
• Kulje oikeanpuoleisen alipuun läpi, eli kutsu Preorder(oikea->alipuu)

Ennakkotilauksen läpikäymisen käyttötavat:

• Ennakkotilauksen läpikulkua käytetään puun kopion luomiseen.
• Ennakkotilauksen läpikulkua käytetään myös etuliitelausekkeiden saamiseksi lausekepuuhun.

Koodikatkelma ennakkotilauksen läpikäymistä varten:

// 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->tiedot<< ' ';  // Then recur on left subtree  printPreorder(node->vasen);  // Toista nyt oikealla alipuulla 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->tiedot);  // Toista sitten vasemmassa alipuussa printPreorder(node->left);  // Toista nyt oikealla alipuulla 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>

Aika monimutkaisuus: PÄÄLLÄ)
Aputila: Jos emme ota huomioon pinon kokoa funktiokutsuille, niin O(1) muuten O(h), missä h on puun korkeus.

Postimääräyksen läpikulku :

Postorder Traversal vierailee solmussa järjestyksessä: Vasen -> Oikea -> juuri

Postorder Traversal -algoritmi:

Algoritmi Postimääräys (puu)

• Kävele vasemman alipuun läpi, eli kutsu Postorder(vasen->alipuu)
• Kulje oikeanpuoleisen alipuun läpi, eli kutsu Postorder(oikea->alipuu)
• Vieraile juurella

Mailorder Traversalin käyttötarkoitukset:

• Postorder-läpikulkua käytetään puun poistamiseen. Katso kysymys puun poistamisesta yksityiskohtia varten.
• Postorder-läpikulku on hyödyllinen myös lausekepuun postfix-lausekkeen saamiseksi.
• Postorder-läpikulku voi auttaa roskienkeräysalgoritmeissa, erityisesti järjestelmissä, joissa käytetään manuaalista muistinhallintaa.

Mailorder Traversalin koodikatkelma:

// 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->vasen);  // Toista sitten oikealla alipuulla printPostorder(solmu->oikea);  // Käsittele nyt node cout<< node->tiedot<< ' '; }>

// 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->vasen);  // Toista sitten oikealla alipuulla printPostorder(solmu->oikea);  // Käsittele nyt solmu printf('%d ', solmu->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>

Tasojärjestyksen läpikäynti :

Tasojärjestyksen läpikäynti vierailee kaikissa samalla tasolla olevissa solmuissa kokonaan ennen seuraavaa tasoa.

Algoritmi tasotilauksen läpikäymiselle:

Tasojärjestys (puu)

• Luo tyhjä jono Q
• Jonota puun juurisolmu kohtaan Q
• Silmukka kun Q ei ole tyhjä
  • Poista solmu Q:sta ja käy siinä
  • Lisää jonoon poistetun solmun vasen lapsi, jos se on olemassa
  • Jonoa poistetun solmun oikea ali, jos se on olemassa

Tasojärjestyksen käyttötavat:

negatiivinen diskreetti matematiikka

• Tasojärjestyksen läpikulkua käytetään pääasiassa Breadth First Searchina solmujen etsimiseen tai käsittelyyn tasoittain.
• Tasojärjestyksen läpikulkua käytetään myös Puun serialisointi ja deserialisointi .

Koodikatkelma tasotilauksen läpikulkua varten:

// 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;  // Lisää jonoon juuri ja alusta korkeus q.push(root);  while (q.empty() == false) { // Tulosta jonon etuosa ja poista se jonosta Node* node = q.front();  cout<< node->tiedot<< ' ';  q.pop();  // Enqueue left child  if (node->vasen != NULL) q.push(solmu->vasen);  // Jonoa oikea lapsi if (solmu->oikea != NULL) q.push(solmu->oikea);  } }>

// 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->tiedot);  // Jonoa vasen lapsi if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Jonota oikea lapsi if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Poista solmu jonosta ja tee siitä temp_node temp_node = deQueue(queue, &front);  } }>

// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuejono = uusi LinkedList();  queue.add(root);  while (!queue.isEmpty()) { // poll() poistaa nykyisen otsikon.  Solmun tempSolmu = queue.poll();  System.out.print(tempNode.data + ' ');  // Lisää jonoon vasen lapsi if (tempNode.left != null) { queue.add(tempNode.left);  } // Jonota oikea lapsi 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): # Tulosta jonon etuosa ja # poista se jonosta print(queue[0].data, end=' ') node = queue.pop(0) # Jonon vasen lapsi, jos node.left ei ole Ei mitään: queue.append(node.left) # Jonota oikea lapsi, jos node.right ei ole Ei mitään: queue.append(node.right)>

// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuejono = uusi jono();  jono.Enqueue(juuri);  while (jono.Laskuri != 0) { Solmu tempSolmu = jono.Dequeue();  Console.Write(tempNode.data + ' ');  // Jonoa vasen lapsi if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Jonota oikea lapsi 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);  }  } }>

Muut puiden läpikäymiset:

1. Rajan ylitys
2. Diagonaalinen läpikulku

1. Rajan ylitys :

Rajan ylitys Puu sisältää:

• vasen raja (vasemmalla olevat solmut eivät sisällä lehtien solmuja)
• lehdet (koostuvat vain lehtien solmuista)
• oikea raja (solmut oikealla lukuun ottamatta lehtien solmuja)

Algoritmi rajan ylittämistä varten:

BoundaryTraversal (puu)

• Jos root ei ole tyhjä:
  • Tulosta juuritiedot
  • PrintLeftBoundary(root->left) // Tulosta vasemmat rajasolmut
  • PrintLeafNodes(root->left) // Tulosta vasemman alipuun lehtisolmut
  • TulostaLehtisolmut(juuri->oikea) // Tulosta oikean alipuun lehtisolmut
  • PrintRightBoundary(root->right) // Tulosta oikeat rajasolmut

Rajan ylityksen käyttötarkoitukset:

• Rajojen läpikulku auttaa visualisoimaan binääripuun ulkorakenteen ja antaa näkemyksiä sen muodosta ja rajoista.
• Rajojen läpikulku tarjoaa tavan käyttää ja muokata näitä solmuja, mikä mahdollistaa toiminnot, kuten rajasolmujen karsimisen tai uudelleensijoituksen.

2. Diagonaalinen läpikulku

Puun lävistäjän läpikäymisessä kaikki yhden diagonaalin solmut tulostetaan yksitellen.

Algoritmi diagonaaliseen läpikulkuun:

DiagonalTraversal(puu):

• Jos root ei ole tyhjä:
  • Luo tyhjä kartta
  • DiagonalTraversalUtil(juuri, 0, M) // Kutsu aputoimintoa aloitusdiagonaalitasolla 0
  • Jokaiselle M:n avain-arvo-parille (diagonalLevel, solmut):
    • Jokaiselle solmulle solmuissa:
    • Tulosta solmun tiedot

DiagonalTraversalUtil(solmu, diagonaalitaso, M):

• Jos solmu on tyhjä:
• Palata
• Jos diagonalLevel ei ole M:ssä:
  • Luo uusi luettelo M:llä diagonalLevelille
• Liitä solmun tiedot luetteloon M[diagonalLevel]
• DiagonalTraversalUtil(solmu->vasen, diagonaalitaso + 1, M) // Siirrä vasen lapsi suurennetulla diagonaalitasolla
• DiagonalTraversalUtil(solmu->oikea, diagonaalitaso, M) // Siirrä oikea lapsi samalla diagonaalitasolla

Diagonaalisen läpimenon käyttötarkoitukset:

• Diagonaalinen läpikulku auttaa visualisoimaan binääripuiden hierarkkisen rakenteen, erityisesti puupohjaisissa tietorakenteissa, kuten binäärihakupuissa (BST) ja kasapuissa.
• Diagonaalista läpikulkua voidaan käyttää laskemaan polkusummat diagonaaleja pitkin binääripuussa.

Usein kysytyt kysymykset (FAQ) Tree Traversal -tekniikoista:

1. Mitä ovat puun läpikulkutekniikat?

Puun läpikulkutekniikat ovat menetelmiä, joita käytetään puutietorakenteen kaikissa solmuissa vierailemiseen ja käsittelemiseen. Niiden avulla voit käyttää jokaista solmua täsmälleen kerran systemaattisesti.

2. Mitkä ovat yleisimmät puiden läpikulkutyypit?

Yleisimmät puun läpikulkutyypit ovat: Inorder traversal, Preorder traversal, Postorder traversal, Level order traversal (leveys-ensimmäinen haku)

3. Mikä on Inorder-läpikulku?

Inorder traversal on syvyys-ensimmäinen läpikulkumenetelmä, jossa solmuissa käydään järjestyksessä: vasen alipuu, nykyinen solmu, oikea alipuu.

4. Mikä on ennakkotilaus?

Ennakkotilausläpikulku on syvyys-ensimmäinen läpikulkumenetelmä, jossa solmuissa käydään järjestyksessä: nykyinen solmu, vasen alipuu, oikea alipuu.

5. Mikä on postimääräysten läpikulku?

Postorder traversal on syvyys-ensimmäinen läpikulkumenetelmä, jossa solmuissa käydään järjestyksessä: vasen alipuu, oikea alipuu, nykyinen solmu.

6. Mikä on tasojärjestyksen läpikulku?

Tasojärjestyksen läpikulku, joka tunnetaan myös nimellä Breadth-First Search (BFS), vierailee solmuissa taso kerrallaan alkaen juuresta ja siirtyen seuraavalle tasolle ennen kuin kulkee syvemmälle.

7. Milloin minun tulee käyttää kutakin läpikulkutekniikkaa?

Inorder-läpikulkua käytetään usein binäärihakupuissa solmujen saamiseksi järjestykseen.

Ennakkotilauksen läpikulku on hyödyllinen puun kopion luomiseen.

Postorder-läpikulkua käytetään yleisesti lausekepuissa lausekkeiden arvioimiseen.

Tasojärjestyksen läpikulku auttaa löytämään lyhimmän polun solmujen välillä.

8. Kuinka toteutan puun läpikulkualgoritmit?

Puun läpikulkualgoritmit voidaan toteuttaa rekursiivisesti tai iteratiivisesti riippuen erityisvaatimuksista ja käytetystä ohjelmointikielestä.

9. Voidaanko puun läpikulkualgoritmeja soveltaa muihin puumaisiin rakenteisiin?

Kyllä, puun läpikulkualgoritmeja voidaan mukauttaa kulkemaan läpi muita puumaisia ​​rakenteita, kuten binäärikasoja, n-arvoisia puita ja puina esitettäviä kaavioita.

10. Otetaanko suorituskykyyn liittyviä näkökohtia valittaessa läpikulkutekniikkaa?

Suorituskykyä koskevat näkökohdat riippuvat tekijöistä, kuten puun koosta ja muodosta, käytettävissä olevasta muistista ja tietyistä läpikäynnin aikana suoritettavista toiminnoista. Yleisesti ottaen läpikulkutekniikan valinta voi vaikuttaa tiettyjen toimintojen tehokkuuteen, joten on tärkeää valita sopivin menetelmä omaan käyttötapaukseen.

Muita tärkeitä opetusohjelmia:

• DSA opetusohjelma
• Järjestelmäsuunnittelun opetusohjelma
• Ohjelmistokehityssuunnitelma
• Tiekartta tuotepäälliköksi
• Opi SAP
• Opi SEO