[Tree] 기초 inorder traverse 구현 및 이해

코드 레벨로 내려가서 차근차근 짚고 넘어가는데 c++ 기초가 부실한게 여실히 나타난다. 하나하나 두들기면서 배울수밖에. 할수있다. 코딩도 수학 같이 아는것과 모르는것을 구분하는것이 정말 중요한듯.

//creat a tree 

#include <iostream>
using namespace std;

//structure of the binary tree
struct treenode { //member
    int info;
    struct treenode *left , *right;  //
};

//Function to create the binary tree 

struct treenode* create(){

    int data;
    struct treenode* tree;

    //Dynamically allocating memory
    //for tree-node

    tree = new treenode;
    cout << " "< endl;
    cout << "\nEnter data to be inserted " 
         << "or type -1 for no insertion : ";

    cin >> data;

    //termination
    if (data == -1){ //회귀에서 빠져나올수있는 곳을 남겨노라고했지. 
        return 0;
    }

    //assign value from user into tree
    tree->info = data;

    //recursively call to create the left and the right sub tree

    cout << "Enter left child for " << data;
    tree -> left = create();
    cout << "Enter right child for" << data;
    tree -> right = create();

    return tree;
};

void inorder(struct treenode* root){ // the beauty of recursion 이해완료!!! 
//https://www.youtube.com/watch?v=KIVdqquGehY&ab_channel=SimpleSnippets 미쳣다.

    if (root ==NULL) return ;

    inorder(root->left);
    cout << root -> info << "";
    inorder(root->right);

}


int main(){

    //Root Node
    struct treenode* root = NULL;

    //Function call
    root = create();
    inorder(root);
    return 0;
}

---

분석

//structure of the binary tree
struct treenode { //member
    int info;
    struct treenode *left , *right;  //
};

우선 treenode(binary tree) 구조를 미리선언해줘야한다. 어떻게 생긴지는 알아야하지않읂가.  struct 라는 member 선언 함수인데 이때 안에 또 struct가 불려지며 treenode가 생성되는데 이때 포인터 형태로 구성하여 왼쪽 child 혹은 오른쪽 child로 지칭가능하게 게 선언. 

struct 구조를 그림으로 형상화작업.

---

오늘 깨달은 Beauty of Recursion. 회귀함수의 미학. 이거를 코드로 순차적으로 이해하고 형상화 하느라  머리가 빠지는줄알았다.

위 Create() 함수에서 입력값이 좌측 부터 입력되며 이진 트리(binary tree)를 생성하고 반드시 숙지할것은 모든 recursion은 빠져나올수있게 return 값들이 존재해야 무한 루프에서 벗어 날 수 있다. 

void inorder(struct treenode* root){ // the beauty of recursion 이해완료!!! 
//https://www.youtube.com/watch?v=KIVdqquGehY&ab_channel=SimpleSnippets 미쳣다.

    if (root ==NULL) return ;

    inorder(root->left);
    cout << root -> info << "";
    inorder(root->right);

}

ref: https://dev.to/jenshaw/binary-trees-discussing-in-depth-first-traversals-4a8n

이게 정말 그림으로 표현하기 힘든데  위 gif가 정말 잘 표현해줬다.  또한 직접 코드를 머리속에 돌려보면서 순차적으로 어떤 단계로 나아가는지 반드시 이해해야한다.  난 이해가 안되서 정말 잘 설명해준 유튜브로 이해 .. 2시간 걸린듯.

 

자주 이용해야지 좋은 세상이다. 딱 알맞게 핵심을 설명.

---

tree 구조가 이제좀 머리속에들어온다 . 앞으로 해야할것들 나열..

• Inserting an element.
• Removing an element.
• Searching for an element.
• Traversing the tree.

코딩 배우는건 진짜 손이 많이가는것같다. 일일이 다 해보면서 돌다리를 두들겨야할듯 끝.