2016-12-25 5 views
2

이 연습은 "algorithms in c++"에서 발췌 한 것입니다. 이와 같은 자유 트리가 있다고 가정합니다. enter image description here이진 트리에서 자유 트리 표현

첫 번째 질문 :이 무료 트리를 이진 트리로 나타낼 수 있습니까?

우리는 2 개 이상의 자식 노드를 가지고 있기 때문에이 자유 트리를 이진 트리 으로 표현할 수 없다고 생각합니다.

두 번째 질문 :이 자유 트리에서 몇 개의 정렬 된 트리를 나타낼 수 있습니까?

나는 그 질문을 이해할 수 없다. 순서화 된 트리를 생성하는 방법을 결정하기 위해 노드에 키가 없습니다.

+3

당신은 [바로 이진 트리 형제 왼쪽 아이]는 같은 어린이 1 인 임의의 수의 노드가있는 트리를 나타낼 수 (https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree). 따라서 두 개 이상의 자식이있는 노드가있는 것이 이진 트리를 자유 트리를 나타내는 것으로 거부하지 않는 이유입니다. –

+0

두 번째 질문은 자유 트리부터 시작하여 가장자리에 방향성을 추가하여 결과 트리가 유추 된 루트 트리라는 사실을 묻습니다. – templatetypedef

+0

답변 해 주셔서 감사합니다. 왼쪽 자식 오른쪽 형제 트리에 대해서는 몰랐습니다. 두 번째 질문의 경우, 정렬되지 않은 나무가 아닌 순서가 지정된 나무를 만들어야합니다 (뿌리를 낸 나무). –

답변

1

정확하게 질문을하면, 이진 트리로 트리를 표시하는 것입니다. 즉, 이진 트리의 데이터 구조를 사용하여 임의의 트리를 나타내는 것입니다. 더 구조적으로 말하자면, 임의적 인 트리를 2 진 트리에 주입식으로 매핑하는 방법이 필요합니다.

기술은 here; 기본 아이디어는 a의 자식 c_1,...c_n (두 개 이상일 수 있음)을 a의 왼쪽 자식이되는 c_1과 같이 임의로 선택한 자식으로 나타 내기위한 것입니다. c_1의 올바른 하위 항목으로 다음 자식 인 c_2이 저장됩니다. 등등. 즉, 각 노드에 대해 하나의 하위가 왼쪽 하위 트리에 저장되고 오른쪽 하위 트리가 항상 오른쪽 하위 노드를 선택하면 자식의 '대체 노드'의 '형제'가 저장됩니다. 접근법은 다음과 같이 스케치 될 수 있습니다. 상대적으로 좋지 않은 텍스트 표현에 대해서는 나와 함께 견뎌주십시오.

arbitrary tree 

     a 
/| | \ 
c_1 c_2 c_3 c-4 

binary tree 

    a 
/
c_1 
    \ 
    c_2 
     \ 
     c_3 
      \ 
      c_4 
+0

답변 해 주셔서 감사합니다. –