Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Java

इनऑर्डर ट्री ट्रैवर्सल करने के लिए Java प्रोग्राम


इस लेख में, हम समझेंगे कि इनऑर्डर ट्री ट्रैवर्सल कैसे करें। इनऑर्डर ट्रैवर्सल में, प्रत्येक नोड को सबट्रीज के बीच प्रोसेस किया जाता है। सरल शब्दों में, लेफ्ट सबट्री विजिट करें, फिर नोड, फिर राइट सबट्री।

नीचे इसका प्रदर्शन है:

मान लीजिए हमारा इनपुट है:

प्रोग्राम चलाएं

वांछित आउटपुट होगा:

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;
            }
        }
    }
}
  1. जावा प्रोग्राम से आयत का परिमाप (Perimeter of Rectangle) निकालना जावा प्रोग्राम से आयत का परिमाप (Perimeter of Rectangle) निकालना

    इस लेख में हम समझेंगे कि आयत का परिमाप कैसे निकाला जाता है। आयत का परिमाप आयत की सभी भुजाओं की लंबाई को जोड़कर निकाला जाता है। नीचे एक आयत का प्रदर्शन दिया गया है। आयत का परिमाप आयत की दो लंबाई और दो चौड़ाई की कुल लंबाई होती है: इनपुट मान लीजिए हमारा इनपुट है: आयत की भुजाओं की लंबाई हैं: 5, 8, 5,

  1. Python में n-ary ट्री का व्यास खोजने का प्रोग्राम Python में n-ary ट्री का व्यास खोजने का प्रोग्राम

    मान लीजिए, हमें एक n-ary ट्री दिया गया है और ट्री का व्यास निर्धारित करने के लिए कहा गया है। ट्री का व्यास ट्री के किन्हीं दो लीफ नोड्स के बीच मौजूद सबसे लंबा पथ है। हमें पूर्णांक मान वापस करना है जो ट्री के व्यास को दर्शाता है। इसलिए, यदि इनपुट निम्न ट्री है: तो आउटपुट 3 होगा। इस n-ary ट्री का व्

  1. Python में n-ary ट्री का रूट खोजने का प्रोग्राम Python में n-ary ट्री का रूट खोजने का प्रोग्राम

    मान लीजिए, हमें एक n-ary ट्री के नोड्स एक सरणी में दिए गए हैं। हमें ट्री को पुनर्निर्मित करके उसका रूट नोड ढूंढना और वापस करना है। वापस किए गए नोड से पूरा ट्री प्रीऑर्डर नोटेशन में प्रदर्शित करना है। इसलिए, यदि इनपुट निम्न ट्री है: तो आउटपुट होगा: [14, 27, 32, 42, 56, 65] हम ट्री के प्रीऑर्डर ट्रै