बनाना द्विआधारी खोज पेड़

Question

तो मैं क्रम में निम्न मान जोड़ने एक द्विआधारी खोज वृक्ष का निर्माण:

10, 7, 16, 12, 5, 11, 2, 20, 1, 14 

मैं ऊंचाई 5 के एक पेड़ मिल वहाँ एक विधि (परीक्षण और त्रुटि के अलावा अन्य) है कि मैं यह कर सकते हैं पूर्णांक के क्रम का निर्धारण करने के लिए उपयोग करें जो ऊंचाई 4 का पेड़ बनाएगा?

Answer 1

मैं पूरी तरह से के माध्यम से इस बारे में नहीं सोचा है, लेकिन विशिष्ट गहराई का एक पेड़ होने का एक तरीका है कि उन्हें डालने से पहले अपने तत्वों को सॉर्ट करने के लिए है: तो एक द्विआधारी खोज वृक्ष में N तत्वों डालने एक पेड़ का उत्पादन करेगा छँटाई अर्थात गहराई N।

आप में सक्षम हो सकता है:

1. क्रमबद्ध अपने तत्वों
2. सम्मिलित एक विशिष्ट K=4 उनमें से इस तरह से कि में शेष तत्व सम्मिलित K
3. गहराई का एक पेड़ का निर्माण करने के पेड़ गहरा नहीं होता है।

(बेशक, चुनने जो K तत्वों के साथ शुरू करने के लिए और शेष तत्व डालने के लिए एक रणनीति मुश्किल हिस्सा है - लेकिन शायद यह होगा एक शुरुआत)

---

संपादित : मुझे लगता है कि एक सामान्य समाधान संभव है, मानते हैं कि K काफी बड़ा है। कैसे इस बारे में:

1. को देखते हुए 10, 7, 16, 12, 5, 11, 2, 20, 1, 14
2. क्रमबद्ध अपने तत्वों: 1, 2, 5, 7, 10, 11, 12, 14, 16, 20
3. सम्मिलित पिछले K = 4 तत्वों, तो पिछले K-1, तो K-2, और इतने पर, 1 करने के लिए नीचे ।

उदाहरण के लिए, छंटाई और डालने के बाद पिछले 4:

12 
    \ 
    14 
    \ 
     16 
     \ 
     20 

... तो डालने के बाद पिछले 3:

12 
/\ 
7 14 
\  \ 
    10 16 
    \  \ 
    11 20 

... तो पिछले 2 के बाद:

12 
/\ 
    7 14 
/\  \ 
2 10 16 
\ \  \ 
    5 11 20 

... और अंत में, पिछले तत्व डालने के बाद:

 12 
    /\ 
    7 14 
/\  \ 
    2 10 16 
/\ \  \ 
1 5 11 20 

... आपको ऊंचाई के बीएसटी के साथ छोड़ दिया गया है = 4।

ध्यान दें कि यह दृष्टिकोण केवल तभी काम करेगा जब K काफी बड़ा होगा - विशेष रूप से, जब K(K+1)/2 >= N।

Answer 2

हां, आप पहले एक पूरी तरह संतुलित संतुलित पेड़ बना सकते हैं और फिर आप नोड्स को ऐसे तरीके से आउटपुट कर सकते हैं जिनके माता-पिता नोड्स को उनके बच्चों के सामने मुद्रित किया जा सके।

एक पूरी तरह से संतुलित पेड़ बनाने के लिए, बस संख्याओं को क्रमबद्ध करें और फिर पेड़ बनाने के लिए रिकर्सिव बाइनरी डिवीजनों का उपयोग करें।

---

उदाहरण के लिए, आपके मामले में हम संख्या

1 2 5 7 10 11 12 14 16 20 

सॉर्ट और फिर उन लोगों से एक संतुलित पेड़ का निर्माण (रूट के रूप में मध्य नंबर लेने के लिए और इस प्रक्रिया रिकर्सिवली दोहराने)

  11 
    5   14 
1  7  12 16 
    2  10    20 

अब हम एक ऑर्डर में नोड्स को मुद्रित करने के लिए प्रीऑर्डर ट्रैवर्सल या चौड़ाई-पहले ट्रैवर्सल का उपयोग कर सकते हैं (जब तक हम बच्चों के सामने पैरेंट नोड्स को आउटपुट करते हैं) हम ठीक होंगे।

11 5 14 1 7 12 16 2 10 20 

Answer 3

public void testMakeBinarySearchTree() { 
    List<Integer> array = new ArrayList<>(); 
    for (int i = 0; i < 10; i++) { 
     array.add(i+1); 
    } 


    Collections.shuffle(array); 


    Node root = new Node(array.get(5)); 
    for (int value : array) { 
     binarySearchTreeInsertNode(root, value); 
    } 
} 


private void binarySearchTreeInsertNode(Node node, int value) { 
    int data = node.getData(); 
    if (value > data) { 
     Node right = node.getRight(); 
     if (right != null) { 
      binarySearchTreeInsertNode(right, value); 
     } else { 
      node.setRight(new Node(value)); 
     } 
    } else if (value < data) { 
     Node left = node.getLeft(); 
     if (left != null) { 
      binarySearchTreeInsertNode(left, value); 
     } else { 
      node.setLeft(new Node(value)); 
     } 
    } 
}