C 이진 트리 삽입에서 매개변수를 이중포인터로 받는 이유를 모르겠습니다.
글쓴이: flrpf13 / 작성시간: 수, 2018/11/28 - 9:16오후
//---------- 이진 트리 삽입 ----------// void setTreenode(Treenode *ThisNode, int data, Treenode *L, Treenode *R) { ThisNode->key = data; ThisNode->left = L; ThisNode->right = R; } void insert_treenode(Treenode **root, int key) //이중 포인터가 왜 필요하지? { Treenode *p = NULL, //부모 노드, NULL 초기화 *t = *root, //현재 노드, *n; //새 노드 while (t != NULL) { if (key == t->key) return; p = t; if (key < p->key) t = p->left; else t = p->right; } n = (Treenode *)malloc(sizeof(Treenode)); if (n == NULL) return; n->key = key; n->left = n->right = NULL; if (p != NULL) { if (key < p->key) p->left = n; else p->right = n; } else *root = n; } main() { Treenode *n0 = (Treenode*)malloc(sizeof(Treenode)), *n1 = (Treenode*)malloc(sizeof(Treenode)), *n2 = (Treenode*)malloc(sizeof(Treenode)), *n3 = (Treenode*)malloc(sizeof(Treenode)), *n4 = (Treenode*)malloc(sizeof(Treenode)), *n5 = (Treenode*)malloc(sizeof(Treenode)), *n6 = (Treenode*)malloc(sizeof(Treenode)); setTreenode(n0, 30, n1, n2); setTreenode(n1, 20, n3, n4); setTreenode(n2, 10, n5, n6); setTreenode(n3, 15, NULL, NULL); setTreenode(n4, 25, NULL, NULL); setTreenode(n5, 8, NULL, NULL); setTreenode(n6, 15, NULL, NULL); insert_treenode(&n0, 4); }
다음은 이진 트리를 크기별로 부모노드보다 작은 값은 좌측 자식노드로, 큰것은 우측 자식 노드로 구성하고
이 트리에다가 4를 추가하는 코드입니다.
30
/ |
20 10
/ | / |
15 25 8 15
이런 구조입니다.
그런데 위 insert_treenode매개변수를 Treenode* 가아닌 Treenode**로 받는 이유를 모르겠습니다.
책에서도 루트노드의 포인터를 바꾸기 위함이다 하는데,
저코드를 디버깅해서 insert_treenode함수의 *t 가 가리키는 것을 추적해보았는데
결국 t는 루트 노트(위 모양에서 30)을 가리킵니다.
그런데 저 매개변수를 이중이 아닌 일중 포인터 Treenode*식으로 바꾸고
한 4줄 밑에?
Treenode *t = *root를 Treenode *t = root로,
함수 마지막 else *root = n을 root = n으로,
main함수에서 insert_treenode(&n0, 4)를
insert_treenode(n0, 4)로.
이런식으로 주소의 단계? 깊이? 를 1단계씩 낮춰줘도
전-혀 문제가 없고 알고리즘을 읽고 분석해봐도 문제가 없는데,
대체 왜 이중포인터로 전달해서 처리할까요?
Forums:
테스트 코드
간단합니다.
간단합니다.
tree의 모든 노드(Treenode)는 다른 Treenode의 child입니다. left이거나, right이거나.
아, 딱 한 가지 경우만 빼고요. root는 어느 Treenode의 child도 아니죠.
보통 Tree 밖의 누군가가 Treenode * 포인터로 root를 가리킵니다.
문제를 아시겠나요? 트리 내부의 어딘가에 Treenode를 추가할 땐, 추가할 위치의 parent만 변경하면 됩니다.
이 때는 Treenode *만 전달해 주어도 충분합니다.
딱 한 가지 예외, root를 추가할 때, 예컨대 텅 빈 Tree에 Treenode를 추가할 때는 parent가 없습니다.
외부에서 들고 있던 Treenode *를 바꾸어서 root를 가리키게 해야 합니다. 그래서 Treenode **를 전달해 주어야 합니다.
이런 "딱 한 가지 경우의 예외"로 코드가 번잡해지는 경우는 각종 자료구조/알고리즘 구현에서 종종 찾을 수 있습니다. 간결하고 일관성 있고 아름다운 코드를 좋아하시는 분들에게 골칫거리죠. 대체로 workaround가 있기는 한데, 그것도 사람에 따라 "아름다움"과는 거리가 좀 있습니다.
예컨대, Tree에 항상 "가짜 root node"가 들어있게 하여, 모든 "의미 있는 노드"는 항상 Parent node를 갖는다는 성질을 부여해 줄 수 있지요. 이러면 parent node가 없는 node를 추가할 일이 절대 없기 때문에 인터페이스가 간단해집니다. 이런 구조가 차라리 더 낫겠다고 생각하신다면, 그렇게 하세요.
댓글 달기