Bu eğitimde, farklı ağaç geçiş teknikleri hakkında bilgi edineceksiniz. Ayrıca, C, C ++, Java ve Python'da farklı ağaç geçiş yöntemlerinin çalışma örneklerini bulacaksınız.
Bir ağacın üzerinden geçmek, ağaçtaki her düğümü ziyaret etmek demektir. Örneğin, ağaçtaki tüm değerleri eklemek veya en büyüğünü bulmak isteyebilirsiniz. Tüm bu işlemler için, ağacın her bir düğümünü ziyaret etmeniz gerekecektir.
Diziler, yığınlar, kuyruklar ve bağlantılı liste gibi doğrusal veri yapılarının verileri okumak için yalnızca bir yolu vardır. Ancak ağaç gibi hiyerarşik bir veri yapısı farklı yollardan geçilebilir.
Ağaç geçişi
Yukarıda gösterilen görselde ağacın unsurlarını nasıl okuyabileceğimizi düşünelim.
Yukarıdan başlayarak, Soldan sağa
1 -> 12 -> 5 -> 6 -> 9
Alttan başlayarak, Soldan sağa
5 -> 6 -> 12 -> 9 -> 1
Bu işlem biraz kolay olsa da ağacın hiyerarşisine değil, sadece düğümlerin derinliğine saygı duyar.
Bunun yerine, bir ağacın temel yapısını dikkate alan geçiş yöntemlerini kullanırız, örn.
struct node ( int data; struct node* left; struct node* right; )
Sol ve sağ tarafından gösterilen yapı düğümü başka sol ve sağ çocuklara sahip olabilir, bu nedenle onları alt düğümler yerine alt ağaçlar olarak düşünmeliyiz.
Bu yapıya göre her ağaç,
- Veri taşıyan bir düğüm
- İki alt ağaç
Sol ve Sağ Alt Ağaç
Amacımızın her bir düğümü ziyaret etmek olduğunu unutmayın, bu nedenle alt ağaçtaki tüm düğümleri ziyaret etmemiz, kök düğümü ziyaret etmemiz ve sağ alt ağaçtaki tüm düğümleri de ziyaret etmemiz gerekir.
Bunu yaptığımız sıraya bağlı olarak, üç tür çapraz geçiş olabilir.
Inorder geçişi
- İlk önce, sol alt ağaçtaki tüm düğümleri ziyaret edin
- Sonra kök düğüm
- Sağ alt ağaçtaki tüm düğümleri ziyaret edin
inorder(root->left) display(root->data) inorder(root->right)
Ön sipariş geçişi
- Kök düğümü ziyaret edin
- Soldaki alt ağaçtaki tüm düğümleri ziyaret edin
- Sağ alt ağaçtaki tüm düğümleri ziyaret edin
display(root->data) preorder(root->left) preorder(root->right)
Postorder geçişi
- Soldaki alt ağaçtaki tüm düğümleri ziyaret edin
- Sağ alt ağaçtaki tüm düğümleri ziyaret edin
- Kök düğümü ziyaret edin
postorder(root->left) postorder(root->right) display(root->data)
Sıralı geçişi görselleştirelim. Kök düğümden başlıyoruz.
Sol ve Sağ Alt Ağaç
Önce soldaki alt ağaçtan geçiyoruz. Ayrıca, bu ağaç bittiğinde kök düğümü ve doğru alt ağacı ziyaret etmeyi de hatırlamamız gerekir.
Bütün bunları bir yığına koyalım ki hatırlayalım.
Yığın
Şimdi yığının ÜSTÜNDE işaret edilen alt ağaca geçiyoruz.
Yine, aynı sıralı kuralı takip ediyoruz
Sol alt ağaç -> kök -> sağ alt ağaç
Soldaki alt ağaçtan geçtikten sonra,
Nihai Yığın
"5" düğümünün herhangi bir alt ağacı olmadığından, onu doğrudan yazdırıyoruz. Bundan sonra ana "12" yi ve ardından sağ çocuk "6" yı yazdırırız.
Her şeyi bir yığına koymak yardımcı oldu çünkü artık kök düğümün sol alt ağacı geçildiğine göre, onu yazdırabilir ve sağ alt ağaca gidebiliriz.
Tüm unsurları geçtikten sonra, sıralı geçişi şu şekilde elde ederiz:
5 -> 12 -> 6 -> 1 -> 9
Yığını kendimiz oluşturmak zorunda değiliz çünkü özyineleme bizim için doğru düzeni sağlar.
Python, Java ve C / C ++ Örnekleri
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);
