习题复习 Trees binary c++

Question

给定一棵二叉树，其根是宝藏，其内部节点可以包含龙或不包含任何东西，要求您设计一种算法，告诉我们树的叶子到根部的龙数量最少。如果存在多条路径且龙的数量相同，则算法将 return 位于所有路径左侧的路径。为此，实现一个函数来获取其节点存储整数的二叉树：

根包含整数0，代表宝物。
内部节点包含整数1表示该节点有龙或整数2表示没有龙
在每个叶子中存储一个大于等于3的整数，不能重复。和 return 整个 sheet 到所选路径。树至少有一个根节点和一个不同于根的叶节点。例如，给定以下树（示例中显示的第二个测试用例），算法 return 整数 4.

我无法上传示例树的图片，但有人告诉我，我可以通过所有分支，知道哪条路是龙少的路径，我将不胜感激。

问候！

Answer 1

您想递归地考虑这些问题：如果您在 parent 节点处...

没有children你一定没有龙和节点计数器，你认为自己有0条龙并且是最好的节点：你会告诉你的parent如果被问到
一个左分支and/or一个右分支，然后你向你的children询问他们的dragon-count以及他们认为哪个节点最好，如果是左节点报告较少或相等的龙数...
- 你从中取出你的 best-node 和 dragon-count，否则
- 你从正确的节点
如果您的节点存储整数 1

通过在根节点开始该处理，您将获得整棵树的结果。

Answer 2

这是第一个想到的算法。假设您有一个数组存储节点 node_value[NODE_NUM] 中的值，其中 NODE_NUM 是树中的节点数，并且您存储的子节点的索引每个节点都有数组 left[NODE_NUM] 和 right[NODE_NUM]，你的根节点将有索引 root_index。我们将到根路径中的龙的数量信息存储在数组dragon[NODE_NUM]中所以算法伪代码为：

# the recursive function itself   
process(node_index):
    n_left <- 0
    if node_value[left[node_index]] = 1
        n_left <- 1
    n_right <- 0
    if node_value[right[node_index]] = 1
        n_right <- 1

    dragon[left[node_index]] <- dragon[node_index] + n_left
    dragon[right[node_index]] <- dragon[node_index] + n_right
    process(left[node_index])
    process(right[node_index])

# the number of dragons in path from root to root is, obviously, zero:
dragon[root_index] <- 0

# Call the function itself
process(root_index)

之后，在dragon中，我们将从树中的每个节点开始计算龙的数量。现在，您所要做的就是遍历所有节点并找到叶子节点并且其值最小：

min <- infinity
node_min <- unknown
for each node:
    if node_value[node] >= 3:
        if dragon[node] < min:
            min <- dragon[node]
            node_min <- node

return node_min

现在，node_min是通往根的路径中龙最少的节点。

习题复习 Trees binary c++

Exercise review Trees binary c++

algorithm

binary-tree

tree-traversal