एक बाइनरी पेड़ का लंबवत योग

Question

बाइनरी पेड़ के ऊर्ध्वाधर योग को कैसे ढूंढें।

उदाहरण के लिए, नीचे द्विआधारी पेड़,

     1 
        /\ 
       / \ 
       / \ 
       2  3 
       /\ /\ 
      / \ / \ 
       4 5 6 7 
      /\/\/\/\ 
      5 9 1 3 6 7 5 5 

ऊपर पेड़ के लिए विचार करें, कार्यक्षेत्र राशि के रूप में गणना की जानी चाहिए,

• पंक्ति 1: 5
• पंक्ति 2: 4
• रेखा 3: 2,9,1
• रेखा 4: 5
• लाइन 5: 1,3,6
• पंक्ति 6: 6
• लाइन 7: 3,7,5
• लाइन 8: 7
• लाइन 9: 5

आउटपुट चाहिए हो:

5,4,12,5,10,6,15,7,5 

Answer 1

पहले तुम पदों खोजना चाहिए, आप के लिए छोड़ दिया और अधिकार विशिष्ट नोड तक पहुँचने के लिए खर्च करते हैं संख्या की गणना कर सकते हैं:

    1  : l = 0, r = 0 
       /\ 
      / \ 
     l=1,r=0 2  3 : l = 0, r = 1. 
      /\ /\ 
    ... 4...5 6...7 .... 

, बस आप अपने द्विआधारी पेड़ पार कर सकते हैं और अंत में प्रत्येक नोड के लिए LorR = NumberOfLeft - NumberOfRights गणना, तो समूह इस संख्या (उनके LorR मूल्य से) एक साथ और प्रत्येक समूह योग (उनमें सबसे सकारात्मक से LorR के सबसे नकारात्मक मूल्य को प्रिंट) को खोजने ।

अद्यतन: यह दो से अधिक ऊंचाई के पेड़ के लिए उत्तर नहीं देता है, हम इस समस्या को एल्गोरिदम में थोड़ा संशोधन के साथ ठीक कर सकते हैं।

    1 
       /\ 
      / \ 
      / \ 
      2  3 upto this we used 1/2 size of pyramid 
      /\ /\ 
     / \ / \ 
      4 5 6 7 upto this we used 1/2 + 1/4 part of pyramid 
     /\/\/\/\ 
     5 9 1 3 6 7 5 5 upto this we used 1/2 + 1/4 + 1/4 part of pyramid 

:

हम पेड़ देख सकते हैं पिरामिड के रूप में, पिरामिड के प्रत्येक शिखर लंबाई 1 है, प्रत्येक शाखा शेष शाखा का हिस्सा होने के बाद क्या नवीनतम चाल में पारित करने के लिए बराबर है, तो हम ऊंचाई 3 के पेड़ के लिए चित्र में यह दिखाने

इसका मतलब है कि प्रत्येक चरण में हम बाएं मानों की गणना उनकी ऊंचाई से करते हैं (वास्तव में प्रत्येक बार 1/2 गुणा को बाएं मान में जोड़ा जाएगा, जो अंतिम बार को छोड़कर, जो एच -1 सेंट मूल्य के बराबर है)।

तो इस मामले के लिए हमारे पास है: 1 रूट में समूह 0 में है, पत्ती में 3 समूह -1/2 + 1/4 + 1/4 = 0, 6 पत्ते में समूह 1/2 में है - 1/4 - 1/4 = 0

1 पत्ते में -1/2 + 1/4 - 1/4 = -1/2 और इसी तरह है।

के पूर्णांकन करने से रोकने के लिए 1/(2^एक्स) शून्य या अन्य समस्याओं के लिए हम 2 ^{ज -1} के लिए हमारी कारकों (1/2, 1/4, 1/8, ...) गुणा कर सकते हैं । असल में मैंने जो पहले मामले में लिखा था, हम कह सकते हैं कि कारकों को 2 ^2-1 से गुणा किया जाता है।

Answer 2

एक स्यूडोकोड में जानवर बल विधि:

columnAdd(tree): 
    sumPerColumn = new Map<int,int>(); 
    traverse(tree.root, sumPerColumn, 0); 
    return sumPerColumn; 

traverse(node, sumPerColumn, currentColumn): 
    sumPerColumn[currentColumn] ++; 
    traverse(node.left, sumPerColumn, currentColumn-1); 
    traverse(node.right, sumPerColumn, currentColumn+1); 

इस उपज होगा:

{-2: 4, 
    -1: 2, 
    0: 12, 
    1: 3, 
    2: 7} 

Answer 3

जहां तक ​​मैं ले छोड़ दिया समझ -1 होता है, आगे बढ़ सही +1 है । आप संशोधित डीएफएस का उपयोग कर सकते हैं। यहाँ मान लेते हैं कि add(col, value)

dfs(col, node) 
begin 
    add(col, node.value) 
    if(haveLeft) 
    dfs(col-1, left) 
    if(haveRight) 
    dfs(col+1, right) 
end 

मानते हुए, कि हे में काम करता है (1) (HashMap या उदाहरण के लिए सरल सरणी का उपयोग करके) जोड़ने परिभाषित किया गया है, इस हे (एन) में काम करता है।