I denne vejledning lærer du om forskellige teknikker til traversering af træer. Du finder også arbejdseksempler på forskellige trægennemgangsmetoder i C, C ++, Java og Python.
At krydse et træ betyder at besøge hver knude i træet. Du kan f.eks. Tilføje alle værdierne i træet eller finde den største. For alle disse operationer skal du besøge hver node i træet.
Lineære datastrukturer som arrays, stakke, køer og sammenkædet liste har kun en måde at læse dataene på. Men en hierarkisk datastruktur som et træ kan krydses på forskellige måder.
Træ gennemgange
Lad os tænke på, hvordan vi kan læse elementerne i træet i billedet vist ovenfor.
Startende fra top, venstre mod højre
1 -> 12 -> 5 -> 6 -> 9
Startende fra bunden, venstre mod højre
5 -> 6 -> 12 -> 9 -> 1
Selvom denne proces er noget let, respekterer den ikke træets hierarki, kun dybden af noderne.
I stedet bruger vi gennemkørselsmetoder, der tager højde for den grundlæggende struktur af et træ, dvs.
struct node ( int data; struct node* left; struct node* right; )
Strukturknudepunktet, som venstre og højre peger på, kan have andre venstre og højre børn, så vi skal tænke på dem som undertræer i stedet for underknudepunkter.
Ifølge denne struktur er hvert træ en kombination af
- En node, der bærer data
- To undertræer
Venstre og højre undertræ
Husk, at vores mål er at besøge hver knude, så vi skal også besøge alle knudepunkterne i undertræet, besøge rodknudepunktet og besøge alle knudepunkterne i det rigtige undertræ.
Afhængigt af rækkefølgen, hvor vi gør dette, kan der være tre typer traversal.
Bestil gennemkørsel
- Besøg først alle knudepunkter i det venstre undertræ
- Derefter rodnoden
- Besøg alle knudepunkter i det rigtige undertræ
inorder(root->left) display(root->data) inorder(root->right)
Forudbestil traversal
- Besøg rodnoden
- Besøg alle knudepunkterne i venstre undertræ
- Besøg alle knudepunkter i det rigtige undertræ
display(root->data) preorder(root->left) preorder(root->right)
Postorder traversal
- Besøg alle knudepunkterne i venstre undertræ
- Besøg alle knudepunkter i det rigtige undertræ
- Besøg rodnoden
postorder(root->left) postorder(root->right) display(root->data)
Lad os visualisere rækkefølge i rækkefølge. Vi starter fra rodnoden.
Venstre og højre undertræ
Vi krydser det venstre undertræ først. Vi skal også huske at besøge rodnoden og det rigtige undertræ, når dette træ er færdigt.
Lad os lægge alt dette i en stak, så vi husker det.
Stak
Nu krydser vi til undertrådet, der er peget på TOPPEN på stakken.
Igen følger vi den samme regel for ordre
Venstre undertræ -> rod -> højre undertræ
Efter at have krydset det venstre undertræ står vi tilbage med
Endelig stak
Da noden "5" ikke har nogen undertræer, udskriver vi den direkte. Derefter udskriver vi sin forælder "12" og derefter det rigtige barn "6".
At lægge alt på en stak var nyttigt, for nu hvor rodnodens venstre undertræ er krydset, kan vi udskrive det og gå til det rigtige undertræ.
Efter at have gennemgået alle elementerne får vi ordren gennemgange som
5 -> 12 -> 6 -> 1 -> 9
Vi behøver ikke selv oprette stakken, fordi rekursion opretholder den rigtige rækkefølge for os.
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);
