So erstellen Sie einen Binärbaum

Question

Ich meine nicht binäre Suchbaum.

zum Beispiel, Wenn ich die Werte 1,2,3,4,5 in einen binären Suchbaum einfüge, ergibt der inorder traversal 1,2,3,4,5 als Ausgabe.

Wenn ich jedoch die gleichen Werte in einen Binärbaum einfüge, sollte der Inorder-Traversal 4,2,5,1,3 als Ausgabe ergeben.

Binärbaum kann mit dynamischen Arrays erstellt werden, in denen für jedes Element in Index n 2n + 1 und 2n + 2 seine linken bzw. rechten childs darstellt.

so ist die Darstellung und Ebene Reihenfolge Traversal sehr einfach hier.

aber ich denke, in Ordnung, nachbestellen, vorbestellen ist schwierig.

Meine Frage ist, wie können wir einen Binärbaum wie einen binären Suchbaum erstellen. dh. haben eine Baumklasse, die Daten, linke und rechte Zeiger anstelle von Arrays enthält. , so dass wir rekursiv Traversal tun können.

Answer 1

Der Baum Klasse Deklaration Teil ist sicherlich nicht die Schwierigkeit hier. im Grunde erklären Sie genau, wie es zu erklären, in der Frage:

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

Dies unterstützt verschiedene Formen der Traversal, etwa so:

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

Sie sollen vor und nach Ordnung Traversierungen ableiten können, davon. In einer realen Implementierung würde der Baum wahrscheinlich templatiert sein, um zufällige Daten zu speichern, die Durchlaufroutinen würden allgemeiner sein (mit einer Benutzerdateneingabe oder natürlich einem Benutzer-zugeteilten Anrufrückruf oder was auch immer), natürlich.

Answer 2

Da ich auf die Frage, die ich gestellt habe, keine Antworten erhalten habe, werde ich meine eigene Implementierung des Binärbaums mit Arrays veröffentlichen. jetzt weiß ich, dass Array-Implementierung ist einfacher als ich dachte, aber ich weiß immer noch nicht, wie Sie das gleiche mithilfe von verketteten Listen implementieren.

der Code ist in C#

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

Wenn ich Sie richtig verstehe, du 1 einen binären Baum aus einem Array

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

sollte dies vorab ausgefüllt den binären Baum mit den Werten erstellen möchten - 5 wie folgt:

1 
/\ 
    2 3 
/\ 
4 5 

dies mit der folgenden Klasse durchgeführt werden kann:

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

Wenn Sie nach einer umfassenden BinaryTree-Implementierung suchen, können Sie unter The C5 Generic Collection Library nachlesen.