[완료]C언어 이진 탐색 트리 순회에 관한 질문입니다.

lhs8421478의 이미지

안녕하세요 자료구조를 공부하며 코딩을 하고 있는 초짜입니다..

이진 탐색 트리를 구현하면서 파라미터값이 없고 재귀가 아닌 루프형식으로 해서 전위 순회를 구현하려 했습니다.

근데 if문에서 비교 대상에 대해 이것저것 생각해보다 도무지 머리가 안굴러가서 이렇게 질문 합니다 ㅠㅠ

조언 부탁 드립니다.

밑에는 프린트 문에 대한 소스 코드입니다.

 void tree_print()
 {
     tree_node *node;
     tree_node *parent;
 
     parent = NULL;
     node = root;
     if (node == NULL) {
         printf("트리가 비었습니다.\n");
         return;
     }
     while (node != NULL ) {
         parent = node;
         printf("%d ",node->data);
         if (node != NULL) {
             if (parent->data > node->data) {
                 node = parent->left_node;
             } else {
                 node = parent->right_node;
             }
         }
     }
 }
gramo의 이미지

그냥 loop를 쓰실려면, stack이나 queue를 따로 사용하셔야 할껍니다.

lhs8421478의 이미지

그냥 공부한다고 생각하고 재귀를 안쓰고 한번 해보려고 했습니다...

기술이 아닌 어떤식으로 어떻게 풀면 되는지에 대해 생각해보려다가.. 도무지 안되서 도움을 청한것 입니다 ㅠㅠ

흠.. 스택이나 큐 아니고는 방법이 없는건가요?

gramo의 이미지

어떻게든 구현한다면, 결국 스택이나 큐 같은 자료구조를 만들어 사용하게 될겁니다. (문제 개념 자체가 그렇습니다.)
그냥 공부한다고 하시면, 재귀 개념을 정확하게 익히시는게 더 도움이 될 것으로 생각합니다.

참고로 함수 재귀는 스택과 같은 개념으로 볼 수 있습니다.

lhs8421478의 이미지

네.. 우선 함수가 들어간다면 밑에 함수가 스택에 싸이고

함수 안에서 다시 함수 호출 즉 재귀함수...

쌓인 스택 위에 쌓이고.. 처리되면 빠져 나가고.. 그런식으로 이해하고 있습니다.

더 공부해야될게 있나요??? 있다면 어떤게 있는지 조언 부탁 드립니다.

raymundo의 이미지

http://bartsesang.tistory.com/320

여기 중간에 있는 재귀함수를 비재귀함수로 바꾸기 부분을 참고하시면 될 것 같네요.

좋은 하루 되세요!

lhs8421478의 이미지

감사합니다 !

링크에가서 보고 공부좀 해야겠네요 ㅠㅠ

넘나오래됐지만..의 이미지

트리 자체에 부모필드를 추가하면 된다고 C자료구조 호로비츠 책에 나와있네요... 스택을 쓰는건 결국 재귀호출을 한다는 거랑 다를 게 없어보여서요..

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.