2016-07-26 1 views
0

이진 검색 트리를 코딩하고 노드를 삭제하는 함수를 만들었습니다. 일반적으로 두 개의 입력 매개 변수가 있습니다. 첫 번째는 삭제되어야하는 객체를 가리키는 포인터이고 두 번째는 이진 검색 트리의 루트에있는 점입니다.포인터를 유효하지 않게 설정하는 방법은 무엇입니까?

노드가 잎인 "가장 쉬운"것 외에도 기본적으로 모든 사례가 작동합니다.

내 코드는 삭제해야 할 노드의 내용을 0으로 설정하지만 여전히 참조가 있으며 트리에 표시됩니다.

* p는 삭제해야하는 요소입니다.

* pBaum은 트리의 루트를 가리 킵니다.

* p-> right 및 * p-> left는 * p의 오른쪽 및 왼쪽 하위 트리에 대한 포인터입니다.

* p-> conten은 * p의 값입니다. 잎의 경우

내 코드 :

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
     printf("%d Ist Blatt \n", p->content); 
     free(p); 
     return pBaum; 
     } 

Basicly 내가 "은"포인터 * P는 말할 필요는 지금부터 무효가. 그러나 나는 적절한 해결책을 찾을 수 없습니다. 어쩌면 너희들도 도울 수있을거야.

편집 : 좋아, NULL로 부모 포인터를 설정하려면 자체적으로 시도했다.

struct tnode* danglingPointerFix (struct tnode *p, int nodtodelete) 
{ 
if((p->right)->content = nodtodelete) 
    { 
     p->right = NULL; 
     return 0; 
    } 
    if((p->left)->content = nodtodelete) 
    { 
     p->left = NULL; 
     return 0; 
    } 
} 

struct tnode *searchnode(struct tnode *p, int nodtodelete) 
{ 
if (p == NULL) 
{ 
    printf("Baum ist leer oder Element nicht vorhanden \n"); 
    return 0; 
} 
if (p -> content == nodtodelete) 
{ 
    return p; 
} 
if (p->content < nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode (p->right, nodtodelete); 
} 
if (p->content > nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode(p->left, nodtodelete); 
} 
} 

그러나 저는 segfaulting을 사용하고 있습니다. 어쩌면 어딘가에서 볼 수 있습니다. 제 의견으로는이 솔루션이 작동해야합니다.

+2

포인터를 NULL로 설정하는 것이 실행 가능한 옵션이 아닌 이유가 있습니까? 그러나 아마도 당신은 잘못된 방식으로보고 있습니다. 일반적으로 이와 같은 트리를 유지할 때 왼쪽 노드와 오른쪽 노드의 포인터를 설정하여 더 이상 삭제 된 노드를 참조하지 않게됩니다. –

+1

'p '에 대한 참조를 잊어 버리지 않습니까? –

+0

0XDEADBEEF가 때때로 포인터를 유효하지 않은 것으로 표시하는 데 사용됩니다. – monkeyStix

답변

0

당신은 삭제할 잎을 가리키는 부모 노드를 찾을해야합니다. 발견되면 부모의 left 또는 right 포인터를 NULL으로 설정해야합니다. 같이한다

그래서 삭제 :

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
      // This is a leaf --> It may be deleted 
      deleteNodeInParent(pBaum, p); 

      printf("%d Ist Blatt \n", p->content); 
      free(p); 
      return pBaum; 
     } 

그런 다음 당신은 deleteNodeInParent를 구현해야합니다. left == p 또는 right == p인지 여부를 확인하고 그럴 경우 - NULL으로 설정하고 돌아 오는 것을 제외하고는 현재 검색 기능과 매우 비슷합니다. 같은

뭔가 : 말했다

void deleteNodeInParent(struct tnode *p, struct tnode *pDeleted) 
{ 
    if (p == NULL) 
    { 
     printf("Baum ist leer oder Element nicht vorhanden \n"); 
     return; 
    } 
    if (p->left == pDeleted) 
    { 
     p->left = NULL; 
     return; 
    } 
    if (p->rigth == pDeleted) 
    { 
     p->rigth = NULL; 
     return; 
    } 

    if (p -> content == pDeleted->content) 
    { 
     // Can only happen for head - just return 
     return; 
    } 
    if (p->content < pDeleted->content) 
    { 
     deleteNodeInParent(p->right, pDeleted); 
     return; 
    } 
    if (p->content > pDeleted->content) 
    { 
     deleteNodeInParent(p->left, pDeleted); 
     return; 
    } 
} 

, 난 당신이 부모에 대한 포인터와 구조체 TNODE를 확장하는 경우가 훨씬 쉬울 것이라 생각합니다.

+0

내 자신의 꽤 simliar 아마 무언가를 시도했습니다 내 danglingPointerFix 메서드에서 세그먼트 오류를 ​​볼 수 있습니다. –

+0

@RobinSchmidt - 글쎄, 당신은'danglingPointerFix' 함수에서'=='테스트 대신'='할당을합니다. 그게 세분화 오류로 연결되는지 여부는 확실하지 않습니다. 하지만 먼저 수정하십시오. – 4386427

+0

@RobinSchmidt - 또한'if ((p-> right) -> content ...'를하기 전에'p-> right == NULL'을 검사해야합니다.'p'가'NULL ' ''p-> left'와'p-> right' 둘 다'NULL' 일 수도 있습니다. – 4386427

1

리프 노드를 해제했지만 부모 노드는 여전히 매달린 포인터를 유지합니다. 그것을 해결

한 가지 방법은 다음과 같은 기능을 추가하는 것입니다

struct tnode *deleteLeftNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->left, pBaum); 
     parent->left = NULL; 
    } 
    return pBaum; 
} 

struct tnode *deleteRightNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->right, pBaum); 
     parent->right = NULL; 
    } 
    return pBaum; 
} 
+0

나는 내 자신의 꽤 simliar 아마 무언가를 시도 했어 세그먼트 결함을 볼 수 있습니다. –

+1

오른쪽 노드가 NULL이고 왼쪽 노드를 제거하려고하면 충돌합니다. 비교를하기 위해서는'=='이 필요합니다. (단일'='는 할당 임). 보십시오 (p-> 오른쪽 && (p-> 오른쪽) -> 콘텐츠 == nodtodelete)' –