Puun läpikulku (järjestys, ennakkotilaus ja jälkitilaus) esimerkkeineen

by: Sarah Chen Sarah Chen
Hours Päivitetty

Mikä on Tree Traversal?

Puutietorakenteessa läpikulku tarkoittaa solmuissa vierailemista jollakin tietyllä tavalla. Nodes2-tyyppisiä läpikulkuja on olemassa. Yleensä tällainen läpikulku perustuu binääripuuhun. Binääripuu tarkoittaa, että jokaisessa solmussa voi olla enintään 2 solmua.

Binääripuu on hyvin tunnettu tietorakenne. Siellä on myös binaarihakupuu (BST). Tämän tyyppistä läpikulkua käytetään useisiin tarkoituksiin. Tasojärjestyksen läpikulku, sitä käytetään kahden solmun välisen syvyyden laskemiseen. On olemassa toisenlainen puu nimeltä "AVL", jossa solmun korkeuden laskeminen on välttämätöntä. Voimme edustaa taulukossa binaaripuuta, mutta muistin optimoinnissa käytämme rakennetta ja osoitinta viittaamaan seuraavaan solmuun.

Puun läpikulkutyypit

Kuten keskustelimme binääripuut, nyt keskustelemme yksittäisistä läpikulkutyypeistä. Tyypistä riippuen on olemassa kahta tyyppiä läpikulkua. Aiemmin olemme maininneet tasojärjestyksen tai Breadth-First Traversalin välttämättömyyden. Nyt Syvyys-ensimmäinen läpikulku kuten jälkitilausta käytetään solmun poistamiseen (käsittelemme sitä myöhemmin), ennakkotilausta käytetään binaaripuun kopioimiseen, ja "inorder" kulkee puun läpi ei-laskevalla tavalla.

  • Leveys - ensimmäinen läpikulku
  • Syvyys-ensimmäinen läpikulku
  • Ennakkotilaa läpikulku
  • Tilauksen jälkeinen läpikulku
  • Määräysten mukainen kulku

Leveys - ensimmäinen läpikulku

Se tunnetaan myös tasojärjestyksen läpikulkuna. Tarkastellaan seuraavaa puuta tasojärjestyksen läpikulun havainnollistamiseksi.

Leveys - ensimmäinen läpikulku

Joten aloitamme juurisolmusta "1". Se merkitään tasoksi 1. Sitten algoritmi menee kaikille nykyisen solmun lapsille. Vierailemme nyt solmuissa 2 ja 3. Ne merkitään tasoiksi 2.

Sen jälkeen, koska meillä on 2 solmua tasolla 2, vierailemme myös heidän lastensa luona. Joten käymme 5,6,8,7, 3, XNUMX, XNUMX ja merkitsemme ne tasoksi XNUMX. Tässä on asia, jota ei mainita,

Solmun taso = pääsolmun taso + 1

Taso 1: 1

Taso 2: 2 3

Taso 3: 5 6 8 7

Samanlaista algoritmia käytetään BFS:lle (Breadth-First-Search).

Tässä on pseudokoodi tasotilauksen läpikulkua varten:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Inorder Traversal Bianry Tree

Otetaan sama esimerkki kuin aiemmin. Tämän tyyppisessä läpikäymisessä käymme ensin vasemmassa alipuussa, sitten juuressa ja sen jälkeen oikeanpuoleisessa alipuussa. Muistamisen helpottamiseksi voimme sanoa, että järjestys menee kuten vasen-juuri-oikea.

Inorder Traversal Bianry Tree

Oletetaan, että koko puun juuri on 1. Nyt algoritmi seuraa:

  • Käy solmun 1 vasemmassa alipuussa.
  • Nykyinen solmu on 2 (koska se on 1:n vasen alipuu)

Inorder Traversal Bianry Tree

  • Vieraile 2:n vasemmassa alipuussa. Nykyinen solmu on tällä kertaa 5.
  • Siirretään kohtaan 5, sillä ei ole lapsia, joten solmu 5 merkitään vierailluksi. Se palaa pääsolmuun; joka on 2.
  • Koska 2:n vasemmassa alipuussa vieraillaan, nyt käydään myös 2:ssa.
  • - algoritmi siirtää nykyisen solmun solmun 2 oikeaan alipuuhun, joka on solmu 6. Vierailun jälkeen solmussa 6. Se siirtyy pääsolmuun 2.
  • Koska solmussa 2 käydään, vierailemme nyt 2:n vanhemmassa; joka on solmu 1.
  • Sen jälkeen vierailemme oikealla alipuulla.

Joten lopullinen läpikulku näyttää tältä:

Järjestys: 5 → 2 → 6 → 1 → 8 → 3 → 7

Tässä on Pseudokoodi tilauksen läpikäymiselle:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Tämä on rekursiivinen algoritmi järjestyksen läpikäymiselle. Varten Binäärihakupuu (BST), Inorder traversal antaa järjestetyn arvojen joukon.

AIHEESEEN LIITTYVÄT ARTIKKELIT

Tilauksen jälkeinen läpikäynti

Tässä läpikäymisessä kuljemme ensin vasemmanpuoleisen alipuun poikki ja sitten juuren jälkeen oikeanpuoleisen alipuun. Kaikki matkat ovat jälkitilauksena. Esitetään esimerkki:

Tilauksen jälkeinen läpikäynti

Tässä juuri = 1,

  • Siirrymme ensin vasempaan alipuuhun. Joten juuresta tulee 2.
  • Sitten 2 on jättänyt alipuun, joten siirrymme solmuun 5. Nyt juuri on 5.
  • Sillä ei ole vasenta alipuuta, eikä sillä ole myöskään oikeaa alipuuta. Joten nyt merkitsemme solmun 5 vierailluksi ja siirrymme sen pääsolmuun.

Tilauksen jälkeinen läpikäynti

  • Nyt juuri on 2 ja sen vasemmassa alipuussa on käyty kokonaan. Siirrymme nyt sen oikeaan alipuuhun. Joten juuresta tulee 6.
  • Koska solmussa 6 ei ole vasenta ja oikeaa alipuuta, merkitsemme solmun 6 vierailluksi ja siirrymme sen pääsolmuun 2.
  • Nyt sekä vasemmalla että oikealla alipuulla käydään solmun 2 kohdalla. Myös se merkitään käydyksi.
  • Siirrymme solmun 2 yläpäähän, joka on solmu 1.
  • Vasemmassa alipuussa käydään juuri 1. Nyt käymme samalla tavalla oikeanpuoleisessa alipuussa.

Tilauksen jälkeinen läpikäynti

Merkitty ympyrä on oikea alipuu. Nyt vierailemme oikeanpuoleisessa alipuussa, kuten vierailimme vasemmassa alipuussa. Sen jälkeen vierailemme solmussa. Lopullinen läpikulku on siis:

Jälkitilaus: 5 → 6 → 2 → 8 → 7 → 3 → 1

Tässä on pseudokoodi tilauksen jälkeiseen läpikäyntiin:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Ennakkotilaa kulku

Ennakkotilauksen läpikäymisessä algoritmi vierailee ensin juurisolmussa, jonka jälkeen se siirtyy vasempaan ja oikeaan alipuuhun. Ymmärtämisen helpottamiseksi voimme ajatella ennakkotilauskäyntejä, kuten juuri → vasen-oikea.

Ennakkotilaa kulku

Joten valitaan solmu 1 juureksi.

  • Algoritmin mukaan juuri löydetään ensin, sitten vasen ja sitten oikea alipuu.
  • Joten käymme juuri 1:ssä. Sitten siirrymme sen vasempaan alipuuhun. Juureksi tulee 2.
  • Vierailemme solmussa 2 ja siirrymme sen vasempaan alipuuhun. Joten juuresta tulee 3.
  • Vierailemme solmussa 3, sitten siirrymme sen pääsolmuun. Nyt käydään solmussa 2 ja sen vasemmassa alipuussa. Aika käydä oikealla alipuulla.
  • Siirrymme oikeaan alipuuhun, juureksi tulee 4. Vierailemme kohdassa 4. Koska 4:llä ei ole alisolmua, siirrymme sen yläpuolelle.
  • Nyt juuri on 2 ja siinä käydään yhdessä sen vasemman ja oikean alipuun kanssa. Joten siirrymme sen pääsolmuun. Nyt juuresta tulee 1.
  • Samalla tavalla käymme oikeanpuoleisessa alipuussa.

Ennakkotilaus: 1 → 2 → 3 → 4 → 5 → 6 → 7

Tässä on pseudokoodi tilauksen jälkeiseen läpikäyntiin:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Toteutus sisään Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

lähtö: 

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Toteutus C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

Lähtö:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

Toteutus C++ (Käytetään std:queue-tasojärjestystä)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1