Tree의 레벨 구하기~
글쓴이: espoirgod / 작성시간: 목, 2005/06/30 - 10:15오후
typedef struct BinarySearchTree {
int key;
struct BinarySearchTree *left;
struct BinarySearchTree *right;
} T;
void getlevel(T *tree, int level)
{
if (tree) {
level++;
getlevel(tree->left, level);
getlevel(tree->right, level);
// treedepth 는 전역 변수입니다
if (treedepth < level)
treedepth = level;
}
}
여러분들은 링크드 리스트로 구현한 트리의 레벨을
어떻게 구하시나요?
이 소스 간단해서 좋기는 한데..
별로 마음에 안 들어서요;;
Forums:
자주 쓰일만한 것이라면 트리의 depth 정도를 기억하는 것도 나쁘진 않
자주 쓰일만한 것이라면 트리의 depth 정도를 기억하는 것도 나쁘진 않을 듯 합니다 ;)
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
이 정도면 어떨까요? 전역 변수는 안씁니다.[code:1]int ge
이 정도면 어떨까요? 전역 변수는 안씁니다.
int getLevel(T* tree) { if (tree == NULL) return 0; int lLevel = getLevel(tree->left); int rLevel = getLevel(tree->right); if (lLevel > rLevel) return lLevel + 1; else return rLevel + 1; }[quote="doldori"]이 정도면 어떨까요? 전역 변수는 안씁니다
되돌이를 쓰지 않는 건 어떻습니까?
↑ 어떻게 할수 있죠? 쉽지않을것 같은데요?
↑ 어떻게 할수 있죠? 쉽지않을것 같은데요?
[quote="hyperhidrosis"]↑ 어떻게 할수 있죠? 쉽지않을
스택 하나만 있으면 됩니다 ;)
typedef struct { nodeptr node; int level; } stack; stack stack_data[MAX_NODE]; int top;정도로 하고...
우선 stack 에... tree의 최상위 노드를 집어넣은 후....
stack 이 비어있으면 종료
비어있지 않으면 pop
노드의 자식노드들과 현재레벨을 stack 에 push
를 반복하면 되겠죠 ;)
c calling convension 보다 stack연산이 가볍다면... 더 빨라지기는 합니다...
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
이럴 때는 특별한 사유가 없다면 doldori님처럼 recursive 하
이럴 때는 특별한 사유가 없다면 doldori님처럼 recursive 하게 하는 편이
이해하기도 쉽고 문제를 발생시킬 소지도 적다고 봅니다.
Fibonacci 처럼 중복된 노드 방문이 있는 것도 아니고요.
정태영님께서 제시하신 것처럼 별도의 스택을 사용하거나,
비슷한 방법을 쓰되 큐를 써서 BFS를 사용하는 방법도 있겠습니다만
이 경우엔 어차피 DFS로 하나 BFS로 하나 노드 방문수에 차이가 없어서
구현이 쉬운 쪽이 낫지 않나 생각이 드네요.
속도도 DFS 쪽이 웬만하면 더 빠를 것 같고요.
댓글 달기