छद्म कोड दो पेड़ों की तुलना करने के लिए

Question

यह एक समस्या है जिसे मैंने कुछ बार सामना किया है, और मुझे विश्वास नहीं है कि मैंने सबसे कुशल तर्क का उपयोग किया है।

उदाहरण के तौर पर, मान लें कि मेरे पास दो पेड़ हैं: एक फ़ोल्डर संरचना है, दूसरा उस फ़ोल्डर संरचना का एक इन-मेमोरी 'मॉडल' है। मैं दो पेड़ों की तुलना करना चाहता हूं, और नोड्स की एक सूची तैयार करता हूं जो एक पेड़ में मौजूद हैं, न कि दूसरे - और इसके विपरीत।

क्या इसे संभालने के लिए कोई स्वीकृत एल्गोरिदम है?

Answer 1

ऐसा लगता है कि आप केवल प्री-ऑर्डर ट्रैवर्सल करना चाहते हैं, अनिवार्य रूप से। जहां नोड का "दौरा" करना उन बच्चों की जांच करना है जो एक संस्करण में हैं लेकिन दूसरे नहीं हैं।

अधिक सटीक: रूट पर शुरू करें। प्रत्येक नोड पर, नोड के दो संस्करणों में से प्रत्येक में आइटम का एक सेट प्राप्त करें। दो सेटों के सममित अंतर में एक आइटम होता है लेकिन दूसरे नहीं। उनको प्रिंट/आउटपुट करें। चौराहे में वे आइटम होते हैं जो दोनों के लिए आम हैं। चौराहे में प्रत्येक आइटम के लिए (मुझे लगता है कि आप एक पेड़ से गुम वस्तुओं की ओर देखने के लिए नहीं जा रहे हैं), इसकी सामग्री की जांच के लिए उस नोड पर "विज़िट" को दोबारा कॉल करें। यह एक ओ (एन) ऑपरेशन है, जिसमें थोड़ा रिकर्सन ओवरहेड है।

Answer 2

public boolean compareTrees(TreeNode root1, TreeNode root2) { 
    if ((root1 == null && root2 != null) || 
     (root1 != null && root2 == null)) { 
    return false; 
    } 

    if (root1 == null && root2 == null) { 
    return true; 
    } 

    if (root1.data != root2.data) { 
    return false; 
    } 

    return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right); 
} 

Answer 3

पायथन में एक साधारण उदाहरण कोड।

class Node(object): 
    def __init__(self, val): 
    self.val = val 
    self.child = {} 

    def get_left(self): 
    #if left is not in the child dictionary that means the element does not have a left child 
    if 'left' in self.child: 
     return self.child['left'] 
    else: 
     return None 

    def get_right(self): 
    #if right is not in the child dictionary that means the element does not have a rigth child 
    if 'right' in self.child: 
     return self.child['right'] 
    else: 
     return None 


def traverse_tree(a): 
    if a is not None: 
    print 'current_node : %s' % a.val 
    if 'left' in a.child: 
     traverse_tree(a.child['left']) 

    if 'right' in a.child: 
     traverse_tree(a.child['right']) 



def compare_tree(a, b): 
    if (a is not None and b is None) or (a is None and b is not None): 
    return 0 
    elif a is not None and b is not None: 
    print a.val, b.val 
    #print 'currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s' % (a.val, b.val, a.child['left'].val, b.child['left'].val, a.child['right'].val, b.child['right'].val) 
    if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()): 
     return 1 
    else: 
     return 0 
    else: 
    return 1 

#Example 
a = Node(1) 
b = Node(0) 
a.child['left'] = Node(2) 
a.child['right'] = Node(3) 
a.child['left'].child['left'] = Node(4) 
a.child['left'].child['right'] = Node(5) 
a.child['right'].child['left'] = Node(6) 
a.child['right'].child['right'] = Node(7) 
b.child['left'] = Node(2) 
b.child['right'] = Node(3) 
b.child['left'].child['left'] = Node(4) 
#b.child['left'].child['right'] = Node(5) 
b.child['right'].child['left'] = Node(6) 
b.child['right'].child['right'] = Node(7) 
if compare_tree(a, b): 
    print 'trees are equal' 
else: 
    print 'trees are unequal' 
#DFS traversal 
traverse_tree(a) 

यह भी एक उदाहरण चिपकाया जिसे आप चला सकते हैं।

Answer 4

यदि आप एक एवीएल पेड़ की तरह एक प्रकार के पेड़ का उपयोग करते हैं, तो आप अपने पेड़ को कुशलतापूर्वक क्रम में भी पार कर सकते हैं। यह आपके पथ को क्रमबद्ध क्रम में "कम" से "उच्च" तक वापस कर देगा। फिर आप अपने पेड़ एल्गोरिदम में उपयोग की जाने वाली समान तुलना विधि का उपयोग करके अपनी निर्देशिका सरणी (उदा। क्विकॉर्ट का उपयोग कर) को सॉर्ट कर सकते हैं।

फिर दोनों पक्षों की तरफ से तुलना करना शुरू करें, अपने पेड़ को क्रम में घुमाकर और अपनी क्रमबद्ध निर्देशिका सरणी में अगला आइटम जांचकर अगले आइटम को आगे बढ़ाना शुरू करें।

यह अभ्यास में अधिक कुशल होना चाहिए, लेकिन केवल बेंचमार्किंग बता सकती है।