樹的水平順序在向量中的元素遍歷

Question

我正在尋找一個算法，以獲取x值的列表，並通過它們循環開始在中間，然後在左邊的中間，然後在右邊的中間，然後中間左邊的中間......像一棵樹。

我不認爲遞歸會起作用，因爲它會在到達另一邊之前完全遍歷一邊。我需要平均分析。

Pretend this is a list of 50 numbers: 
.................................................. (50) 

Need to find the 25th element first 

........................1......................... (lvl1) 

Then the 12th, then 38th 
...........2.........................3............ (lvl2) 

Then the 6,18 31,44 
.....4...........5.............6...........7...... (lvl3) 

Then the 3,9,15,21 28,34,41,48 
..8.....9.....a......b.....c.......d.....e.....f.. (lvl4) 

等...直到所有的值都被遍歷。所以當lvl4被擊中的時候，我已經看到1,2,3,4,5,6,7,8,9，a，b，c，d，e，f。

我所有的嘗試都失敗了，以迭代的方式做到這一點。

效率並不重要，因爲它不會經常運行。

希望我的問題很明確。謝謝你

Answer 1

（後面是寫在斯威夫特的解決方案，但我希望你能理解並翻譯成喜愛選擇的語言，如果你想使用它）

---

我們可以很容易地想出一個解決方案，在你的數組數值描述一個完整的（/適當的）二叉樹的特殊情況下，即numElements = 2^(lvl-1)+1，其中lvl是你的樹的級別。請參閱下面的功能printFullBinaryTree(...)。

現在，我們還可以輕鬆地將任何數組擴展爲描述完整二叉樹的數組，參見expandToFullBinary。 '

通過結合這兩種方法，我們有了任意大小輸入數組的一般方法。

---

展開任何陣列成一個描述滿二叉樹：

/* given 'arr', returns array expanded to full binary tree (if necessary) */ 
func expandToFullBinary(arr: [String], expandByCharacter: String = "*") -> [String] { 

    let binLength = Int(pow(2.0,Double(Int(log2(Double(arr.count)))+1)))-1 
    if arr.count == binLength { 
     return arr 
    } 
    else { 
     let diffLength = binLength - arr.count 
     var arrExpanded = [String](count: binLength, repeatedValue: expandByCharacter) 

     var j = 0 
     for i in 0 ..< arr.count { 
      if i < (arr.count - diffLength) { 
       arrExpanded[i] = arr[i] 
      } 
      else { 
       arrExpanded[i+j] = arr[i] 
       j = j+1 
      } 
     } 

     return arrExpanded 
    } 
} 

打印陣列（即描述了一個滿二叉樹）爲二叉樹根據你的問題規格：

/* assumes 'arr' describes a full binary tree */ 
func printFullBinaryTree(arr: [String]) { 

    var posVectorA : [Int] = [arr.count/2] 
    var posVectorB : [Int] 
    var splitSize : Int = arr.count/2 

    var elemCount = 0 

    if arr.count < 2 { 
     print("\(arr.first ?? "")") 
    } 
    else { 
     while elemCount < arr.count { 
      posVectorB = [] 
      splitSize = splitSize/2 
      for i in posVectorA { 

       if elemCount == arr.count { 
        print("noo") 
        break 
       } 

       print(arr[i], terminator: " ") 
       elemCount = elemCount + 1 

       posVectorB.append(i-splitSize-1) 
       posVectorB.append(i+splitSize+1) 
      } 
      print("") 
      posVectorA = posVectorB 
     } 
    } 
} 

描述完整二叉樹以及描述非滿二叉樹的向量示例：

/* Example */ 
var arrFullBinary : [String] = ["8", "4", "9", "2", "a", "5", "b", "1", "c", "6", "d", "3", "e", "7", "f"] 

var arrNonFullBinary : [String] = ["g", "8", "h", "4", "i", "9", "j", "2", "a", "5", "b", "1", "c", "6", "d", "3", "e", "7", "f"] 

printFullBinaryTree(expandToFullBinary(arrFullBinary, expandByCharacter: "")) 
/* 1 
    2 3 
    4 5 6 7 
    8 9 a b c d e f */ 

printFullBinaryTree(expandToFullBinary(arrNonFullBinary, expandByCharacter: "")) 
/* 1 
    2 3 
    4 5 6 7 
    8 9 a b c d e f 
    g h i j   */ 

Answer 2

你可以通過queue data structure和一些數學來解決這個問題。

首先推入元組（0,25,49）。這表示這是位置25處的節點，分割範圍0-49。因此，隊列應該是這樣的：

[（0，25，49）]

現在，在每一個點，取出隊列的前面，該指數在打印元件，並將其推入的後代。那麼，例如，當你彈出（0,25,49），如何追蹤後代？左邊的後代是0-24範圍的中間，所以你可以推入（0,12,24）。右後裔是26-49範圍的中間，所以你可以推入（26,38,49）。所以隊列應該看起來像這樣：

[（0,13,23），（26,38,49）]。

Et cetera。