इस लेख में, हम समझेंगे कि इनऑर्डर ट्री ट्रैवर्सल कैसे करें। इनऑर्डर ट्रैवर्सल में, प्रत्येक नोड को सबट्रीज के बीच प्रोसेस किया जाता है। सरल शब्दों में, लेफ्ट सबट्री विजिट करें, फिर नोड, फिर राइट सबट्री।
नीचे इसका प्रदर्शन है:
मान लीजिए हमारा इनपुट है:
प्रोग्राम चलाएं
वांछित आउटपुट होगा:
tree_object का इन-ऑर्डर ट्रैवर्सल है: 5->12->6->1->9->
एल्गोरिदम
चरण 1 - शुरू चरण 2 - डेटा स्पेसिफिकेशन्स के साथ एक क्लास पहले से परिभाषित है चरण 3 - क्लास का नया इंस्टेंस बनाएं चरण 4 - इंस्टेंस को प्रासंगिक मानों से इनिशियलाइज़ करें चरण 5 - इनऑर्डर ट्रैवर्सल करने के लिए मेथड इनवोक करें चरण 6 - परिणाम प्रदर्शित करें चरण 7 - रुकें
उदाहरण 1: रिकर्सिव इनऑर्डर ट्रैवर्सल
यहाँ, हमने इन-ऑर्डर ट्रैवर्सल के लिए रिकर्सिव मेथड का उपयोग किया है।
class Node {
int item;
Node left_node, right_node;
public Node(int key) {
item = key;
left_node = right_node = null;
}
}
public class Tree {
Node root;
Tree() {
root = null;
}
void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left_node);
System.out.print(node.item + "->");
inOrder(node.right_node);
}
public static void main(String[] args) {
Tree tree_object = new Tree();
System.out.println("एक tree_object ऑब्जेक्ट परिभाषित है: ");
tree_object.root = new Node(1);
tree_object.root.left_node = new Node(12);
tree_object.root.right_node = new Node(9);
tree_object.root.left_node.left_node = new Node(5);
tree_object.root.left_node.right_node = new Node(6);
System.out.println("tree_object का इन-ऑर्डर ट्रैवर्सल है: ");
tree_object.inOrder(tree_object.root);
}
}
आउटपुट
एक tree_object ऑब्जेक्ट परिभाषित है: tree_object का इन-ऑर्डर ट्रैवर्सल है: 5->12->6->1->9->
उदाहरण 2: नॉन-रिकर्सिव (इटरेटिव) इनऑर्डर ट्रैवर्सल
यहाँ, हम इन-ऑर्डर ट्रैवर्सल के लिए नॉन-रिकर्सिव मेथड का उपयोग कर रहे हैं।
import java.util.Stack;
class Node {
int data;
Node left_node, right_node;
public Node(int item) {
data = item;
left_node = right_node = null;
}
}
class Tree {
Node root;
void inorder() {
if (root == null)
return;
Stack temp_stack = new Stack();
Node current_node = root;
while (current_node != null || temp_stack.size() > 0) {
while (current_node != null) {
temp_stack.push(current_node);
current_node = current_node.left_node;
}
current_node = temp_stack.pop();
System.out.print(current_node.data + " ");
current_node = current_node.right_node;
}
}
public static void main(String args[]) {
Tree tree = new Tree();
System.out.println("एक tree ऑब्जेक्ट परिभाषित है: ");
tree.root = new Node(1);
tree.root.left_node = new Node(2);
tree.root.right_node = new Node(3);
tree.root.left_node.left_node = new Node(4);
tree.root.left_node.right_node = new Node(5);
System.out.println("tree का इन-ऑर्डर ट्रैवर्सल है: ");
tree.inorder();
}
}
आउटपुट
एक tree ऑब्जेक्ट परिभाषित है: tree का इन-ऑर्डर ट्रैवर्सल है: 4 2 5 1 3
ट्री ट्रैवर्सल प्रकार
| ट्रैवर्सल | क्रम | उपयोग का मामला |
|---|---|---|
| इनऑर्डर (LNR) | लेफ्ट → नोड → राइट | BST में सॉर्टेड ऑर्डर, एक्सप्रेशन ट्री |
| प्रीऑर्डर (NLR) | नोड → लेफ्ट → राइट | ट्री कॉपी, प्रीफिक्स एक्सप्रेशन |
| पोस्टऑर्डर (LRN) | लेफ्ट → राइट → नोड | ट्री डिलीट, पोस्टफिक्स एक्सप्रेशन |
| लेवल ऑर्डर | लेवल दर लेवल | शॉर्टेस्ट पथ, लेवल-वाइज प्रोसेसिंग |
रिकर्सिव बनाम इटरेटिव
| पहलू | रिकर्सिव | इटरेटिव |
|---|---|---|
| कोड सादगी | सरल, पठनीय | जटिल, एक्सप्लिसिट स्टैक |
| स्पेस जटिलता | O(h) कॉल स्टैक | O(h) एक्सप्लिसिट स्टैक |
| स्टैक ओवरफ्लो जोखिम | गहरे ट्रीज के लिए हाँ | नहीं (हीप मेमोरी उपयोग) |
| प्रदर्शन | थोड़ा धीमा (कॉल ओवरहेड) | थोड़ा तेज़ |
Morris ट्रैवर्सल (O(1) स्पेस)
// थ्रेडेड बाइनरी ट्री कॉन्सेप्ट - कोई स्टैक/रिकर्सन नहीं
void morrisInorder(Node root) {
Node current = root;
while (current != null) {
if (current.left_node == null) {
System.out.print(current.item + " ");
current = current.right_node;
} else {
// इनऑर्डर प्रीडिसेसर ढूंढें
Node pre = current.left_node;
while (pre.right_node != null && pre.right_node != current)
pre = pre.right_node;
if (pre.right_node == null) {
pre.right_node = current; // थ्रेड बनाएं
current = current.left_node;
} else {
pre.right_node = null; // थ्रेड हटाएं
System.out.print(current.item + " ");
current = current.right_node;
}
}
}
}