Trädgenomgång

I den här handledningen lär du dig om olika tekniker för trädgenomgång. Du hittar också arbetsexempel på olika trädgenomgångsmetoder i C, C ++, Java och Python.

Att korsa ett träd innebär att besöka varje nod i trädet. Du kanske till exempel vill lägga till alla värden i trädet eller hitta det största. För alla dessa operationer måste du besöka varje nod i trädet.

Linjära datastrukturer som matriser, staplar, köer och länkad lista har bara ett sätt att läsa informationen. Men en hierarkisk datastruktur som ett träd kan passeras på olika sätt.

Trädkorsning

Låt oss tänka på hur vi kan läsa trädets element i bilden som visas ovan.

Från början, vänster till höger

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

Börjar från botten, vänster till höger

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

Även om denna process är något lätt, respekterar den inte trädets hierarki, bara djupet på noderna.

Istället använder vi korsningsmetoder som tar hänsyn till ett träds grundstruktur, dvs.

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

Strukturnoden som vänster och höger pekar på kan ha andra vänster- och högerbarn så vi bör tänka på dem som underträd istället för undernoder.

Enligt denna struktur är varje träd en kombination av

  • En nod som bär data
  • Två underträd
Vänster och höger subtree

Kom ihåg att vårt mål är att besöka varje nod, så vi måste besöka alla noder i underträdet, besöka rotnoden och besöka alla noder i rätt underträd också.

Beroende på i vilken ordning vi gör detta kan det finnas tre typer av traversal.

Inorder traversal

  1. Besök först alla noder i vänster underträd
  2. Sedan rotnoden
  3. Besök alla noder i rätt underträd
 inorder(root->left) display(root->data) inorder(root->right)

Förbeställ traversal

  1. Besök rotnoden
  2. Besök alla noder i det vänstra underträdet
  3. Besök alla noder i rätt underträd
 display(root->data) preorder(root->left) preorder(root->right)

Postorder traversal

  1. Besök alla noder i det vänstra underträdet
  2. Besök alla noder i rätt underträd
  3. Besök rotnoden
 postorder(root->left) postorder(root->right) display(root->data)

Låt oss visualisera in-order traversal. Vi börjar från rotnoden.

Vänster och höger subtree

Vi korsar vänster subtree först. Vi måste också komma ihåg att besöka rotnoden och rätt underträd när detta träd är klart.

Låt oss lägga allt detta i en stapel så att vi kommer ihåg det.

Stack

Nu korsar vi till underträdet som pekas på STAPPENS ÖVERST.

Återigen följer vi samma regel för ordning

 Vänster underträd -> rot -> höger underträd

Efter att ha gått igenom vänster subtree sitter vi kvar med

Sista stacken

Eftersom noden "5" inte har några underträd skriver vi ut den direkt. Därefter skriver vi ut sin förälder "12" och sedan rätt barn "6".

Att lägga allt på en stack var till hjälp eftersom nu när rotnodens vänstra underträd har passerat kan vi skriva ut det och gå till rätt underträd.

Efter att ha gått igenom alla element, får vi inorder traversal som

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

Vi behöver inte skapa stacken själva eftersom rekursion håller rätt ordning för oss.

Python, Java och C / C ++ exempel

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

Intressanta artiklar...