如何創建二叉樹

Question

我並不是指二叉搜索樹。

例如， 如果我將值1,2,3,4,5插入二進制搜索樹，那麼順序遍歷將給出 1,2,3,4,5作爲輸出。

但如果我在二叉樹中插入相同的值，那麼inorder遍歷應該給出 4,2,5,1,3作爲輸出。

可以使用動態數組創建二叉樹，其中對於索引n中的每個元素，012n + 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

由於我沒有收到任何問題的答案，所以我會用數組發佈自己的二叉樹實現。 現在我知道數組的實現比我想象的更容易，但我仍然不知道如何使用鏈表來實現它。

的代碼是用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。