C++로 이진트리를 만들고 있는데 막혔습니다.....

dnfwlq8054의 이미지

#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: 
첨부파일 크기
Image icon 캡처.PNG24.08 KB
Stephen Kyoungwon Kim@Google의 이미지

이 정도는 컴파일 에러를 읽고 뭐가 문젠지 찾으실 수 있어야 하구요.

로직도 이상합니다. 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하다 보면 코드도 읽고 관리하기가 힘들어집니다.

swish95의 이미지

일단 이진 트리의 필요한 함수를 정리하세요

1. root node 정의
2. search 함수 정의 - 특정 값을 찾아서 해당하는 노드를 반환하는 함수(아마 stack 같은 자료형에 기반을 둬야겠죠?)
3. left, right 가 비어있는 노드 찾는 함수 - 이게 search 하고 비슷하지만 용도가 다름니다, left 또는 right 가 비어있는 노드 반환
4. 특정 노드의 left 또는 right 에 노드에 새로운 노드를 할당 하는 함수 - left 에 값없으면 left, 있으면 right 에 넣어야 겠네요
5. 전체 노드를 보기쉽게 출력하는 함수

대락 이정도인데 필요에 따라 5번 부터 만들어놓고 하나하나 만들어 보는게 좋겠네요
중간중간 필요함수들은 잘 정리해서 만들구요

------------------------------------------------------------
ProgrammingHolic

Stephen Kyoungwon Kim@Google의 이미지

제가 답을 달 때 제대로 읽어보지 않았었네요. 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면 해당 자식 노드가 존재하지 않습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.