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를 추가할 일이 절대 없기 때문에 인터페이스가 간단해집니다. 이런 구조가 차라리 더 낫겠다고 생각하신다면, 그렇게 하세요.
댓글 달기