목록을 사용하지 않고 이진 트리를 퍼팅합니다

StackOverflow https://stackoverflow.com/questions/685532

문제

바이너리 트리의 가능한 모든 순열을 생성하기위한 알고리즘을 찾아야하며 목록을 사용하지 않고 그렇게해야합니다 (이는 트리 자체가 목록으로 변환 할 수없는 의미와 구속을 전달하기 때문입니다). 높이가 3 이하의 나무에 맞는 알고리즘을 찾았지만 높이가 더 높아질 때마다 높이 당 한 세트의 가능한 순열 세트가 느슨해집니다.

각 노드는 원래 상태에 대한 정보를 전달하므로 하나의 노드가 해당 노드에 대해 가능한 모든 순열이 시도되었는지 확인할 수 있습니다. 또한 노드는 날씨에 대한 정보를 전달하거나 '교체'되지 않았습니다. 즉, 하위 트리의 가능한 모든 순열을 본 경우. 트리는 왼쪽 중심이되므로 오른쪽 노드는 항상이 알고리즘에 대해 덮을 필요가없는 경우를 제외하고는 잎 노드 여야하지만 왼쪽 노드는 항상 잎이나 분기입니다.

현재 사용하고있는 알고리즘은 다음과 같이 설명 할 수 있습니다.

if the left child node has been swapped
      swap my right node with the left child nodes right node
      set the left child node as 'unswapped'
  if the current node is back to its original state
      swap my right node with the lowest left nodes' right node
      swap the lowest left nodes two childnodes
      set my left node as 'unswapped'
      set my left chilnode to use this as it's original state
      set this node as swapped
      return null
  return this; 
else if the left child has not been swapped
  if the result of trying to permute left child is null
     return the permutation of this node
  else 
     return the permutation of the left child node
if this node has a left node and a right node that are both leaves
   swap them
   set this node to be 'swapped'

알고리즘의 원하는 동작은 다음과 같습니다.

            branch
             /    |
       branch     3
         /   |
   branch    2
   /     |
  0      1


            branch
             /    |
       branch     3
         /   |
   branch    2        
   /     |
  1      0           <-- first swap



            branch
             /    |
       branch     3
         /   |
   branch    1         <-- second swap
   /     |
  2      0



            branch
             /    |
       branch     3
         /   |
   branch    1         
   /     |
  0      2   <-- third swap


            branch
             /    |
       branch     3
         /   |
   branch    0   <-- fourth swap        
   /     |
  1      2

등등...

도움이 되었습니까?

해결책

구조는 순열에 완전히 적합하지 않지만 왼쪽 중심이라는 것을 알고 있으므로 도움이되는 몇 가지 가정을 할 수 있습니다.

나는 당신과 비슷한 방식으로 그것을 작업하려고 시도했고, 나는 당신이 충분하지 않은 이진 정보 (교체 여부) 만 있다는 사실에 항상 잡혔습니다. 네 잎의 경우 4 개가 있습니다! (24) 가능한 조합이지만, 교환 상태 정보를 저장하기위한 3 개의 분기 (3 비트, 8 개의 가능한 조합) 만 있습니다. 이 정보를 저장할 장소가 없습니다.

그러나 트리를 통과하는 트래버서를 작성하고 잎의 수를 사용하여 필요한 스왑 수를 결정한 다음 나무 자체에 남겨 두는 대신 체계적으로 스왑을 통과 할 수 있습니다.

같은 것

For each permutation
   Encode the permutation as a series of swaps from the original
   Run these swaps on the original tree
   Do whatever processing is needed on the swapped tree

그것은 당신의 응용 프로그램에 적합하지 않을 수도 있지만, 당신은 당신이하는 방식으로 왜 그것을 해야하는지에 대한 많은 세부 사항을 제공하지 않았습니다. Factorial (순열 수)이 지수 ( "교체 된"비트 수)보다 빠르게 증가하기 때문에 지금은 단순히 작동하지 않습니다. 8 개의 잎이 있다면 총 15 비트에 7 개의 가지와 8 개의 잎이 있습니다. 8 개의 잎의 40320 순열은 15 비트의 32768 개만 있습니다. 수학적으로, 당신은 단순히 순열을 나타낼 수 없습니다.

다른 팁

트리의 모든 항목 목록을 작성하는 데 무엇이 문제입니까? 생성 수단을 사용하여 가능한 모든 주문을 구축 한 다음 트리 구조로 다시 맵핑하십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top