Как создать двоичное дерево

Question

Я не имел в виду двоичное дерево поиска.

например, Если я вставляю значения 1,2,3,4,5 в двоичное дерево поиска, то обход порядка даст 1,2,3,4,5 в качестве вывода.

, но если я вставляю те же значения в двоичное дерево, обход порядка должен давать 4,2,5,1,3 в качестве вывода.

Двоичное дерево может быть создано с использованием динамических массивов, в которых для каждого элемента индекса n, 2n + 1 и 2n + 2 представляют собой его левый и правый дочерние элементы соответственно.

поэтому представление и обход уровня уровня здесь очень прост.

но думаю, в порядке, после заказа, предварительный заказ сложно.

Мой вопрос: как мы можем создать двоичное дерево, как дерево двоичного поиска. т.е. имеют класс дерева, который содержит данные, левый и правый указатели вместо массивов. , чтобы мы могли рекурсивно совершать обход.

Answer 1

Часть декларации класса дерева, конечно, не является трудностью здесь. Вы в основном указано точно, как объявить его, в вопросе:

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

Это поддерживает различные формы обхода, например так:

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

Вы должны быть в состоянии вывести обходы до и после заказа От этого. В реальной реализации дерево, вероятно, было бы шаблоном для хранения случайных данных, процедуры трассировки были бы более общими (с вводом пользовательских данных или, возможно, запросом для каждого узла), конечно.

Answer 2

Поскольку я не получил никаких ответов на вопрос, который я задал, я опубликую свое собственное воплощение бинарного дерева с использованием массивов. теперь я знаю, что реализация array проще, чем я думал, но все же я не знаю, как реализовать то же самое с помощью связанных списков.

код в 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

Если я вас правильно понял, вы хотите создать бинарное дерево из массива

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

это должно предварительно заполнить бинарное дерево со значениями 1 - 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

Если вы используете исходный код для всесторонней реализации BinaryTree, вы можете изучить его на странице The C5 Generic Collection Library.