Puun kulku

Tässä opetusohjelmassa opit erilaisista puiden kulkutekniikoista. Löydät myös toimivia esimerkkejä erilaisista puiden kulkumenetelmistä C, C ++, Java ja Python.

Puun läpi kulkeminen tarkoittaa vierailua puun jokaisessa solmussa. Saatat esimerkiksi haluta lisätä kaikki arvot puuhun tai löytää suurimman. Kaikissa näissä toiminnoissa sinun on käytävä puun jokaisessa solmussa.

Lineaarisilla tietorakenteilla, kuten matriiseilla, pinoilla, jonoilla ja linkitetyllä luettelolla, on vain yksi tapa lukea tietoja. Puun kaltaista hierarkkista tietorakennetta voidaan kuitenkin kulkea eri tavoin.

Puun kulku

Mietitään, miten voimme lukea puun elementit yllä olevassa kuvassa.

Alkaen ylhäältä, vasemmalta oikealle

 1 -> 12 -> 5 -> 6 -> 9

Alkaen alhaalta, vasemmalta oikealle

 5 -> 6 -> 12 -> 9 -> 1

Vaikka tämä prosessi on melko helppo, se ei kunnioita puun hierarkiaa, vain solmujen syvyyttä.

Sen sijaan käytämme kulkumenetelmiä, joissa otetaan huomioon puun perusrakenne eli

 struct node ( int data; struct node* left; struct node* right; )

Vasemmalla ja oikealla osoittavalla rakenteellisella solmulla voi olla muita vasemman- ja oikeanpuoleisia lapsia, joten meidän pitäisi ajatella heitä alipuina alisolmujen sijaan.

Tämän rakenteen mukaan jokainen puu on yhdistelmä

  • Solmu, joka kuljettaa tietoja
  • Kaksi alipuuta
Vasen ja oikea alipuu

Muista, että tavoitteemme on käydä jokaisessa solmussa, joten meidän on käytävä käymään kaikissa alipuun solmuissa, käymään juurisolmussa ja myös kaikkien oikean alipuun solmuissa.

Siitä riippuen, missä järjestyksessä tämä tapahtuu, kulkemista voi olla kolmenlaisia.

Tilausliikenne

  1. Käy ensin kaikissa vasemman alipuun solmuissa
  2. Sitten juurisolmu
  3. Käy kaikissa oikean alipuun solmuissa
 inorder(root->left) display(root->data) inorder(root->right)

Ennakkotilaa kulku

  1. Käy juurisolmussa
  2. Käy kaikissa vasemman alipuun solmuissa
  3. Käy kaikissa oikean alipuun solmuissa
 display(root->data) preorder(root->left) preorder(root->right)

Postorderin läpikulku

  1. Käy kaikissa vasemman alipuun solmuissa
  2. Käy kaikissa oikean alipuun solmuissa
  3. Käy juurisolmussa
 postorder(root->left) postorder(root->right) display(root->data)

Visualisoidaan järjestyksessä kulkua. Aloitamme juurisolmusta.

Vasen ja oikea alipuu

Ohitamme ensin vasemman osapuun. Meidän on myös muistettava käydä juurisolmussa ja oikeassa alipuussa, kun tämä puu on tehty.

Laitetaan kaikki tämä pinoon niin, että muistamme.

Pino

Nyt siirrymme pinon huipulle osoittamaan osapuuhun.

Jälleen kerran noudatamme samaa sääntöä

 Vasen alipuu -> juuri -> oikea alipuu

Vasemman alipuun läpi kulkemisen jälkeen meille jää jäljelle

Viimeinen pino

Koska solmussa "5" ei ole alipuuta, tulostamme sen suoraan. Sen jälkeen tulostamme sen vanhemman "12" ja sitten oikean lapsen "6".

Kaiken sijoittaminen pinoon oli hyödyllistä, koska nyt kun juurisolmun vasen alipuu on ylitetty, voimme tulostaa sen ja siirtyä oikeaan alipuun.

Kun olemme käyneet läpi kaikki elementit, saamme sisäisen läpikulun

 5 -> 12 -> 6 -> 1 -> 9

Meidän ei tarvitse luoda pinoa itse, koska rekursio ylläpitää oikeaa järjestystä meille.

Python-, Java- ja C / C ++ -esimerkkejä

Python Java C C + 
 # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
 // Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
 // Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
 // Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);

Mielenkiintoisia artikkeleita...