가장자리에서 이진 트리를 만드는 방법은 무엇입니까?

Question

나는 어떻게이에서 트리를 구성 할

parentId childId 
    e.g. 0 3 // means from node 0 to node 3 
    // 0 does not mean root of the tree. 

에서의 입력에서 이진 트리의 모든 모서리는 무엇입니까? 이 작업을 수행하는

Answer 1

한 가지 방법은 두 개의 패스에서이 작업을 수행하는 것입니다 :

1. 트리에서 모든 링크를 조립합니다.
2. 트리의 루트를 찾으십시오.

모든 링크를 어셈블하려면 각 노드의 ID (또는 ID가 모두 0 범위에 있다는 것을 알고있는 경우 적절한 크기의 거대한 배열)로 키 해시 테이블을 작성하는 것으로 시작할 수 있습니다. .. 일부 N 선택) N. 파일에서 행을 읽을 때마다 다음을 수행 할 수 있습니다.

1. 노드가 시작 및 끝점에서 지정한 ID로 이미 존재하지 않으면 해당 노드를 만들고 처음에는 왼쪽 및 오른쪽 포인터를 없는.
2. 두 번째 노드를 첫 번째 노드의 자식으로 추가합니다. (저는 바이너리 검색 트리가 아니라고 가정합니다. 따라서 자식의 순서는 중요하지 않습니다. 바이너리 검색 트리라면, 발견 한 것을 기반으로 적절한 자식 포인터를 설정할 수 있습니다).

루트 노드를 찾으려면 처음에는 트리의 모든 노드 인 루트 노드의 후보 노드 집합을 만들 수 있습니다. 지금까지 구축 한 노드를 반복 할 수 있습니다. 노드 v가 다른 노드 u의 자식 인 것을 알게 될 때마다 후보 v (후보 노드)의 집합에서 노드 v를 제거 할 수 있습니다. 당신이 끝나면, 당신은 가능한 모든 뿌리의 집합으로 남아있을 것입니다. 가장자리 목록이 실제로 이진 트리를 정의하는 경우이 노드는 하나의 노드가됩니다. 이진 트리의 포리스트를 정의하면 포리스트의 모든 트리의 루트를 되돌릴 수 있습니다.

전체적으로 O (n) 시간이 소요됩니다. 여기서 n은 가장자리 수입니다 (이진 트리의 가장자리 수가 노드 빼기 수이기 때문에 트리의 노드 수도).

원할 경우이 두 패스를 한 번에 굴릴 수 있습니다. 방금 발표하기 쉽도록 각기 다른 설명을했습니다.

희망이 도움이됩니다.

Answer 2

먼저 다음지도

는 이진 트리 인 경우에 귀하의 정보의 링크,지도를 통해 다음 iterage 연결된 노드
의 목록, 노드 ID의지도를 구축하고에서를 만들 파일의 누락 된 정보가 다음 줄에서 두 번째, 같은 순서로 항상 (첫번째 왼쪽)과 노드 당 두 행 형식으로

부모, leftChild, rightChild 또는
또는 왼쪽과 오른쪽이 있어야한다 .