树的水平顺序在向量中的元素遍历

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。