Tree Traversal

I denne opplæringen vil du lære om forskjellige tregjennomgangsteknikker. Du finner også arbeidseksempler på forskjellige metoder for treovergang i C, C ++, Java og Python.

Å krysse et tre betyr å besøke hver node i treet. Du kan for eksempel legge til alle verdiene i treet eller finne den største. For alle disse operasjonene må du besøke hver node i treet.

Lineære datastrukturer som matriser, stabler, køer og koblet liste har bare én måte å lese dataene på. Men en hierarkisk datastruktur som et tre kan krysses på forskjellige måter.

Tree traversal

La oss tenke på hvordan vi kan lese elementene i treet i bildet vist ovenfor.

Starter fra toppen, fra venstre til høyre

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

Starter fra bunnen, fra venstre til høyre

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

Selv om denne prosessen er noe enkel, respekterer den ikke treets hierarki, bare dybden av nodene.

I stedet bruker vi gjennomkjøringsmetoder som tar hensyn til grunnstrukturen til et tre, dvs.

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

Strukturenoden som venstre og høyre peker på, kan ha andre venstre og høyre barn, så vi bør tenke på dem som undertrær i stedet for undernoder.

I henhold til denne strukturen er hvert tre en kombinasjon av

  • En node som bærer data
  • To undertrær
Venstre og høyre undertre

Husk at målet vårt er å besøke hver node, så vi må besøke alle nodene i undertreet, besøke rotnoden og besøke alle nodene i riktig undertreet også.

Avhengig av i hvilken rekkefølge vi gjør dette, kan det være tre typer kryss.

Inorder traversal

  1. Først besøker du alle nodene i venstre undertreet
  2. Deretter rotnoden
  3. Besøk alle nodene i riktig undertre
 inorder(root->left) display(root->data) inorder(root->right)

Forhåndsbestill traversal

  1. Besøk rotnoden
  2. Besøk alle nodene i det venstre undertreet
  3. Besøk alle nodene i riktig undertre
 display(root->data) preorder(root->left) preorder(root->right)

Postorder traversal

  1. Besøk alle nodene i det venstre undertreet
  2. Besøk alle nodene i riktig undertre
  3. Besøk rotnoden
 postorder(root->left) postorder(root->right) display(root->data)

La oss visualisere gjennomkjøring. Vi starter fra rotnoden.

Venstre og høyre undertre

Vi krysser venstre undertre først. Vi må også huske å besøke rotnoden og riktig undertre når dette treet er ferdig.

La oss legge alt dette i en bunke slik at vi husker det.

Stable

Nå krysser vi til undertræren som er pekt på toppen av bunken.

Igjen følger vi den samme regelen om ordre

 Venstre undertre -> rot -> høyre undertre

Etter å ha krysset venstre undertrær sitter vi igjen med

Endelig stabel

Siden noden "5" ikke har noen undertrær, skriver vi den ut direkte. Etter det skriver vi ut foreldrene "12" og deretter det rette barnet "6".

Det var nyttig å legge alt på en bunke, for nå som venstre undertrær i rotnoden er krysset, kan vi skrive det ut og gå til høyre undertrær.

Etter å ha gått gjennom alle elementene får vi ordren traversal som

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

Vi trenger ikke å lage stakken selv fordi rekursjon opprettholder riktig rekkefølge for oss.

Python, Java og C / C ++ eksempler

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

Interessante artikler...