이해 깊이 우선 탐색 BST 주어진 표현으로

Question

,

/****************tree.h ***********************/ 
typedef void* (*ProcessItem)(void *, void *); 

---

/**************** BSTNode.c ************************/ 
typedef struct BinarySearchTreeNode{ 
    void *key; 
    void *value; 
    bool visit; // For traversals 
    struct BinarySearchTreeNode *parent; 
    struct BinarySearchTreeNode *left; 
    struct BinarySearchTreeNode *right; 
}Node; 

typedef struct Tree{ //BST 
    Node *root; 
    int size; 
}Tree; 
static void visitFunc(ProcessItem, Node *); 

---

학습의 일부로서, 다음 (C 코멘트)에 상세한 알고리즘이 대응 코드는 작성된 세 가지 DFS 탐색.

---

예약 주문 탐색

/* 
    Pre-order traversal of BST and Binary tree: Node -> Left -> Right 
    0) Assuming node pointer is pointing to root node, which is, not NULL. 

    1) Visit node, if not visited 

    2) From that node, 
    If left sub-tree exists, and 
    If root node of that left sub-tree never visted, 
    then traverse to root node of left sub-tree. 
    Go to step 1 and continue until a node (that has visted root of left sub-tree) or (that has no left sub-tree exists) 

    3) From that node, 
    If right sub-tree exists, and 
    It root node of right sub-tree not visited, 
    then traverse to root node of right sub-tree. 
    Go to step 1 and continue, until a node (that has visited root of right sub-tree) or (that has no right sub-tree exists). 

    4) We reach this step, because, 
    Either left/right sub-tree exist but visited 
      or 
    left and right sub trees does not exist 

    Reach parent node and go to step-1 for applying pre-order traversal on that node 

*/ 
static void preOrderTraverse(Node *n, ProcessItem action){ 

    if (n == NULL){ 
    return; // if tree is empty, then go back 
    } 

    Node *root = n;        // |Step-0 

    while(root != NULL){ 

    if(root->visit == false){ 
     visitFunc(action, root);     // |Step-1: Visit node, if not visited 
    } 

    if(root->left != NULL &&     // |Step-2: if left sub-tree exists, and 
     (root->left->visit == false)){   // |Step-2: If root node of that left sub-tree's never visted, 
     root = root->left;      // |Step-2: then traverse to root node of left sub-tree. 
     continue;        // |Step-2: Go-to step 1 
    } 

    if(root->right != NULL &&     // |Step-3: if right sub-tree exists, 
     (root->right->visit == false)){  // |Step-3: If root node of right sub-tree not visited, 
     root= root->right;      // |Step-3: then traverse to root node of right sub-tree. 
     continue;        // |Step-3: Go-to step 1 
    } 

    /* 
    If the instruction pointer points to below insruction, then that means, 
     Either left/right sub-tree exist but visited 
      or 
     left and right sub trees are empty 

    What can be done now? 
    Go to parent's tree root node and apply preOrderTraversal 
    */ 
    root = root->parent;      // |Step-4 Reach parent node. 

    } 
} 

---

후 주문 탐색

/* 
    Algorithm: Post-order traversal of BST and Binary tree: Left -> Right -> Node 

    0) Assuming node pointer is pointing to root node, which is, not NULL. 

    1) From that node, 
    If left sub-tree exists, and 
    If root node of that left sub-tree never visted, 
    then traverse to root node of left sub-tree. 
    Repeat step 1 until a node (that has visted root of left sub-tree) or (that has no left sub-tree exists) 

    2) From that node, 
    If right sub-tree exists, and 
    If root node of that right sub-tree never visted, 
    then traverse to root node of right sub-tree. 
    Go to step 1 and continue until a node (that has visited root of right sub-tree) or (that has no right sub-tree exists) 

    3) Visit that node, if not visited 

    4) We reach this step, because, 
    Either left/right sub-tree exist but all visited 
      or 
    left and right sub trees does not exist 

    Reach parent node and go to step-1 for applying post-order traversal on that node 

*/ 
static void postOrderTraverse(Node *n, ProcessItem action){ 

    if (n == NULL){ 
    return; // if tree is empty, then go back 
    } 

    Node *root = n;        // |Step-0 

    while(root !=NULL){ 

    while(root->left != NULL &&    // |Step-1: If left sub-tree exists, and 
      (root->left->visit == false)){  // |Step-1: If root node of that left sub-tree never visted, 
     root=root->left;       // |Step-1: then traverse to root node of left sub-tree. 
    } 

    if(root->right != NULL &&     // |Step-2: If right sub-tree exists, and 
     (root->right->visit == false)){   // |Step-2: If root node of that right sub-tree never visted, 
     root=root->right;      // |Step-2: then traverse to root node of right sub-tree. 
     continue; 
    } 

    visitFunc(action, root);     // |Step-3: Visit node, if not visited 

    /* 
     If the instruction pointer points to below insruction, then that means, 
     Either left/right sub-tree exist but all visited 
      or 
     left and right sub trees are empty 

    What can be done now? 
    Go to parent's tree root node and apply postOrderTraversal 
    */ 

    root = root->parent;      // |Step-4: Reach parent node. 
    } 
} 

---

에서 주문 통과

,321 visitFunc가 BSTNode.c에 정의되어 있으며 processItem 사용자로부터 오는 0

---

,

static void visitFunc(ProcessItem processItem, Node *node){ 

    if(node->visit == TRUE){ 
    return; 
    } 
    node->visit=true; 
    processItem(node->key, node->value); 
    return; 
} 

---

배경 :

그것은 꽤 분명하다, 즉, 위의 DFS 알고리즘 온라인에서 구할 수 있습니다. 하지만, 내 학습에 따라 이러한 알고리즘에 필요한 세부 수준이 누락되었습니다. 나는 이러한 세부 사항의 부족이 위의 알고리즘에서 다루어 졌다고 생각할 것이다 (C 주석에서). 제 (C 코멘트에서) 언급 한 알고리즘을 강조하고 parent 포인터가 아니라 명시 적 스택을 사용하여 탐색 코드를 대응

는

내 질문 :

1) 당신은 4 논리적 결함을 볼 수 있나요 3 가지 탐색 모두를위한 단계 알고리즘 및 코드?

2) 위의 코드에서 노드를 방문하기 전에 조건 확인이 필요합니까?

참고 : 탐색 알고리즘의 초급은

Answer 1

1)는 세 순회의 4 단계 알고리즘과 코드의 논리적 결함을 볼 수 있나요?

선주문 순회를 확인했습니다. 괜찮아 보인다.

그러나 Mohhem에서 언급했듯이 방문 필드는 처음에는 false로 설정 될 수 있지만 탐색 후에는 true로 설정됩니다. 그래서, 당신은 두 번째로 나무를 횡단 할 수 없을 것입니다.

일반적으로 트리 순회는 재귀 함수를 사용하여 수행되거나 반복 함수를 사용하려면 스택으로 푸시 및 팝해야합니다.

2) 위의 코드에서 노드를 방문하기 전에 조건 확인이 필요합니까?

예, 노드를 다시 방문하기 전에 노드가 방문되었는지 확인해야합니다. 그렇지 않으면 탐색이 잘못됩니다.

편집 -이 지점에 대한 추가 설명. 검사는 예약 주문 탐색을 위해이없는, 우리가 나무

 a 
    b c 
    d e 
f g 

그리고 조건이 있다고 가정 해 봅시다.

첫 번째 조건 인 if에 도달 할 때마다 첫 번째 a, b, d, f를 차례로 방문한 다음 계속합니다. 루트 = f에서 다음 if 조건에 도달하면 거짓이고 최종 조건은 root = root->parent에 도달합니다.

이제 루트 = d. 조건 검사가 없기 때문에 d가 다시 방문됩니다. 이것은 틀 렸습니다. 그런 다음 두 번째 조건으로 이동하여 f를 방문합니다. 다시 root = root->parent이고 루트 = d이고 d가 다시 인쇄됩니다.

따라서 트래버스가 잘못된 것을 알 수 있습니다.

Answer 2

분명히 재귀가 아니고 스택을 사용하지 않는 이진 트리 순회 함수가 필요합니다. (당신은 그 질문에서 명시 적으로 말하지 않지만, 귀하의 의견은 그것을 제안합니다.)

포스트 오더 탐색을 살펴 보겠습니다. (이 답변은 쉽게 다른 깊이 우선 순회 확장,하지만 쉬운 postorderis, 그래서 우리는 그냥 살펴 보겠습니다 수 있습니다.)

재귀 함수는 간단하다 :

이

typedef struct Node Node; 

struct Node { 
    int key; 
    Node *left; 
    Node *right; 
    Node *parent; 
}; 

void postorder_rec(const Node *nd, void (*func)(const Node *nd)) 
{ 
    if (nd) { 
     postorder_rec(nd->left, func); 
     postorder_rec(nd->right, func); 
     func(nd); 
    }; 
} 

이 기능은 가볍고 좋은 재귀 깊이를 갖습니다. 재사용 버전을 프로덕션 코드로 사용하지 않겠지 만 그런 코드에서는 트리를 균형있게 유지하여 트리 (따라서 재귀) 깊이가 20 인 노드를 약 1 백만 가지로 가질 수 있습니다.

노드에 visited 플래그를 추가 할 것을 제안했습니다. 이 방법은 규칙 위반이 트리의 상태를 변경하기 때문에 적합하지 않습니다. 이 상태를 순회하기 전에 다시 설정해야하지만 이렇게하려면 트리를 탐색해야합니다. 아야!

트리 루트의 상태에 따라 플래그를 "visited"또는 "unvisited"로 처리하는 것이 좋습니다. 그러나 어떤 이유 때문에 중간 또는 중간에서 순회를 중지하려는 경우 실패합니다 트래버스간에 새 노드를 추가하는 경우 이 방법은 신뢰할 수 없습니다. 게다가, 당신은 항상 각 노드에 여분의 플래그를 가지고 다닐 필요가 있습니다.

그러나 해결책이 있습니다. 트리 노드에 부모 링크가 있습니다. 이전에 방문한 노드에 대한 링크를 유지하고 다음을 기반으로 다음 위치를 결정할 수 있습니다.

• 이전 노드가 null 인 경우 시작하십시오.
• null 인 하위 노드를 방문하지 마십시오.그렇지 않으면 널 (null) 하위와 루트 노드의 상위 (널)를 구별 할 수 없습니다.
• 이전에 방문한 노드가 현재 노드의 부모 인 경우 :
      • 왼쪽 자식이있는 경우 다음을 방문하십시오.
      • 그렇지 않은 경우, 올바른 아이가있는 경우 다음을 방문하십시오.
      • 그렇지 않으면 함수를 호출하고 부모로 돌아갑니다.
• 이전에 방문한 노드가 현재 노드의 왼쪽 자식 인 경우 :
      • 올바른 자식이있는 경우 다음을 방문하십시오.
      • 그렇지 않으면 함수를 호출하고 부모로 돌아갑니다.
• 이전에 방문한 노드가 현재 노드의 오른쪽 자식 인 경우 :
      • 함수를 호출하고 부모로 돌아갑니다.
• 노드가 null 인 경우 중지 – 루트의 상위 노드까지갔습니다.

이러한 조건은 간단하고 기능은 다음과 같습니다 수 있습니다

void postorder_iter(const Node *nd, void (*func)(const Node *nd)) 
{ 
    const Node *prev = NULL; 

    while (nd) { 
     const Node *curr = nd; 

     if (prev == nd->parent && nd->left) { 
      nd = nd->left; 
     } else if (prev != nd->right && nd->right) { 
      nd = nd->right;    
     } else { 
      func(nd); 
      nd = nd->parent; 
     } 

     prev = curr; 
    } 
} 

있는 그대로 반복 기능 – 재귀 함수가 간단하고 연결이 필요하지 않습니다에 대한 실질적인 혜택이 없다 노드에있는 부모에게.

그러나 이러한 기능은 탐색의 상태를 유지하는 반복자에 염기로서 사용될 수있다 : 여기

typedef struct PostIter PostIter; 

struct PostIter { 
    const Node *nd; 
    const Node *prev; 
    int count; 
}; 

const Node *postorder_next(PostIter *iter) 
{ 
    if (iter->nd == NULL) return NULL; 

    if (iter->count) { 
     (iter->prev) = iter->nd; 
     iter->nd = iter->nd->parent; 
    } 

    while (iter->nd) { 
     const Node *prev = iter->prev; 
     const Node *nd = iter->nd; 

     if (prev == nd->parent && nd->left) { 
      iter->nd = nd->left; 
     } else if (prev != nd->right && nd->right) { 
      iter->nd = nd->right;    
     } else { 
      iter->count++; 
      return nd; 
     } 

     iter->prev = nd; 
    } 

    return NULL; 
} 

, 반복 버전에서 로컬 변수에 의해 기술 된 탐색의 상태 , iterator 구조체에 번들로 제공됩니다. 함수를 호출하는 대신 함수에서 반환합니다. count은 다소 복잡하지만 반복기가 이미 고급 상태인지 여부를 함수가 알 수 있도록해야합니다. 즉, 첫 번째 호출에서는 상위 항목으로 이동하지 않습니다.

이제이 같은 반복자 사용할 수 있습니다 다른 곳에 정의해야합니다 콜백 함수를 제공의

PostIter iter = {head}; 

while (postorder_next(&iter)) { 
    printf("%d -> ", iter.nd->key); 
} 
puts("nil"); 

를 대신 이제 루프 본문, 어떤 수의에 방문 코드를 넣을 수 있습니다 물론, 루프 외부에서 선언 된 액세스 변수. travesal 코드는 복잡해졌지만 이제는 호출 코드가 훨씬 간단 해졌습니다.

선주문 및 주문 처형을위한 반복 코드 작성은 독자의 연습 문제로 남겨 둡니다. :)