Puu läbimine

Selles õpetuses saate teada erinevate puude läbimise tehnikate kohta. Samuti leiate toimivaid näiteid erinevatest puude läbimise meetoditest C, C ++, Java ja Python.

Puu läbimine tähendab iga puu sõlme külastamist. Näiteks võiksite lisada puule kõik väärtused või leida suurima. Kõigi nende toimingute jaoks peate külastama puu kõiki sõlme.

Lineaarsetel andmestruktuuridel, nagu massiivid, korstnad, järjekorrad ja lingitud loend, on andmete lugemiseks ainult üks viis. Kuid hierarhilist andmestruktuuri nagu puu saab läbida erineval viisil.

Puu läbimine

Mõelgem sellele, kuidas saaksime ülaltoodud pildil puu elemente lugeda.

Alustades ülevalt, vasakult paremale

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

Alustades alt vasakult paremale

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

Kuigi see protsess on mõnevõrra lihtne, ei austa see puu hierarhiat, vaid ainult sõlmede sügavust.

Selle asemel kasutame läbimismeetodeid, mis võtavad arvesse puu põhistruktuuri st

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

Vasakul ja paremal osutataval struktursõlmel võib olla ka teisi vasak- ja parempoolseid lapsi, nii et me peaksime neist mõtlema kui alamsõlmede asemel alampuud.

Selle struktuuri järgi on iga puu kombinatsioon

  • Andmeid kandev sõlm
  • Kaks alampuud
Vasak ja parem alampuu

Pidage meeles, et meie eesmärk on külastada iga sõlme, seega peame külastama kõiki alampuu sõlme, külastama juursõlme ja külastama ka kõiki parempoolse alampuu sõlme.

Sõltuvalt sellest, millises järjekorras seda teeme, võib läbimist olla kolme tüüpi.

Tellimuse läbimine

  1. Kõigepealt külastage kõiki vasaku alampuu sõlme
  2. Siis juursõlm
  3. Külastage kõiki parempoolse alampuu sõlme
 inorder(root->left) display(root->data) inorder(root->right)

Ettetellimine läbimine

  1. Külastage juursõlme
  2. Külastage kõiki vasaku alampuu sõlme
  3. Külastage kõiki parempoolse alampuu sõlme
 display(root->data) preorder(root->left) preorder(root->right)

Postitellimuse läbimine

  1. Külastage kõiki vasaku alampuu sõlme
  2. Külastage kõiki parempoolse alampuu sõlme
  3. Külastage juursõlme
 postorder(root->left) postorder(root->right) display(root->data)

Kujutleme järjekorras läbimist. Alustame juursõlmest.

Vasak ja parem alampuu

Kõigepealt läbime vasaku alampuu. Samuti peame meeles pidama, et külastame juurte sõlme ja õiget alampuid, kui see puu on tehtud.

Paneme kõik selle virna, nii et mäletame.

Virn

Nüüd läbime virna ülaosale suunatud alampuu.

Jällegi järgime sama sisekorra reeglit

 Vasak alampuu -> juur -> parem alampuu

Pärast vasaku alampuu läbimist jääb meile järele

Viimane virn

Kuna sõlmel "5" pole alampuid, printime selle otse. Pärast seda printime selle vanema "12" ja seejärel õige lapse "6".

Kõigi virna panek oli kasulik, sest nüüd, kui juursõlme vasak-alampuu on läbitud, saame selle printida ja minna paremale alampuule.

Pärast kõigi elementide läbimist saame sisemise läbipääsu as

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

Me ei pea virna ise looma, sest rekursioon säilitab meie jaoks õige järjekorra.

Pythoni, Java ja C / C ++ näited

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);

Huvitavad Artiklid...