이진 트리를 만드는 방법

Question

나는 이진 탐색 트리를 의미하지 않았다.

예를 들어, 이진 탐색 트리에 값 1,2,3,4,5를 삽입하면 inorder traversal은 1,2,3,4,5를 출력으로 제공합니다.

그러나 이진 트리에 같은 값을 삽입하면 inorder traversal은 4,2,5,1,3을 출력으로 제공해야합니다.

인덱스 n의 각 요소에 대해 2n + 1 및 2n + 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); 
} 

당신은 사전 및 사후 주문 순회을 추론 할 수 있어야한다 :

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

이 지금과 같은 탐색 다양한 형태의 지원 그것을 통해서. 실제 구현에서 트리는 무작위 데이터를 저장하기 위해 템플릿으로 작성되며, 순회 루틴은 물론 (사용자 데이터 입력 또는 사용자 제공 노드 별 콜백 등을 통해) 더욱 일반적입니다.

Answer 2

내가 질문 한 질문에 대한 답을 얻지 못했기 때문에 배열을 사용하여 이진 트리를 구현했습니다. 지금은 배열 implementaion 내가 생각했던 것보다 쉽지만 여전히 링크 된 목록을 사용하여 동일한 구현하는 방법을 몰라요.

코드는 당신이이 값을 1로 이진 트리를 미리 채울한다

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

배열에서 이진 트리를 만들려면, 제대로 이해하면 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

에 - 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에서 살펴볼 수 있습니다.