बाइनरी पेड़ कैसे बनाएं

Question

मेरा मतलब बाइनरी खोज पेड़ नहीं था।

उदाहरण के लिए

, अगर मैं मान एक द्विआधारी खोज वृक्ष में 1,2,3,4,5 सम्मिलित inorder ट्रावर्सल 1,2,3,4,5 आउटपुट के रूप में दे देंगे।

लेकिन यदि मैं एक ही मूल्य को बाइनरी पेड़ में डालता हूं, तो इनऑर्डर ट्रैवर्सल को आउटपुट के रूप में 4,2,5,1,3 देना चाहिए।

बाइनरी पेड़ गतिशील सरणी का उपयोग करके बनाया जा सकता है जिसमें सूचकांक एन, 2 एन + 1 और 2 एन + 2 में प्रत्येक तत्व क्रमशः अपने बाएं और दाएं बच्चे का प्रतिनिधित्व करता है।

तो प्रतिनिधित्व और स्तर आदेश ट्रैवर्सल यहां बहुत आसान है।

लेकिन मुझे लगता है कि, क्रम में, पोस्ट ऑर्डर, प्री-ऑर्डर मुश्किल है।

मेरा सवाल यह है कि हम बाइनरी खोज पेड़ की तरह बाइनरी पेड़ कैसे बना सकते हैं। यानी। में एक वृक्ष वर्ग है जिसमें सरणी के बजाय डेटा, बाएं और दाएं पॉइंटर्स होते हैं। ताकि हम पुनरावर्ती रूप से ट्रैवर्सल कर सकें।

Answer 1

पेड़ वर्ग घोषणा भाग निश्चित रूप से यहां कठिनाई नहीं है। मूल रूप से कहा वास्तव में आप कैसे यह घोषित करने के सवाल में:

void Inorder(const BinaryTree *root) 
{ 
    if(root == 0) 
    return; 
    Inorder(root->left); 
    printf("now at %d\n", root->data); 
    Inorder(root->right); 
} 

आप पहले और बाद में आदेश traversals निकालना सक्षम होना चाहिए:

class BinaryTree 
{ 
private: 
    int data; 
    BinaryTree *left, *right; 
}; 

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

Answer 2

चूंकि मुझे पूछे गए प्रश्न का कोई जवाब नहीं मिला है, इसलिए मैं सरणी का उपयोग करके बाइनरी पेड़ का अपना कार्यान्वयन पोस्ट करूंगा। अब मुझे पता है कि सरणी कार्यान्वयन मेरे विचार से आसान है, लेकिन फिर भी मुझे नहीं पता कि लिंक किए गए सूचियों का उपयोग करके इसे कैसे कार्यान्वित किया जाए।

कोड #

class BinaryTree 
    { 
     private static int MAX_ELEM = 100;  //initial size of the array 
     int lastElementIndex; 
     int?[] dataArray; 

     public BinaryTree() 
     { 
      dataArray = new int?[MAX_ELEM]; 
      lastElementIndex = -1; 
     } 

     //function to insert data in to the tree 
     //insert as a complete binary tree 
     public void insertData(int data) 
     { 
      int?[] temp; 
      if (lastElementIndex + 1 < MAX_ELEM) 
      { 
       dataArray[++lastElementIndex] = data; 
      } 
      else 
      { //double the size of the array on reaching the limit 
       temp = new int?[MAX_ELEM * 2]; 
       for (int i = 0; i < MAX_ELEM; i++) 
       { 
        temp[i] = dataArray[i]; 
       } 
       MAX_ELEM *= 2; 
       dataArray = temp; 
       dataArray[++lastElementIndex] = data; 
      } 
     } 

     //internal function used to get the left child of an element in the array 
     int getLeftChild(int index) { 
      if(lastElementIndex >= (2*index+1)) 
       return (2*index + 1); 
      return -1; 
     } 

     //internal function used to get the right child of an element in the array 
     int getRightChild(int index) { 
      if(lastElementIndex >= (2*index+2)) 
       return (2*index + 2); 
      return -1; 
     } 
     //function to check if the tree is empty 
     public bool isTreeEmpty() { 
      if (lastElementIndex == -1) 
       return true; 
      return false; 
     } 

     //recursive function for inorder traversal 
     public void traverseInOrder(int index) { 
      if (index == -1) 
       return; 
      traverseInOrder(getLeftChild(index)); 
      Console.Write("{0} ", dataArray[index]); 
      traverseInOrder(getRightChild(index)); 
     } 

     //recursive function for preorder traversal 
     public void traversePreOrder(int index) { 
      if (index == -1) 
       return; 
      Console.Write("{0} ", dataArray[index]); 
      traversePreOrder(getLeftChild(index)); 
      traversePreOrder(getRightChild(index)); 
     } 

     //recursive function for postorder traversal 
     public void traversePostOrder(int index) { 
      if (index == -1) 
       return; 
      traversePostOrder(getLeftChild(index)); 
      traversePostOrder(getRightChild(index)); 
      Console.Write("{0} ", dataArray[index]); 
     } 

     //function to traverse the tree in level order 
     public void traverseLevelOrder() 
     { 
      Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n"); 
      if (lastElementIndex == -1) 
      { 
       Console.WriteLine("Empty Tree!...press any key to return"); 
       Console.ReadKey(); 
       return; 
      } 
      for (int i = 0; i <= lastElementIndex; i++) 
      { 
       Console.Write("{0} ", dataArray[i]); 
      } 
      Console.WriteLine("\n"); 
     } 


    } 

Answer 3

ग अगर मैं तुम्हें सही ढंग से समझ, आप एक सरणी

int[] values = new int[] {1, 2, 3, 4, 5}; 
BinaryTree tree = new BinaryTree(values); 

इस मान 1 के साथ द्विआधारी पेड़ prepopulate चाहिए से एक द्विआधारी पेड़ बनाना चाहते हैं में है - 5 इस प्रकार है:

1 
/\ 
    2 3 
/\ 
4 5 

इस निम्नलिखित वर्ग का उपयोग किया जा सकता है:

class BinaryTree 
{ 
    int value; 
    BinaryTree left; 
    BinaryTree right; 

    public BinaryTree(int[] values) : this(values, 0) {} 

    BinaryTree(int[] values, int index) 
    { 
     Load(this, values, index); 
    } 

    void Load(BinaryTree tree, int[] values, int index) 
    { 
     this.value = values[index]; 
     if (index * 2 + 1 < values.Length) 
     { 
      this.left = new BinaryTree(values, index * 2 + 1); 
     } 
     if (index * 2 + 2 < values.Length) 
     { 
      this.right = new BinaryTree(values, index * 2 + 2); 
     } 
    } 
} 

Answer 4

यदि आप एक व्यापक बाइनरीट्री कार्यान्वयन के स्रोत के बाद हैं तो आप The C5 Generic Collection Library पर एक नज़र से सीख सकते हैं।