插入二叉樹不排序輸入

Question

如何可以建立二叉樹不排序它，即

如果我有一個輸入5 4 9 8 1 2 7如何可以插入到基於二叉樹的參考。 我知道這可以很容易地與數組實現，但它可能與參考基地？

Answer 1

一個簡單的規則是總是插入到左側的子樹中，然後切換子樹。右子樹總是比左子樹大0-1個元素，所以你總是可以插入左子樹。現在，左邊的子樹比右邊的子樹大0-1個元素，所以你想切換子樹來保持不變。在僞代碼：

insert(t,v) { 
    if (t == null) { 
     return new TreeNode(v,null,null) 
    } else { 
     left = insert(t.left,v) 
     right = t.right 
     t.left = right 
     t.right = left 
     return t 
    } 
} 

Answer 2

Tree buildTree(int[] array, int index) { 
    if(index > array.length) { return null; } 
    return new Tree(
    array[index], 
    buildTree(array, 2 * index + 1), 
    buildTree(array, 2 * index + 2)); 
} 

大部分的工作是在遞歸和索引，但它也不是太糟糕的。