Post-order traversal이 정렬 된 결과를 제공하도록 이진 트리를 구성하십시오.

Question

바이너리 검색 트리에서 In-order traversal (VISIT LEFT, VISIT ROOT, VISIT RIGHT)이 정렬 된 결과를 제공한다는 것을 알고 있습니다. 하지만 이진 트리에서 Post-order traversal (VISIT LEFT, VISIT RIGHT, VISIT ROOT)을 수행해야하며, 결과는 정렬 된 값을 제공해야합니다.

이를 달성하기 위해 내 바이너리 트리를 어떻게 구성해야합니까?

Answer 1

루트가 마지막으로 방문되므로 가장 큰 항목을 포함해야합니다. 왼쪽 하위 트리는 오른쪽 하위 트리보다 먼저 방문하기 때문에 왼쪽 하위 트리의 모든 항목은 오른쪽 하위 트리의 항목보다 작아야합니다.

이와 같이 트리를 구성하려면 다음과 같이 진행할 수 있습니다. 루트보다 큰 항목을 삽입하면 해당 항목이 새 루트가됩니다. 루트보다 작지만 왼쪽 하위 트리의 루트보다 큰 항목을 삽입하는 경우 오른쪽 하위 트리에 삽입하십시오. 그렇지 않으면 왼쪽 하위 트리에 삽입하십시오.

Answer 2

당신은 트리의 각 노드에서 다음을 확인해야합니다 : 노드에서

• 값이 왼쪽 서브 트리와 오른쪽 서브 트리에있는 모든 값보다 커야합니다.
• 왼쪽 하위 트리의 값은 하위 트리의 값보다 작은 이어야합니다.
  1. 트리 비어 삽입 새로운 노드 인 경우 트리 구조가

  struct tree 
  
  { 
  
  int data; 
  tree * left; 
  tree *right; 
  
  tree(int n) // constructor 
  
  { 
       data = n; 
       left = right = NULL; 
      } 
  }; 
  

  알고리즘은 어디

Answer 3

이 서브 루틴 트리에 삽입된다.
2. 새 노드의 데이터가 루트 노드의 데이터보다 큰 경우 새 노드를
트리의 루트로 만듭니다.
3. 트리의 왼쪽 하위 트리에 새 노드를 삽입하십시오.

tree * insert(tree *root,int n) 

{ 

if(root == NULL) 
{ 

    root = new tree(n); 

    return root; 
} 
else 
{ 

    if(n > root -> data) 
    { 
     tree * t = new tree(n); 

     t -> left = root; 

     return t; 
    } 

    else 


    { 

     root -> left = insert(root -> left,n); 

     return root; 
    } 
    } 
} 

Answer 4

currently accepted answer은 좋은 온라인 알고리즘을 제공합니다. 좀 더 간단한 해결책 --- 온라인이 아니기 때문에 속임수를 쓰는 것 ---은 부모 포인터에 정렬 된 링크 된 목록을 저장하는 것입니다.

즉, 데이터 정렬; 가장 큰 항목을 루트에두고 그 하위 트리 중 하나를 비우고 남은 n-1 항목의 순서가 정렬 된 트리를 다른 하위 트리로 재귀 적으로 구성합니다.

트리의 높이는 n이고, 단일 리프는 목록의 머리이고 루트는 가장 끝에있는 요소입니다. 리프에서 루트까지 트리를 따라 가면 요소는 증가하는 시퀀스를 형성 할 것이고이 경로는 후행 순회와 정확히 일치 할 것입니다.

Answer 5

삭제

• 는 루트를 삭제
• 다른 아버지에게 아들을 연결하는 하나의 아들이있는 경우 잎 있다면, 정기적으로
• 을 삭제 오른쪽 아들로 교체 한 후 왼쪽를 연결할 오른쪽 하위 트리에서 가장 왼쪽에있는 꼭지점을 선택합니다.예를 들어

:

7               6 
/\              /\ 
    3 6    =========DELETING 7 ============>   4 5 
/\/\             / 
1 2 4 5             3 
                  /\ 
                  1 2