Cách tạo cây nhị phân

Question

Tôi không có nghĩa là cây tìm kiếm nhị phân.

ví dụ: nếu tôi chèn giá trị 1,2,3,4,5 vào cây tìm kiếm nhị phân, quá trình truyền tải theo thứ tự sẽ cung cấp 1,2,3,4,5 làm đầu ra.

nhưng nếu tôi chèn cùng một giá trị vào cây nhị phân, quá trình truyền tải theo thứ tự sẽ cung cấp cho 4,2,5,1,3 làm đầu ra.

Cây nhị phân có thể được tạo bằng cách sử dụng mảng động trong đó cho mỗi phần tử trong chỉ mục n, 2n + 1 và 2n + 2 đại diện cho con trái và phải tương ứng.

vì vậy việc truyền tải trật tự đại diện và cấp độ rất dễ dàng tại đây.

nhưng tôi nghĩ, theo thứ tự, đặt hàng trước, đặt hàng trước rất khó.

câu hỏi của tôi là cách chúng ta có thể tạo cây nhị phân như cây tìm kiếm nhị phân. tức là. có một lớp cây có chứa dữ liệu, con trỏ trái và phải thay vì mảng. để chúng tôi có thể đệ quy thực hiện traversal.

Answer 1

Phần khai báo lớp cây là, chắc chắn, không phải là khó khăn ở đây. Về cơ bản bạn nói chính xác làm thế nào để khai báo nó, trong câu hỏi:

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

này hỗ trợ các hình thức khác nhau của traversal, như vậy:

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

Bạn sẽ có thể suy ra traversals trước và sau theo thứ tự từ đó. Trong quá trình thực hiện thực tế, cây có thể được sắp xếp để lưu trữ dữ liệu ngẫu nhiên, các thói quen truyền tải sẽ tổng quát hơn (với đầu vào dữ liệu người dùng hoặc có thể là do người dùng cung cấp cho mỗi nút gọi lại hoặc bất kỳ thứ gì).

Answer 2

Vì tôi chưa nhận được bất kỳ câu trả lời nào cho câu hỏi mà tôi đã hỏi, tôi sẽ đăng triển khai thực hiện của riêng cây nhị phân bằng mảng. bây giờ tôi biết rằng triển khai mảng là dễ dàng hơn tôi nghĩ, nhưng tôi vẫn không biết làm thế nào để thực hiện tương tự bằng cách sử dụng danh sách liên kết.

mã là trong 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

Nếu tôi hiểu bạn một cách chính xác, bạn muốn tạo một cây nhị phân từ một mảng

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

này nên prepopulate cây nhị phân với các giá trị 1 - 5 như sau:

1 
/\ 
    2 3 
/\ 
4 5 

điều này có thể được thực hiện bằng cách sử dụng lớp sau:

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

Nếu bạn sau khi nguồn để triển khai BinaryTree toàn diện, bạn có thể tìm hiểu từ xem The C5 Generic Collection Library.