바이너리 트리를 지그재그 명령으로 변환하여 이중 연결 목록

Question

Ii에 문제가 있습니다. 바이너리 트리를 지그재그 형식으로 이중 연결 목록으로 변환해야합니다.

DLLNode* ConvertBTToZigZgDLL(Node* root) 
{ 
    DLLNode* start=createDLLNode(root->data); 
    DLLNode* tail=start; 
    Stack<Node> stack1, stack2; 
    stack1.push(root->left); 
    stack1.push(root->right); 
    while(!stack1.Empty() || !stack2.Empty()) 
    { 
    while(stack1.HasElement()) 
    { 
     Node* temp=stack1.Pop(); 
     stack2.push(temp->right); 
     stack2.push(temp->left); 
     tail=Attach(tail,createDLLNode(temp->data)); 
     tail=tail->next; 
    } 
    while(stack2.HasElement()) 
    { 
     Node* temp=stack2.Pop(); 
     stack1.push(temp->left); 
     stack1.push(temp->right); 
     tail=Attach(tail,createDLLNode(temp->data)); 
     tail=tail->next; 
    } 
    } 
    return start; 

} 여기 TimeComplexity O (N), N은 주어진 이진 트리의 노드에는이다 :

 Given BT: 
       [1] 
      [2]     [3] 
     [4]  [5]   [6]  [7] 
    [8] [9] [10] [11] [12] [13] [14] [15]
 

ZigZag order of BT in DLL: 
     [1] [3] [2] [4] [5] [6] [7] [15] [14] [13] [12] [11] [10] [9] [8] 

여기 내 의사입니다.

    DLLNode* Attach(DLLNode* source, DLLNode* dest) 
    { 
    source.Next=dest; 
    dest.prev=source; 
    return source; 
    } 

    DLLNode* CreateDLLNode(int data) 
    { 
    DLLNode* res=malloc(sizeof(struct DLLNode)); 
    res->data=data; 
    res->prev=NULL; 
    res->next=NULL; 
    return res; 
    }

난 내 코드의 논리에서 무엇이 잘못되었는지 을 알고 싶은 모든.

친구 중 한 명은 위의 코드가 작동하지 않으며 잘못되었다고 말하고 있습니다. 내 논리가 실패 할 어떤 유스 케이스도 찾을 수 없었다. (널 체크/널/빈 노드 제외)

그냥 내 코드의 논리를 확인하고 알려줘.

내 논리는 간단합니다 : 2 스택을 사용하십시오. stack1에서는 항상 왼쪽 자식을 먼저 누른 다음 오른쪽 자식을 밀어 넣고 stack2에서 항상 오른쪽 자식을 먼저 푸시하고 자식을 두 번째 왼쪽으로 푸시합니다. 처음에 stack1을로드하고 stack1은 비어 있지 않은 pop이고 stack2에서 해당 오른쪽/왼쪽 자식 노드를 푸시합니다. 위의 예제에서 스택 상태는 s1-B [2,3] T s2-B [7,6,5,4] T s1-B [8,9,10,11,12,13,14, 15] T B- 스택 하단 T- 스택 상단. Pls 다시 확인하십시오. 감사.

Answer 1

알고리즘 : stack2 포함하면서

이

는,이 스택은 오른쪽이 왼쪽으로 방문 할 수있는 수준의 노드를 포함하는 데 사용됩니다 stack1를 사용하는 대신 하나의 FIFO 큐의 수정 된 BFS 알고리즘을 사용하여 왼쪽에서 오른쪽으로 방문해야하는 노드

목록은 루트 노드로 초기화되며 루트에 가장 가까운 첫 번째 수준은 stack1에 저장됩니다. 따라서 첫 번째 패스는 stack1을 통해 첫 번째 레벨을 적절한 순서로 가져옵니다.

stack1의 요소가 올바른 순서로 저장되었다고 가정하면 레벨 N에 대해 stack1에서 노드를 당겨서 오른쪽에서 왼쪽 순서로 처리 할 수 ​​있습니다. 이렇게 처리 된 각 노드에 대해 하위 트리는 첫 번째 오른쪽에있는 stack2에 저장되고 그 다음 왼쪽에 저장됩니다. 이렇게하면 노드 목록이 이고 레벨 N + 1의에서 stack2까지 왼쪽에서 오른쪽으로 순서가 지정됩니다. while 루프는 레벨 N에 노드가 더 이상 없을 때 완료됩니다.이 시점에서 stack2에서 노드를 추출하면 레벨 N + 1의 모든 노드가 왼쪽에서 오른쪽 순서로 검색됩니다.

반대로 각 왼쪽에서 오른쪽 레벨에서 stack2에서 노드를 가져 오는 경우 하위 노드를 왼쪽으로 stack1에 저장 한 다음 오른쪽으로 이동하여 오른쪽에서 왼쪽 순서로 다음 반복에서 꺼낼 때 .

그래서 기본적으로 알고리즘은 건전한 것으로 입증되었습니다. 이제 그 구현이 보장되지 않습니다.특히 스택에 모든 NULL 포인터를 추가하는 것입니다. 즉, NULL 포인터를 검색하고이를 통해 읽으려고합니다.

Answer 2

이것은 이미 다른 질문에서 다루고 있습니다.

this stackoverview set of answers을 참조하십시오.