我必须做一个函数,给定一个 int n 和一个二叉搜索树,我必须将 bst int 的第 n 级转换为一个链表。 例如,如果给定数字 2 和这棵树
2
/ \
5 3
我必须用 5 - 3 制作一个喜欢的列表
我在到达给定的级别时遇到问题,然后在该级别上获取每个节点,因为如果我确实达到了该级别,我不知道如何到达下一个节点。意思是,我只能在一个分支上达到这个级别,而且我想不出任何递归的方法。
所以这是 bst 和链接链的结构:
struct nodo {
info_t dato;
nodo *anterior;
nodo *siguiente;
};
struct rep_cadena {
nodo *inicio;
nodo *final;
};
struct rep_binario {
info_t dato;
rep_binario *izq;
rep_binario *der;
};
这是我想不通的功能:
cadena_t nivel_en_binario(nat l, binario_t b)
我已经尝试使用我已经创建的另一个函数来计算树的高度,但我无法停在想要的高度上。
nat altura_binario(binario_t b) {
if (b==NULL) return 0;
else return maximo(altura_binario(b->izq), altura_binario(b->der))+ 1;
}
其中 maximo() 返回两个给定数字之间的最大数字。
最佳答案
您可以通过实现 Breadth-first_search 来做到这一点算法,稍微修改一下。您可以将成对的 (node, level)
入队(其中 node level = parent level + 1),而不是仅将节点入队,然后在入队时您可以检查是否达到了所需的水平,并且只需将其作为结果输出,而不是进一步排队。
伪代码草图:
target_level = ...read from input...
let level_nodes = ...an empty list...
let queue = ...an empty queue...
queue.enqueue((root_node, 0))
while queue is not empty:
node, level = queue.dequeue()
if level == target_level:
level_nodes.append(node)
else:
if node has left child:
queue.enqueue((left_child_node, level + 1))
if node has right child:
queue.enqueue((right_child_node, level + 1))
关于c - 如何将给定级别的二叉搜索树转换为链接链?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55666565/