C++로 이진트리를 만들고 있는데 막혔습니다.....
글쓴이: dnfwlq8054 / 작성시간: 수, 2019/12/11 - 2:34오후
#include <iostream> #include <vector> using namespace std; template <typename T> class Node{ public: T data; Node * _Right; Node * _Left; static vector<Node<T>> v; Node() {} Node(T n) { this->data = n; this->_Right = NULL; this->_Left = NULL; v.push_back(this); } }; template <typename T> class tree { public: void insert(T n); }; template <typename T> void tree<T>::insert(T n) { Node<T> * node = new Node<T>(n); while (1) { for (int i = 0; i < node->v.size(); i++) { if (node->v[i]._Left == NULL) { node->v[i + 1].push_back(node); node->v[i]._Left = node; return; } else if (node->v[i]._Right == NULL) { node->v[i + 1].push_back(node); node->v[i]._Right = node; return; } } } } int main(void) { tree<char> t; t.insert('A'); t.insert('B'); t.insert('C'); return 0; }
코드입니다. 정말 간단하게 구현하려고 합니다.
간단하게 구현 후 점점 살을 붙이고 수정할 생각입니다.
동작을 설명드리자면. 숫자든 문자든 사용자가 자료형을 정한 후 아무조건없이 계속 넣습니다.
넣으면 순차적으로 데이터가 쌓이는 식으로 만들 생각이었습니다.
EX)
A
B D
B Y C Z
이런식으로 insert만 하면 완전이진트리로 계속 데이터를 넣는 것입니다. (정렬 X)
이걸 순차적으로 넣기 위해서 백터를 선언 후 넣은 순서대로 왼쪽 오른쪽 Node를 검사해서
순차적으로 넣는 트리를 구현하려고 합니다.
트리의 입력은 사진파일 하나를 첨부해 놨습니다.
백터에 데이터를 넣은 후 순차적으로 왼쪽 오른쪽 값을 검사하는 식으로 만들려고 합니다.
근데 위 코드를 실행시키면 다음과 같은 오류가 나옵니다.
"C2039 : push_back : Node의 맴버가 아닙니다."
아무래도 백터부분 자료형이 맞지 않아서 그런것 같은데, 어떻게 수정해야 할지 모르겠습니다....
그리고 이 코드에서 이런부분을 수정하면 더 좋을것 같은곳이 있으면 리뷰좀 해주시면 감사하겠습니다.
File attachments:
첨부 | 파일 크기 |
---|---|
![]() | 24.08 KB |
Forums:
...
이 정도는 컴파일 에러를 읽고 뭐가 문젠지 찾으실 수 있어야 하구요.
로직도 이상합니다. Node::v는 사실 f: L -> list of nodes가 되어야 하고, L은 트리의 레벨입니다. 별도로 각각의 노드에 대해 left와 right 노드를 채워 줘야 하구요.
이걸 쉽게 하는 방식은 그냥 1차원 어레이 같은 구조를 쓰는 것입니다. A[0]의 자식은 A[1], A[2]고, A[i]의 자식은 일반적으로 A[2*i + 1], A[2*i +2]겠죠.
새 노드는 들어올 때마다 A에 append를 하면 되고, 추가가 다 끝나면 위의 공식에 따라 각각의 노드에 대해 left와 right를 맞춰주시면 됩니다.
그런데 이 로직은 별로 binary search tree로 자연스럽게 넘어가기 어렵습니다. 중간 단계로 적절하다고 보기 어려워요.
코드를 하기 전에 종이와 볼펜/mechanical pencil 같은 걸로 알고리즘을 먼저 확실하게 하시는 게 낫습니다. 코드는 시간이 대체로 오래 걸리고 그때 가서 처음부터 잘못 된 걸 알면 시간도 많이 걸리고, 그걸 조금씩 patch하다 보면 코드도 읽고 관리하기가 힘들어집니다.
일단 이진 트리의 필요한 함수를 정리하세요
일단 이진 트리의 필요한 함수를 정리하세요
대락 이정도인데 필요에 따라 5번 부터 만들어놓고 하나하나 만들어 보는게 좋겠네요
중간중간 필요함수들은 잘 정리해서 만들구요
------------------------------------------------------------
ProgrammingHolic
위에 답을 달 때
제가 답을 달 때 제대로 읽어보지 않았었네요. Binary Search Tree가 아니라 그냥 입력 순서대로 full binary tree를 만드는 것으로 보이네요.
그 경우라면 입력 순서대로 vector v에 넣고 v[j]의 부모를 이렇게 찾으면 됩니다. j가 0이면 부모가 없고, 0이 아니면 v[(j-1)/2]가 부모 노드에요. v[i]에 대해 v[i*2+1]이 왼쪽, v[i*2+2]가 오른쪽 자식이고, i*2+k가 out of bound면 해당 자식 노드가 존재하지 않습니다.
댓글 달기