트리를 탐색하여 각 노드와 그 위치를 인쇄하십시오.

Question

이미 이진 트리 (inorder, postorder 등)를 트래버스하는 방법을 알고 있습니다. 그러나 문제는 트리를 통과하여 노드와 위치를 인쇄하는 것입니다. 이것은 각 노드마다 키와 위치를 인쇄해야 함을 의미합니다. 어떻게 이런 것들을하는 알고리즘을 실제로 구현할 수 있습니까?

Answer 1

(Java 또는 의사에)의 당신이

void TraverseTree(Node node) 
{ 
    System.out.println("Key: " + node.Key); // print key 
    System.out.println("Position: " + node.Position); // print position 
    System.out.println(); // print empty row 

    TraverseTree(node.Left); 
    TraverseTree(node.Right); 
} 

재귀 탐색 방법 (전순 깊이 우선 탐색)가 있다고 가정 해 봅시다 그리고 당신은 호출하여 시작 :

TraverseTree(root); 

출력이됩니다 트리를 가로 지르도록 선택한 방법에 따라 순서가 정해집니다. 깊이 우선 선주문, inorder, postorder ir breath-first.

void TraverseTree(Node node, int position) 
{ 
    System.out.println("Key: " + node.Key); 
    System.out.println("Position: " + position); // different position print 
    System.out.println(); 

    TraverseTree(node.Left, position + 1); // different calls 
    TraverseTree(node.Right, position + 1); 
} 

을 그리고처럼 호출하여 탐색을 시작합니다 :

열쇠는 항상 노드에 어딘가에 있어야한다, 당신은 그런 식으로 위의 방법을 확장하여 위치를 셀 수

TraverseTree(root, 0); // counting position from 0 
TraverseTree(root, 1); // counting position from 1 

을

그런 다음 위치는 트리를 탐색하는 방법에 따라 달라집니다.