디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

시험시간에 교수님께 배운 코드인데 올려도 될려나..2진트리

밥오(121.139) 2009.11.05 22:02:42
조회 102 추천 0 댓글 1

// SearchTree.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"

struct Node
{
 int key;
 //int recidx;           //<record가 있는 위치에 대한 정보
 Node *left , *right;
};

//이진트리에서 x라는 키값을 가지는 있는 노드를 찾는다.
// t                 :root node
// x                 :찾고자 하는 키값
// 찾은 경우에는 해당 노드의 포인터를 그렇지 않은 경우는 NULL 반환
Node *searchTree(Node *t, int x)
{
 if ( t == NULL) return NULL;
 if ( t->key == x ) return t;
 if ( t->key < x) return searchTree(t->right, x);
 return searchTree(t->left,x);
}

// 재귀를 사용한 노드 삽입
// 특징 : 반환값이 존재한다.
Node *insertTreeRecursive(Node *t, int x)
{
 // case1 : 루트값이 NULL인 경우
 if ( t == NULL )
 {
  //root  = insertTree(root-<NULL 이라면 , 10)
  // ↑
  //NULL-10-NULL
  Node *r = new Node;
  //인스턴스 값이 저장한 곳이 있다. 때문에 포인터는 해당 인스턴스를 가리킬 뿐 값이 없으므로 New로 인스턴스로 변환
  r->key= x;
  r->left= r->right = NULL;
  //아무것도 가리키지 않고 있다.
  return r;
 }

 //case2 :루트값과 비교할 수 있는 경우
 if ( x < t->key ) t->left = insertTreeRecursive (t->left,x);
 else t->right = insertTreeRecursive(t->right,x);

 return t;
}

//재귀를 사용한 노드 삽입
//이중포인터를 사용한다.

void insertTreeRecursiveA(Node **t, int x )
{
 if ( *t == NULL)
 {
  *t = new Node;
  (*t)->key = x;
  (*t)->left = (*t)->right = NULL;
  return;
 }
 if( x < (*t)->key) insertTreeRecursiveA(&(*t)->left,x);
 else insertTreeRecursiveA(&(*t)->right,x);

}


void insertTree(Node **root, int x)
{
 Node *r = new Node;
 r->key = x;
 r->left= 0;
 r->right = 0;
#if 0
 if(*root == 0) {*root=r; return;}
 Node *p =0;
 Node *tmp = *root;
 while(tmp)
 {
  p = tmp;
  if(x < tmp->key) tmp = tmp->left;
  else tmp = tmp->right;
 }

 if(x<p->key) p ->left = r;
 else p->right =r;
#else
 while (*root)
 {
  if(x<(*root)->key) root = &(*root)->left;
  else root = &(*root)->right;
 }
 *root  =r;
#endif
}


void deleteTree(Node **root, int x)
{
 // 1)삭제할 노드를 찾는다.
 Node **r = root;
 while( *r )
 {
  if((*r)->key == x )break;
  if( x < (*r)->key ) r= &(*r)->left;
  else r = &(*r)->right;
 }
 if( *r==0) return;

 // 2)찾은 노드를 삭제한다.
 if( (*r)->left == 0 && (*r)->right == 0)
 {
  Node *s = (*r);
  *r = 0;
  delete s;
 }
 else if ((*r)->left == 0)
 {
  Node *s= (*r);
  *r = (*r) ->right;
  delete s;
 }

 else if ((*r)->right == 0)
 {
  Node *s =(*r);
  *r = (*r) ->left;
  delete s;
 }

 else
 {
  Node **s = &(*r)->right;
  while ((*s)->left) s=&(*s)->left;
  (*r)->key = (*s)->key;
  Node *p = (*s);
  *s = p->right;
  delete p;
 }
 
}

int _tmain(int argc, _TCHAR* argv[])
{
 int A[]={6,8,4,2,7,1,3,10,5,9,};
 Node *root = 0;

 for(int i=0 ; i<10; i++)
  insertTree(&root, A[i]);

 deleteTree(&root,6);

 for(int i=1; i<=10; i++)
 {
  Node *t = searchTree(root, i);
    if(t)
  printf("%d, %d %d\\n",t->key,(t->left)?t->left->key:0,
   (t->right)?t->right->key:0);
 }

  return 0;
}

추천 비추천

0

고정닉 0

0

댓글 영역

전체 댓글 0
등록순정렬 기준선택
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 힘들게 성공한 만큼 절대 논란 안 만들 것 같은 스타는? 운영자 24/06/10 - -
168093 방학동안 집에서 뒹굴다 오늘 학교를 갑니다. [1] 대학생(121.162) 10.01.26 79 0
168089 형들 아 진짜 급해 머야 이게 [18] 응?(124.199) 10.01.26 216 0
168086 백신은 돈주고 구입해야, SW회사도 산다능 [1] Vita500갤로그로 이동합니다. 10.01.26 138 0
168084 첫부팅때 ... 메인보드 로고뜰때부터 화면 깨지면 [2] ㅇㅇ(211.117) 10.01.26 84 0
168083 2009년 5월 기준 언어 점유율 [5] 야메떼♥갤로그로 이동합니다. 10.01.26 257 0
168082 옥션에서 안랩v3를 뿌리고 있다던데 [8] V3(58.238) 10.01.26 190 0
168081 SQL인젝션 [4] ㅇㅇ(211.117) 10.01.26 135 0
168079 ㅅㅂ............내가.. [2] McHello갤로그로 이동합니다. 10.01.26 72 0
168077 왜 강의유형은 항상 이론인가? [2] 더더더갤로그로 이동합니다. 10.01.26 99 0
168076 한빛미디어에서 책 세일한다 [7] ㅇㅇㅃ갤로그로 이동합니다. 10.01.26 179 0
168075 요새는 먹고살만 한가요?? 요새도 많이 힘든가요?? 프로그래밍... [4] 1212(59.7) 10.01.26 110 0
168074 형들은 DirectX 어떤책으로 공부했어?ㅠㅠ & 병특질문 [1] ㅇㅅㅇ(125.180) 10.01.25 201 0
168073 VPN에대해 아시는횽 질문좀요! [1] 이좆보행갤로그로 이동합니다. 10.01.25 92 0
168071 피자마시면서 콜라씹자능 [6] DMW(125.138) 10.01.25 127 0
168070 미안 크랙 공부의신 보고왔어 올릴게 jpg 로 [4] 옹이양갤로그로 이동합니다. 10.01.25 162 0
168069 64비트용 백신 괜찮은거 없나 [6] 박뮤탈갤로그로 이동합니다. 10.01.25 281 0
168066 알약은 바이러스 치료를 잘 못해 [2] 이모군(110.8) 10.01.25 147 0
168064 나도 학원 출신이다. [2] Q Lazzarus갤로그로 이동합니다. 10.01.25 222 0
168063 백신 없는 사람 V3 깔라능 [3] ㅇㅇㅃ갤로그로 이동합니다. 10.01.25 122 0
168062 솔직히 Si 프로그래머가 간지나 보임?? 굴삭기 운전수 가 간지나 보임? 99(203.229) 10.01.25 108 0
168061 C가 보이는 그림책처럼 보기 편한 C++책이 필요 합니다. [2] 책이필요해요(58.238) 10.01.25 119 0
168060 잘 안풀린다능 [5] DMW(125.138) 10.01.25 79 0
168058 병신들이 많아 큰일이다.. [5] 제로리플(118.36) 10.01.25 186 0
168057 프로그래밍 관련글은 아니지만 [2] MC the 백수갤로그로 이동합니다. 10.01.25 109 0
168056 크랙좆초보 [5] 옹이양갤로그로 이동합니다. 10.01.25 168 0
168054 네이버 검색목록 뜨게하는법좀 알려주세요 ㅠ ㅇㅀㄹㅇㅎ(114.200) 10.01.25 101 0
168053 형들 ATI 칩셋 드라이버 Windows Server 2008에는 못설치 [1] 클라리네이갤로그로 이동합니다. 10.01.25 72 0
168052 근데 대학원 붙으면 [2] 오사카(221.153) 10.01.25 109 0
168051 아 mfc 빡치네 [1] 유동컴갤로그로 이동합니다. 10.01.25 125 0
168050 저 Lua 하시는분 계시는지..? [6] 능글맏이(218.149) 10.01.25 124 0
168048 여행에서 돌아옴과 함께 질문 [1] MC the 백수갤로그로 이동합니다. 10.01.25 82 0
168044 Flex... [3] 모닝글로리(58.225) 10.01.25 180 0
168043 나 궁금한게 있어요 [5] ㅁㄵ(218.154) 10.01.25 99 0
168042 이제 개발에 회의감이 드네 [7] 기라(221.147) 10.01.25 174 0
168041 회의하다가 기운이 쪽 빠졌다. [2] 피로토스갤로그로 이동합니다. 10.01.25 155 0
168040 오랜만입니당! [1] ElectronixArts갤로그로 이동합니다. 10.01.25 37 0
168038 파이란을 봤는데 [7] Vita500갤로그로 이동합니다. 10.01.25 110 0
168037 역시 개발은 취미로 하는게 좋을 듯 [3] ㅇㅇㅃ갤로그로 이동합니다. 10.01.25 184 0
168035 심심한데 [8] 답변좀갤로그로 이동합니다. 10.01.25 101 0
168034 선언 없이 사용하는 임시 변수에 대해 어떻게 생각해? [8] ∫ 2t dt=t²+c갤로그로 이동합니다. 10.01.25 151 0
168033 ㅠㅠ 횽들 도움좀 [3] 테플갤로그로 이동합니다. 10.01.25 105 0
168032 휴~ 오늘 기분도 꿀꿀하군... [1] 엽기토깽이갤로그로 이동합니다. 10.01.25 70 0
168031 계절학기 성적 떴는데 [3] 롤리키드갤로그로 이동합니다. 10.01.25 117 0
168030 유리한은 봅니다 [3] Vita500갤로그로 이동합니다. 10.01.25 112 0
168029 c while문 도와주세요 [8] 첫방(116.39) 10.01.25 117 0
168027 여기서 리드웍스 엔진 이라고 아시는분 계시나요?? [2] 빠돌이(218.149) 10.01.25 605 0
168026 나 아이폰으로 게임만들껀데 맥북필요하냐능? [5] ^^(118.131) 10.01.25 191 0
168025 아싸 신난다~ 회사에서 아이폰 사준대. [4] 외계달팽갤로그로 이동합니다. 10.01.25 170 0
168024 자기소개서 쓰는데... [6] 아주아슬갤로그로 이동합니다. 10.01.25 110 0
168023 난 가장 궁금한게 있어 [1] 아오(221.147) 10.01.25 43 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2