PGR21.com
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
Date 2010/06/11 01:27:17
Name ROMANMAX
Subject 자료구조 고수분 이것좀 한번만 봐주세요...
자료구조 레포트중인데요 이진트리의 원소 삭제 소스를 짜고있는데..

책에 있는 알고리즘을 토대로 짜고있는데요....

지금 밑에 소스는 책의 알고리즘을 그대로 옮겨본거거든요..

그런대 이 알고리즘으로 트리 삭제를 할수있는건가요????

저도 인터넷보고 공부좀 하고그랫는데..

그걸로는 이해가 되는데

이알고리즘을 가지고 재귀함수를 사용해서 꼭 만들어오래요.;;;

다른건 다맞는것 같은데 마지막에 자식 노드가 2개일때가..

좀..;;;

maxNode함수를 짜야될것 같은데

조언좀 부탁드립니다

treeNode* deleteBst(treeNode* root, char x)
{
        treeNode* p;
        treeNode* q;
        treeNode* parent;
        p=root;

        if(p==NULL)
                return 0;

        if(p->left==NULL && p->right==NULL){
                if(parent->left==p)
                        parent->left=NULL;
                else
                        parent->right=NULL;
        }
        else if(p->left==NULL || p->right==NULL){
                if(p->left==NULL){
                        if(parent->left==p)
                                parent->left=p->left;
                        else
                                parent->right=p->left;
                }
                else{
                        if(parent->left==p)
                                parent->left=p->right;
                        else
                                parent->right=p->right;
                }
        }
        else if(p->left!=NULL&& p->right!=NULL){

        q=maxNode(p->left);
        p->key=q->key;
        deleteBst(q,q->key);

        }

}

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
10/06/11 09:33
수정 아이콘
else if(p->left==NULL || p->right==NULL){
if(p->left==NULL){
이부분이
else if(p->left==NULL || p->right==NULL){
if(p->left != NULL){
이렇게 되어야 하는 거 아닌가요?

이부분에서 막혀서 진도가 안나가네요.
10/06/11 10:02
수정 아이콘
if(p->left != NULL)
이라는 가정하에 maxNode는 그 아래에 있는 가장 큰 값을 찾아 내면 되는 거군요

treeNode* maxNode(treeNode* start)
{
if(start->right == NULL)
return start;

return maxNode(start->right);


이렇게 하시면 되겠네요.

maxNode 함수를 만드는 건 어려운 게 아닌데 저 알고리즘에서 아이온님이 얘기하신 [첫째, 왼쪽 subtree에서 "제일 큰 노드"의 값을 현재 노드에 카피한다. 둘째, 이 제일 큰 노드인 q를 지워준다] 를 이해하는 게 관건이군요.
ROMANMAX
10/06/11 13:18
수정 아이콘
그러개요..아이온님 댓글 지우셧네..

저도 저핵심이라고 주신 댓글보면서 계쏙 고민하고 고민하면서 짜고있엇는데...

하여튼 빈터님 아이온님 답변 감사합니다
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
83855 lx3 새거 구입 질문입니다. [7] WestSide1340 10/06/11 1340
83852 모델링(수학)관련 질문입니다. [4] LastStage1949 10/06/11 1949
83851 철권질문 [5] 몽키D드래곤1873 10/06/11 1873
83850 ㅠㅠ 여린입천장... [4] mangyg2610 10/06/11 2610
83849 월컵때 모텔들 꽉 차나요? [22] SOD매직미러호3467 10/06/11 3467
83848 동영상 편집(?)에 관한 질문입니다. [5] Psy_Onic-0-1439 10/06/11 1439
83847 프로야구 예매 관련 질문입니다. [2] DJ`Tukutz1546 10/06/11 1546
83846 간단한 영어문장 해석 질문입니다. [1] The_Mineral1367 10/06/11 1367
83845 [건의]월드컵 게시판좀 만들어주세요. [3] 엄마,아빠 사랑해요2164 10/06/11 2164
83844 괜찮은 공대인들 커뮤니티 없나요? [6] 탈퇴한 회원4070 10/06/11 4070
83843 매트랩교육관련문의 [1] Jn_Bbo)1677 10/06/11 1677
83842 컴퓨터 견적내려는데 너무어렵네요.ㅜㅜ 도와주세요 [4] 행복하게살자1735 10/06/11 1735
83841 여름철 티셔츠 어디서 구매하시나요? [1] tiZtoM1684 10/06/11 1684
83840 이 소심한 성격 어떡할까요 [5] JeanS1933 10/06/11 1933
83839 시계 추천 부탁드립니다^^ [15] 동글이2063 10/06/11 2063
83837 서울에 토익학원 괜찮은곳좀 가르켜 주세요 [2] Erehwon1633 10/06/11 1633
83836 자료구조 고수분 이것좀 한번만 봐주세요... [5] ROMANMAX2058 10/06/11 2058
83835 연예인들이 욕먹을거 감수하고 공익 가는 이유가 뭔가요? [43] 방어운전5482 10/06/11 5482
83833 똑딱이는 Lx3 가 진리인가요? [13] WestSide1801 10/06/11 1801
83832 만화책을 싸게 살수 있는곳이 있을까요? [14] 핸드레이크3703 10/06/11 3703
83831 MS/MS 스펙트럼 그래프로 sequence 구하는 법을 모르겠습니다. [1] 크로노너트1872 10/06/11 1872
83830 월드컵질문 [9] 몽키D드래곤1671 10/06/11 1671
83829 피지알 화면 궁금한점입니다. [5] C.P.company1943 10/06/11 1943
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로