5일 : 재귀 함수와 이진 트리

#include<iostream>
using namespace std;
struct Tree
{
    int value;
    Tree* pL;
    Tree* pR;
};
void Add(Tree* pNode, Tree* pNew);
void Pr(Tree* pD);
void Quit(Tree* pD);
int main()
{//이진트리(입력과 출력만 만들기)
 // pNewData는 트리의 추가될 노드, pHead는 트리의 헤드 노드
    Tree *pNewData, *pHead = NULL; 
    int com = 0; // 커맨드와 입력값을 받을 정수
    while (1)
    {
        cout << "\n\n1. 입력\n2. 출력\n3. 종료" << endl;
        cin >> com; // 커맨드 입력
        if (com == 1)
        {
            pNewData = new Tree; // 트리의 노드 생성
            pNewData->pL = NULL; // 트리의 노드의 좌우를 NULL로 선언
            pNewData->pR = NULL;
            cout << "입력하실 값은? ";
            cin >> com; // 트리의 노드에 넣을 값 입력
            pNewData->value = com; // 트리의 노드에 입력한 값 대입
            if (pHead == NULL)
                pHead = pNewData; // 첫 노드일 경우
            else
                Add(pHead, pNewData); // 첫 노드가 아닐 경우
        }
        else if (com == 2)
            Pr(pHead);
        else if (com == 3)
        {
            Quit(pHead);
            return 1;
        }
        else
            cout << "잘못된 입력입니다!" << endl;
    }
}
void Add(Tree* pNode, Tree* pNew)
{
    if (pNode->value > pNew->value) 
    {// 현재 커서가 가진 값보다 새 노드가 가진 값이 작을 때
        if (pNode->pL != NULL) // 현재 커서의 왼쪽이 널인지 확인
            Add(pNode->pL, pNew); // 널이 아니면 커서 이동
        else
            pNode->pL = pNew; //널이면 값 생성
    }
    else if (pNode->value == pNew->value)
    {//현재 커서가 가진 값과 새 노드가 가진 값이 같을 때
 
    }
    else 
    {// 현재 커서가 가진 값보다 새 노드가 가진 값이 클 때
        if (pNode->pR != NULL) // 현재 커서의 오른쪽이 널인지 확인
            Add(pNode->pR, pNew); // 널이 아니면 커서 이동
        else
            pNode->pR = pNew; //널이면 값 생성
    }
}
void Pr(Tree* pD)
{
    if (pD->pL != NULL)
        Pr(pD->pL);
    cout << pD->value<<' ';
    if (pD->pR != NULL)
        Pr(pD->pR);
}
void Quit(Tree* pD)
{
    if (pD->pL != NULL)
        Quit(pD->pL);
    if (pD->pR != NULL)
        Quit(pD->pR);
    delete pD;
}
 

------

#include<iostream>
#include<string>
using namespace std;
struct Node
{
    string value;
    Node* pYes;
    Node* pNo;
};
void Add(Node* pNode, Node* pNew1, Node* pNew2);
void Make(Node* pNewNode, Node* pNewNode2);
void Pr(Node* pD);
int main()
{
    Node *pNewNode, *pNewNode2, *pHead = NULL; // 매번 두 개가 만들어지므로 pNewNode는 2개
    while (1)
    {
        if (pHead == NULL)
        {//pHead가 없을 때
            pNewNode = new Node;
            pNewNode2 = new Node;
            Make(pNewNode, pNewNode2);
            pHead = pNewNode; // pHead에 pNewNode를 대입
        }
        else
        {
            pNewNode = new Node;
            pNewNode2 = new Node;
            Add(pHead, pNewNode, pNewNode2);
        }
        cout << "----------"; //시각 확인용
        Pr(pHead);
        cout << endl;
    }
}
void Add(Node* pNode, Node* pNew1, Node* pNew2)
{
    string com;
    while (1)
    {
        cout << pNode->value << "?" << endl; // 질문
        getline(cin, com); // 답
        if (com == "y")
        {
            if (pNode->pYes != NULL) // y가 들어왔는데 왼쪽에 또 질문할 것이 있다.
                Add(pNode->pYes, pNew1, pNew2); // 질문하자! 왼쪽에 새로 값을 삽입할 경우는 없기 때문에 else문은 없다.
        }
        else if (com == "n")
        {
            if (pNode->pNo != NULL) // n이 들어왔는데 오른쪽에 또 질문할 것이 있다.
                Add(pNode->pNo, pNew1, pNew2); //질문하자!
            else
            { // 아니 질문이 없네?
                Make(pNew1, pNew2); // 자, 만들어서 쑤셔넣자!
                pNode->pNo = pNew1; //기존의 것과 만든 것을 이어준다.
            }
        }
        else
            continue; // y나 n이 아닌 엉뚱한 값이 들어왔다.
        break; // 다 돌았으면 빠져나온다.
    }
}
void Make(Node* pNewNode, Node* pNewNode2)
{ // 노드를 만들어준다.
    string s1, s2;
    cout << "뭐야?" << endl;
    getline(cin, s1);
    cout << "특징은?" << endl;
    getline(cin, s2);
    pNewNode->value = s2;
    pNewNode->pYes = pNewNode2;
    pNewNode->pNo = NULL;
    pNewNode2->value = s1;
    pNewNode2->pYes = NULL;
    pNewNode2->pNo = NULL;
}
void Pr(Node* pD)
{ // 출력해보자. 눈으로 확인용
    if (pD->pYes != NULL)
        Pr(pD->pYes);
    cout << pD->value << " / ";
    if (pD->pNo != NULL)
        Pr(pD->pNo);
}

--

노드 하나에 이름과 특징을 다 기억하도록 위의 코드를 고침

#include<iostream>
#include<string>
using namespace std;
struct Node
{
    string name;
    string desc;
    Node* pnameNo;
    Node* pdescNo;
};
void Add(Node* pNode, Node* pNew);
void Make(Node* pNewNode);
void Pr(Node* pD);
int main()
{
    Node *pNewNode, *pHead = NULL;
    while (1)
    {
        if (pHead == NULL)
        {//pHead가 없을 때
            pNewNode = new Node;
            Make(pNewNode);
            pHead = pNewNode; // pHead에 pNewNode를 대입
        }
        else
        {
            pNewNode = new Node;
            Add(pHead, pNewNode);
        }
        cout << "----------"; //시각 확인용
        Pr(pHead);
        cout << endl;
    }
}
void Add(Node* pNode, Node* pNew)
{
    string com;
    while (1)
    {
        cout << pNode->desc << "?" << endl; // 특징 질문
        getline(cin, com); // 답
        if (com == "y") // 특징 맞춤
        {
            while (1)
            {
                cout << pNode->name << "?" << endl; // 이름 질문
                getline(cin, com); // 답
                if (com == "n") // 이름 틀림
                {
                    if (pNode->pnameNo != NULL) // 질문 확인
                        Add(pNode->pnameNo, pNew); // 질문 있으면 더해
                    else
                    {//질문이 더 없음
                        Make(pNew); // 그게 뭔지 기록
                        pNode->pnameNo = pNew; // 노드 연결
                    }
                }
                else if (com != "y") // 잘못 입력
                    continue; //위로
                break; // 질문 끗
            }
        }
        else if (com == "n")
        {//특징부터 틀림
            if (pNode->pdescNo != NULL) // 질문 확인
                Add(pNode->pdescNo, pNew); // 질문 있으면 더해
            else
            {//질문이 더 없음
                Make(pNew); //그게 뭔지 기록
                pNode->pdescNo = pNew; // 노드 연결
            }
        }
        else // 잘못 입력
            continue; // 위로
        break; // 다 돌았으면 빠져나온다.
    }
}
void Make(Node* pNewNode)
{ // 노드를 만들어준다.
    string s1, s2;
    cout << "뭐야?" << endl;
    getline(cin, s1);
    pNewNode->name = s1;
    cout << "특징은?" << endl;
    getline(cin, s2);
    pNewNode->desc = s2;
    pNewNode->pnameNo = NULL;
    pNewNode->pdescNo = NULL;
}
void Pr(Node* pD)
{ // 출력해보자. 눈으로 확인용
    if (pD->pnameNo != NULL)
        Pr(pD->pnameNo);
    cout << pD->name << " / " << pD->desc << " / ";
    if (pD->pdescNo != NULL)
        Pr(pD->pdescNo);
}