이진이 아닌 트리에 대한 비 재귀 깊이 우선 검색 알고리즘을 찾고 있습니다. 어떤 도움이라도 대단히 감사합니다.
답변
DFS :
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.prepend( currentnode.children );
//do something
}
BFS :
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.append( currentnode.children );
//do something
}
이 둘의 대칭은 매우 시원합니다.
업데이트 : 지적했듯이 take_first()목록의 첫 번째 요소를 제거하고 반환합니다.
답변
아직 방문하지 않은 노드를 보유 하는 스택 을 사용합니다 .
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
답변
부모 노드에 대한 포인터가 있으면 추가 메모리없이 할 수 있습니다.
def dfs(root):
node = root
while True:
visit(node)
if node.first_child:
node = node.first_child # walk down
else:
while not node.next_sibling:
if node is root:
return
node = node.parent # walk up ...
node = node.next_sibling # ... and right
자식 노드가 형제 포인터를 통하지 않고 배열로 저장된 경우 다음 형제를 다음과 같이 찾을 수 있습니다.
def next_sibling(node):
try:
i = node.parent.child_nodes.index(node)
return node.parent.child_nodes[i+1]
except (IndexError, AttributeError):
return None
답변
스택을 사용하여 노드 추적
Stack<Node> s;
s.prepend(tree.head);
while(!s.empty) {
Node n = s.poll_front // gets first node
// do something with q?
for each child of n: s.prepend(child)
}
답변
“스택 사용” 은 면담 질문에 대한 해답으로 작동 할 수 있지만 실제로 재귀 프로그램이 배후에서하는 일을 명시 적으로 수행하고 있습니다.
재귀는 프로그램 내장 스택을 사용합니다. 함수를 호출하면 함수의 인수를 스택으로 푸시하고 함수가 반환하면 프로그램 스택을 팝핑하여 반환합니다.
답변
biziclops에 대한 ES6 구현은 훌륭한 답변입니다.
root = {
text: "root",
children: [{
text: "c1",
children: [{
text: "c11"
}, {
text: "c12"
}]
}, {
text: "c2",
children: [{
text: "c21"
}, {
text: "c22"
}]
}, ]
}
console.log("DFS:")
DFS(root, node => node.children, node => console.log(node.text));
console.log("BFS:")
BFS(root, node => node.children, node => console.log(node.text));
function BFS(root, getChildren, visit) {
let nodesToVisit = [root];
while (nodesToVisit.length > 0) {
const currentNode = nodesToVisit.shift();
nodesToVisit = [
...nodesToVisit,
...(getChildren(currentNode) || []),
];
visit(currentNode);
}
}
function DFS(root, getChildren, visit) {
let nodesToVisit = [root];
while (nodesToVisit.length > 0) {
const currentNode = nodesToVisit.shift();
nodesToVisit = [
...(getChildren(currentNode) || []),
...nodesToVisit,
];
visit(currentNode);
}
}답변
PreOrderTraversal is same as DFS in binary tree. You can do the same recursion
taking care of Stack as below.
public void IterativePreOrder(Tree root)
{
if (root == null)
return;
Stack s<Tree> = new Stack<Tree>();
s.Push(root);
while (s.Count != 0)
{
Tree b = s.Pop();
Console.Write(b.Data + " ");
if (b.Right != null)
s.Push(b.Right);
if (b.Left != null)
s.Push(b.Left);
}
}
일반적인 논리는 루트에서 시작하여 노드를 스택으로 밀어 넣고 Pop () 및 Print () 값입니다. 그런 다음 자식이있는 경우 (왼쪽 및 오른쪽) 스택에 밀어 넣으십시오-먼저 오른쪽을 눌러 왼쪽 자식을 먼저 방문하십시오 (노드 자체를 방문한 후). stack이 비면 () 주문 전의 모든 노드를 방문하게됩니다.
