向量中元素的树级顺序遍历

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

你可以通过 queue data structure 和一些数学来解决这个问题。

首先推入元组 (0, 25, 49)。这表明这是位置 25 处的节点，划分范围 0-49。所以队列应该是这样的：

[(0, 25, 49)]

现在在每个点，移除队列的前端，打印索引处的元素，然后推入后代。那么，比如当你 pop(0, 25, 49) 时，如何跟踪后代？左后代是 0-24 范围的中间，因此您将推入 (0, 12, 24)。右后代是 26-49 范围的中间，因此您将推入 (26, 38, 49)。所以队列应该是这样的：

[(0, 13, 23), (26, 38, 49)].

等等。

Answer 2

（后面的解决方案写在Swift中，但希望您能照着做，翻译成您喜欢的语言，以备不时之需）

我们可以很容易地想出一个解决方案，该解决方案适用于您的数组值的数量描述完整（/正确）二叉树的特殊情况，即，如果 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
        }
    }
}

描述完整二叉树和描述 non-full 二叉树的向量示例：

/* 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            */

向量中元素的树级顺序遍历

Tree Level-Order Traversal of Elements in a Vector

algorithm

tree