연휴로 내주신 과제.
모 대학 시험 문제, 깃허브에 퍼블릭으로 공유됨.

Linked_List

Linked_List.

ListNode

• int item
• sturuct listnode *next

와

LinkedList

• int size
• ListNode *head

로 이루어져 있다.

그 외 제공되는 함수는

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode *findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

인덱스로 찾고, 삽입하고, 제거하는 함수가 추가적으로 있음.
문제에 따라 여기에 더해 있는 경우가 있다.

Q1. insertSortedLL

넣는대로 정렬되는 함수.
1->2->3-> ... 같이 이어져있고
head부터 시작해서
큰 값을 마주하면 멈춰서 그 앞에 삽입해야한다.

구현해야하는 것은 두 가지.

1. 자신에게 맞는 인덱스 탐색
2. 삽입

인덱스만 찾으면, 기존의 insertNode 함수를 쓸 수 있기 때문에,

idx로 next를 옮길때마다 값을 올려서
조건문으로 값이 큰걸 마주한 순간 멈추게 while 돌리고
(또는 for로 돌리되 ll의 size만큼만 돌린다.)

null을 마주하면 그냥 그 자리에 삽입.
....
인데 나는
아예 값으로 인덱스 찾는 함수를 따로 만들어서
얻은 인덱스로 InsertNode 했군...

아예 리스트가 비면 맨 앞에 넣는 예외로 빼고..
(while로 한 대신 Null에 도달하면 그냥 그 index를 전달하고 있다...)

//값으로 적절한 위치를 찾는 함수.
int find_key_node(LinkedList *ll, int x){

	ListNode *tmp = ll->head;
	int in_dex = 0;

	while (tmp!= NULL)
	{
		if (x > tmp->item)
		{
			tmp = tmp->next;
			in_dex += 1;
		}
		else if (x < tmp->item)
		{
			return in_dex;
		}
		else{
			return -1;
		}
	}

	return in_dex;

	
	
}

//해당하는 인덱스가 노드를 순서에 맞게 삽입하는 함수
int insertSortedLL(LinkedList *ll, int item)
{

	ListNode *temp;
	int tmp_index;
	
	temp = ll->head;

	if(ll!= NULL && temp != NULL){
		
		tmp_index = find_key_node(ll, item);
		if(tmp_index != -1){
			insertNode(ll, tmp_index, item);
		}
	}
	else if(ll == NULL){
		printf("리스트가 없음.\n");
	}
	else{
		insertNode(ll, 0, item);
	}

	return tmp_index;

}

사실 null 자체를 반환하는 일은 잘 없겠지만,
C에서 제일 곤란한 경우는 역시 대응하는 값이 null이라서
해당하는 요소를 찾을 수 없어서 segment fault가
생길 때인 것 같다...

Q2. alternateMergeLL

첫번째 ll의 사이사이마다 두번째 ll의 값을 넣어 합치는 함수.

만약 ll의 사이에 자리가 없다면,
ll의 나머지값은 넣지 않는다.

이게 그대로 next만 변경하면
두번째 ll의 모양이... 남기 때문에

아예 새로운 node로 만들어서
두번째 ll의 값을 받아 사이사이에 insert로 넣어주는데....
이건 인덱스로 추가하려면...
추가할때마다 인덱스가 변경되는 걸 반영한다? 라고 생각하니
좀 뻑날까봐...

아예....

for로 0부터 ll2를 전체 순회해서
새 노드를 만들어서 그 아이템을 집어넣고
인덱스는 같이 움직일테니
현재 ll1의 인덱스에서 추가한다
(ll1->next = 새 노드)
(새노드->next = (원래 ll1->next))
그리고 ll2에서 그 아이템으로 이루어진 노드를 지워줌.
(인덱스는 그대로있을테니 removeNode 함수를 쓰면 됨.)

그렇게 ll2가 다 닳을 때까지 돌겠지만,
만약 ll1의 next가 없는 경우에는 멈춘다!
...로.

그래서 ll2_size만큼 for로 돌되
ll2와 ll2이 다 닳을 때까지로 while로 해서
저 과정을 그대로 했는데,

while이 보통 맨 바깥에 있을 때가 흔하니까
좀 헤맨것 빼고는 괜찮았다..

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
	//ll1의 포인터 두개.
	ListNode *temp = ll1->head;
	ListNode *tm_next = temp->next;
    //ll2 포인터와 상수 변수 두개.
	ListNode *ll2_i = ll2->head;
	int ll2_size = ll2->size;
	int ll2_i_key =ll2_i->item;

	// 돌면서 사이사이 새 노드 넣는 과정.
	for(int i = 1; i<= ll2_size; i++){
		while (ll2_i !=NULL && tm_next != NULL){
			ListNode *new= malloc(sizeof(int));
			ll2_i_key = ll2_i->item;
			tm_next = temp->next;
			new->item = ll2_i_key;
			temp->next = new;
			new->next = tm_next;
			ll2_i = ll2_i->next;
			temp = tm_next;
			removeNode(ll2,0);
		}
	}
	
}

Q3. moveOddItemsToBackLL

홀수 값이 있으면 따로 뽑아서
맨 뒤로 옮기는 함수.

....
나는 홀수가 나오면
아예 임의의 리스트를 만들어서
거기에 넣어버리고
현재 홀수 값은 기존리스트에서 지우고

현재 리스트 뒤에 임의의 리스트를 붙여버렸다.

이렇게 길게 하지않아도
새 노드 만듦-> 맨뒤에 붙임->기존 노드 지움
으로 될거같긴 하다.
아마 기존 노드 지울때마다 size가 바뀌긴할텐데
그건 뭐... 하나씩만 지울테니 +1만 하면 되긴 하겠지.

내가 한 과정은 어렵지 않다.
홀수 판단.
-> 홀수면 임의의 리스트에 추가해주기.
-> 짝수면 냅두고 넘어가기.

현재 리스트 맨뒤를 사이즈로 찾은 뒤
맨 뒤->next = 두번째 리스트 헤더

...면 끝!

void moveOddItemsToBack(LinkedList *ll)
{
	ListNode *tmp =ll->head;
	ListNode *tm_next = tmp;
	ListNode *prev = NULL;

	// 임의의 두번째 링크드 리스트 만들기. 
	LinkedList *ll2 = malloc(sizeof(LinkedList));

	ll2->head = NULL;
	ll2->size = 0;

	ListNode *ll2_tmp = ll2->head;

	//기존 리스트 전체 순회.
	while (tm_next != NULL)
	{
		tmp = tm_next;
		tm_next = tmp->next;
        //홀수고, 맨 처음이 홀수가 아니라면
        //이전 노드와 그 다음 노드를 이어버린다.
		if(tmp->item%2 == 1){
			if(prev != NULL){
				prev->next = tmp->next;
				tm_next = tmp->next;
				ListNode *new = malloc(sizeof(ListNode));
				new->item = tmp->item;
				new->next = NULL;
				free(tmp);
                // 두번째 리스트에 그 노드를 넣는 과정.
				if(ll2_tmp != NULL){
					ll2_tmp->next = new;
					ll2_tmp = new;
					ll2->size++;
				}
				else{
					ll2->head = new;
					ll2_tmp = new;
					ll2->size++;
				}
			}
		}
			else{
				// 만약 처음 노드가 홀수라면 
                //바로 ll2에 넣고 ll1의 head도 갱신해야한다.
				tm_next = tmp->next;
				ll->head = tm_next;
				ListNode *new = malloc(sizeof(ListNode));
				new->item = tmp->item;
				new->next = NULL;
				free(tmp);
				if (ll2_tmp != NULL)
				{
					ll2_tmp->next = new;
					ll2_tmp = new;
					ll2->size++;
				}
				else
				{
					ll2->head = new;
					ll2_tmp = new;
					ll2->size++;
				}
			}
	}

	// size 처리에 문제가 있을테니 수동으로 끝까지 이동.
	ListNode *x;
	ListNode *z;

	if(ll->head != NULL){
		x = ll->head;
		while(x != NULL){
			z = x;
			x = x->next;
		}
		
        // 그래서 끝에 도착했다면 이어주자.
		if(z != NULL){
			z->next =ll2->head;
		}
	}
    // 근데 전부 홀수였어서 ll이 비었었다면 ll2로 대체해주자.
	else{
		ll->head = ll2->head;
	}
	// ll2자체는 이제 안쓸테니 없애주자.
	free(ll2);
	
}

생각보다 예외처리가 까다로웠다...
처음 노드가 홀수일 때와,
전부 홀수인 경우.... 같은 게.
아예 삽입 삭제를 일일이 써서 좀 까다로워졌는데
인덱스만 잘 찾았으면 기존 함수 썼을텐데...<

Q4. moveEvenItemsToBackLL

나는 당연히
그냥 ...
홀수? 에서 짝수된거면?
똑같은 메커니즘에 조건문만 바꾸면 되는거 아닌가? 했는데
맞지 맞는데

왜인지 안 되길래
지피티 괴롭혔다

근데 지금봐도 모르겠어
실제로 좀 추가 된건 null인거 대비고
size 반영 뭐 그정도인건데 ........
....
모르겠군

void moveEvenItemsToBack(LinkedList *ll)
{
	ListNode *tmp =ll->head;
	ListNode *tm_next = tmp;
	ListNode *prev = NULL;

	LinkedList *ll2 = malloc(sizeof(LinkedList));

	ll2->head = NULL;
	ll2->size = 0;

	ListNode *ll2_tmp = ll2->head;

	while (tm_next != NULL)
	{
		tmp = tm_next;
		tm_next = tmp->next;
		if(tmp->item%2 == 0){
			if(prev != NULL){
				prev->next = tmp->next;}
			else{
				ll->head = tm_next;
			}

			tm_next = tmp->next;
			ListNode *new = malloc(sizeof(ListNode));
			new->item = tmp->item;
			new->next = NULL;
			free(tmp);
			
			if(ll2_tmp != NULL){
				ll2_tmp->next = new;
				ll2_tmp = new;
				ll2->size++;
			}
			else{
				ll2->head = new;
				ll2_tmp = new;
				ll2->size++;
				}
			}

		else{
			prev = tmp;
		}
}

	ListNode *x;
	ListNode *z;

	if(ll2->head != NULL){
		if(ll->head != NULL){
			x = ll->head;
			while(x != NULL){
				z= x;
				x = x->next;
			}
			z->next = ll2->head;
		}
		else{
			ll->head = ll2->head;
		}

		ll->size += ll2->size;
	}
}

Q5. frontBackSplitLL

절반으로 나눠서 링크드 리스트를 2개로 만드는 함수.
그래서 받는 거 1개 외에도
결과 리스트를 두개 반환해야한다.

그래서 그대로 size의 절반을 단순히 next 갱신이 아니라
새 리스트에 넣을때마다 remove하고
새 리스트에 insert를 해야하는데...

remove하면 size가 달라지니까
size을 고정값으로 처음에 저장해둬야한다.

또 기존 insert 함수는 넣을 때의 인덱스를...확실히 해줘야해서
지금 생각하면 그냥 리스트 두개니까 인덱스 두개 만들면 될 거같긴 한데.... (size가 바뀔테니 그걸 인덱스로 하든가)

나는...

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	
	// 앞 리스트 크기 정하는 부분.
	int front_size;
	
	if(ll->size%2 == 0){
		front_size = ll->size/2;
	}
	else{
		front_size = (ll->size/2)+1;
	}

	ListNode *x = ll->head;

	// 앞 리스트 크기만큼 앞 리스트에 넣는다.
	for(int i = 0; i<front_size;i++){

		ListNode *new = malloc(sizeof(ListNode));

		new->item = x->item;
		new->next= NULL;

		if(resultFrontList->head == NULL){
			resultFrontList->head = new;
		}
		else{
			ListNode *cur = resultFrontList->head;
			while (cur->next != NULL)
			{
				cur = cur->next;
			}
			cur->next = new;
			
		}
		x = x->next;
	}

	// 뒷 리스트 크기만큼 뒷 리스트에 넣는다.
	for(int j = 0; j<(ll->size -front_size);j++)
	{
		ListNode *new_b = malloc(sizeof(ListNode));

		new_b->item = x->item;
		new_b->next = NULL;

		if(resultBackList->head == NULL){
			resultBackList->head = new_b;
		}
		else{
			ListNode *cur_b = resultBackList->head;
			while (cur_b->next != NULL)
			{
				cur_b = cur_b->next;
			}
			cur_b->next = new_b;
			
		}

		x = x->next;
	}


}

지피티의 향기가 나는가?
정답이다. 처음에 아예 새 노드 만들기로 안 하고 한 게
뻑나서 내 마음도 한번 뻑났기 때문이다.

확실히 앞 리스트를 쭉 넣고
뒷 리스트를 쭉 넣는다면 for을 두번 하는게 나을수도.

아니면 아예 쭉 돌리되
인덱스가 front_size 안일때는 첫번째 리스트에 넣고,
그 이상일때는 두번째 리스트에 넣는
두 개의 조건문으로할수는 있는데

실제로 괜찮은건 첫번째일거같다.
(왜냐하면 두번째 방법은 매번 인덱스를 계산해서
조건문으로 비교해야하니까.)

Q6. moveMaxToFront

가장 큰 값을 찾아서
맨 앞에 옮기는 함수다.

...뭐
쉽지 않은가?
max를 모든 리스트를 순회해서
갱신해서 가장 큰 max를 찾은 후

헤드에 넣기만 하면 된다. 와!

그리고 null인 경우만 고려하면 되겠지.
또 자기 자신이 head라면 그 처리 안 하게 예외 처리하고.

그치만 당황했던 이유는
아까 주던 리스트로 안주고 ptrHead,
리스트의 대빵 노드만 주는데다가 더블 포인터로 주길래
내....내가 하려던 값이 뭔지 좀 헤맸다.

아직 잘 납득이 안 됐다 심장에서....

1. 왜 굳이 더블 포인터로 반환하는가?
   ...

근데 좀 알거같다
반환하는 이유는 모르겠지만

*head 로 만들면
그 뒤는 head->next 처럼 쓰지 않는가?

**head로 준다면
*head->next 로 쓰는게 논리적으로 맞겠지.

int moveMaxToFront(ListNode **ptrHead)
{
	// 최댓값 찾는 변수
    ListNode *max_n = *ptrHead;
	int max_i = (*ptrHead)->item;
	ListNode *max_prev = NULL;

	// 리스트에서 이동할 포인터들.
	ListNode *x = *ptrHead;
	ListNode *z;

	z = x;

	// 최댓값을 리스트 전역에서 찾기.
	while ( x != NULL)
	{
		if(max_i < x->item){
			max_i = x->item;
			max_n = x;
			max_prev = z;
		}
		z= x;
		x = x->next;
	}

	// 찾은 최댓값을 빼내고 머리에 잇기.
	ListNode *first = *ptrHead;
	if(max_prev != NULL){
		max_prev->next = max_n->next;
		max_n->next = first;

	}
	else{
		*ptrHead = max_n->next;
		max_n->next = *ptrHead;
	}

	*ptrHead = max_n;
	
}

Q7. recursiveReverse

재귀를 써서 리스트 순서를 뒤집으라는 함수다.

그러니까 1, 2, 3, 4, 5 순이면
5, 4, 3, 2, 1, 순으로 만들어버리는 것이다.

대체 무슨 재귀를 써야 뒤집어진단 말인가?

나는 문제지에 있는 빨간 글씨를 봐버렸다....
골자는 이렇다.

...

하고 봤는데 갑자기 납득 안되어서
고민하다가 챗지피티한테 물어봄

void RecursiveReverse(ListNode **ptrHead)
{

    if (ptrHead == NULL || *ptrHead == NULL || (*ptrHead)->next == NULL) {
        // 예외 처리: 빈 리스트이거나 NULL인 경우 함수 종료
        return;
    }

	ListNode *first, *rest;

	first = *ptrHead;
	rest = first->next;

	if(rest != NULL){
		RecursiveReverse(&rest);
	}
	// 현재 노드의 다음 노드의 다음 노드를 현재 노드로 해준다.
	first->next->next = first;
    // 현재 노드의 다음 노드와의 연결은 끊어준다.
	first->next = NULL;
    // 위의 재귀로 다 돌았을테니 제일 끝 친구를 대빵 시켜준다.
	*ptrHead = rest;

}

뭐 이론적으로는 알겠는데...
1->2->3->4->5 면

1->2에서

1->2->1 해줌

그리고
2->1 해준다는거 아니야
하...

Stack_and_Queue

기본적으로 구현되어있는 함수.

void enqueue(Queue *q, int item);
int dequeue(Queue *q);
int isEmptyQueue(Queue *q);
void removeAllItemsFromQueue(Queue *q);

void push(Stack *s , int item);
int pop(Stack *s);
int isEmptyStack(Stack *s);
void removeAllItemsFromStack(Stack *s);

void printList(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
void removeAllItems(LinkedList *ll);

큐 구조체.

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;	// You should not change the definition of ListNode

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;	// You should not change the definition of LinkedList


typedef struct _queue
{
	LinkedList ll;
} Queue;  // You should not change the definition of Queue

스택 구조체.

typedef struct _stack
{
	LinkedList ll;
}Stack;  // You should not change the definition of Stack

Q1. createQueueFromLinkedList

링크드 리스트 값을 받아서
큐에 넣으면 끝.

현재 링크드 리스트에서 꺼낸 노드에서
값을 확인하여 큐에 넣고,
링크드 리스트에서 그 노드를 삭제한다.

그리고 그 다음 노드를 꺼낸다.

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	ListNode *first = ll->head;

	while (first != NULL)
	{
		enqueue(q, first->item);
		removeNode(ll, 0);
		first = ll->head;
	}
	
}

Q2. createStackFromLinkedList

링크드 리스트 값을 받아서
스택에 넣으면 끝.

이제 명령어만 push로 넣으면 된다...

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
    ListNode *first = ll->head;

	while (first != NULL)
	{
		push(s, first->item);
		removeNode(ll, 0);
		first = ll->head;
	}
}

Q3. isStackPairwiseConsecutive

스택이 짝수면 pairwise군요!
홀수면 아니군요! 하는 함수.

그냥 stack 사이즈만 있으면 끝.

int isStackPairwiseConsecutive(Stack *s)
{
	if(s->ll.size%2 == 0){
		return -1;
	}
	else{
		return 0;
	}
}

Q4. reverseQueue

큐를 거꾸로 넣는 건데
그냥 뽑아서 다시 도로 넣으면 끝.
(전체 사이즈만큼.)

void reverse(Queue *q)
{
	Stack *s = malloc(sizeof(LinkedList));
	s->ll.size = 0;
	s->ll.head = NULL;
	s->ll.tail = NULL;

	// 뽑아서 스택에 저장해놓는다...
	while (q->ll.size != 0){
	
		int new;
		new = dequeue(q);

		push(s, new);
	}
	// 이제 저장한 스택에서 큐에 넣는다...
	while (s->ll.size != 0)
	{
		int new_s;

		new_s = pop(s);
		enqueue(q, new_s);
	}
	

}

Q5. recursiveReverseQueue

이제 그걸 재귀로 하라고 한다.

.....

솔직히 이렇게 적으니
방법이 바로 떠오르지 않았다..

아마 재귀할때는 현재 값이 다른 걸 실행하는 동안
멈춰있는 원리를 이용,

deque 후 재귀 시키고 enque로 넣는다.

void recursiveReverse(Queue *q)
{
 
	int temp;
	if(q->ll.head == NULL){
		return ;
	}
	temp = dequeue(q);
	recursiveReverse(q);
	enqueue(q, temp);

}

Q6. removeUntilStack

어떤 값을 준다면
그전까지의 값을 제거하는 함수.
(값이 나올때까지 그냥 제거해주면 된다.)

void removeUntil(Stack *s, int value)
{

	while (value != s->ll.head->item)
	{
		pop(s);
	}
	
}

Q7. balanced

괄호가 짝이 맞는지 확인하는 함수.

사실 원리는 그건데
그... 어차피
왼쪽 괄호를 스택으로 쌓고
오른쪽 괄호가 나왔을 때 쌓아놓은 스택을 확인해서
대치되는 괄호면 스택 하나 지워서

최종적으로 스택이 비워져있으면 완성.

그래서
끝나고도 스택이 안 비워져있음/
스택에서 꺼내야하는데 아무것도 없음/
스택에서 확인했는데 짝이 안맞음

을 예외처리해주면 된다.

int balanced(char *expression)
{
	int length = 0;

	// 받은 괄호들의 길이를 재는 부분.
	while(expression[length] != '\0'){
		length++;
	}

	// 쓸 스택을 마련, 초기화.
	Stack *s = malloc(sizeof(Stack));

	s->ll.head = NULL;
	s->ll.size = 0;

	int check;
	// 왼쪽 괄호면 전부 집어넣는다.
	for(int i = 0; i <= length; i++){
		if(expression[i] == '(' || expression[i] == '{' || expression[i] == '['){
			push(s, (int)expression[i]);
		}
        // 오른쪽 괄호면...
		else if (expression[i] == ')' || expression[i] == ']' ||expression[i] == '}')
		{
        	// 스택이 비었는지 확인.
            // 안 비었으면 틀림 판정.
			if(isEmptyStack(s)){
				free(s);
				return 1;
			}
            // 체크용으로 꺼내봄.
			check = pop(s);
            // 꺼낸게 일치하지않으면 틀림 판정.
			if(expression[i] == ')' && check != '(' ||
			expression[i] == ']' && check != '['||
			expression[i] == '}' && check != '{'
			){
				free(s);
				return 1;
			}

		}
		
	}
	// 다 했는데 스택이 비어있지않으면 틀림 판정.
	int result = isEmptyStack(s);

	free(s);
	// 모든 틀림 판정을 지나친 결과는...
	return !result;
}

지피티의 향기가 느껴지는가? 맞다.
알고리즘 원리는 알겠는데 6개의 괄호 조건문을 쓰다보면
자신이 맞는지 회의감이 들 것이다.
덕분에 조건이 여러개일때 뭉치는 법을 배웠다.

그리고 의외로 안 맞아서 뭐지 했는데
초기화를 안 시켜줘서 생겼던 오류였나 그랬던 것 같다.

Binary_Tree

이진 트리 구조체.

typedef struct _btnode{
	int item;
	struct _btnode *left;
	struct _btnode *right;
} BTNode;   // You should not change the definition of BTNode

진짜 노드뿐이야?? 정말로?? 했던 듯.

구현된 함수.

BTNode* createBTNode(int item);

BTNode* createTree();
void push( Stack *stk, BTNode *node);
BTNode* pop(Stack *stk);

void printTree(BTNode *node);
void removeAll(BTNode **node);

Q1. identical

완전히 똑같은 순서로 넣은 트리인지 확인하는 함수.

(솔직히 이걸...)
(어떻게.....)

근데 사실 넣는 순서가 같다면
트리가 동일할 것이기때문에
두개의 트리를 순회했을 때
그 노드들의 순서가 일치하면 되는 문제.

그래서 두개의 트리를
각각 순회해서
스택에 전부 넣어버린 다음

스택에 동시에 하나씩 꺼내서
전부 일치하는지 보면 되긴 하는데...

순회 자체는 중위, 후위 순회든 뭐든

(넣기)
(왼쪽으로 재귀)
(오른쪽으로 재귀)

로 해결하고
(저걸 아예 함수로 만들어서
트리 둘 다 처리하면 완성.)

이제 스택을 하나씩 pop하면 될텐데...

// 트리를 순회하면서 스택에 넣는 함수.
void inorder_tree(BTNode *tree, Stack *s){

    if(tree == NULL)
        return ;

    push(s, tree);
    inorder_tree(tree->left, s);
    inorder_tree(tree->right, s);

}

int identical(BTNode *tree1, BTNode *tree2)

{

   if(tree1 != NULL && tree2 != NULL){
   // 넣을 스택 두 개 확보.
    Stack *s = malloc(sizeof(Stack));
    s->top = NULL;
    Stack *s_t = malloc(sizeof(Stack));
    s_t->top = NULL;
	// 트리 두 개 순회 돌기.
    if(tree1 != NULL){
            inorder_tree(tree1, s);
    }
    if(tree2 != NULL){
            inorder_tree(tree2, s_t);
    }
	// 스택 둘 다 빼서 비교해보기.
    //(단, 혹시 NULL을 뽑을 떄를 대비해서 조건문 처리.)
    while(s->top != NULL){
        BTNode *new = pop(s);
        if(s_t->top == NULL){
            return 0;
        }
        BTNode *new_t = pop(s_t);
        if(new->item != new_t->item){
            return 0;
        }
    }
	// 스택 하나 다 뽑았는데 덜 비었으면 실패.
    if(s_t->top != NULL){
        return 0;
    }
	// 다 거쳤다면 성공.
    return 1;
   }
	// 애초에 둘다 null이면 성공.
   if(tree1 == NULL && tree2 == NULL){
    return 1;
   }

   return 0;
}

... 그대로 했네!

Q2. maxHeight

현재 가장 최고 레벨이 몇인지 구하는 함수.
(null이면 -1,
루트면 0,
그 아래 자식부터 1...)

근데 이걸 이제 재귀로 해라...
.....

재귀로 순회를 한다고 해도
그게 어떻게 heigt가 되지..
나는 예전부터 재귀로 누적 값을 구하는데에 약하다...

그래서 보니까

재귀로 왼쪽, 오른쪽을 빠지는데
아예 숫자를 리턴하는 함수로 만들어서
자기 현재 height를 리턴하게 해서

만약 왼쪽 값 /오른쪽 값 중에 더 큰 값을 돌려주는 식으로
(그러면 가장 깊은 리프노드에서 루트까지 높이가 도달할테니)
하는 식인데...

자기 자신이 null -> 0 리턴
자기 자신이 null은 아닌데
왼쪽 자식이 null -> +1 리턴
오른쪽 자식이 null -> +1 리턴

자기 자신이 null이 아니고
왼쪽, 오른쪽 자식도 null이 아님
-> 왼쪽이면 왼쪽값 +1 리턴,
-> 오른쪽이면 오른쪽값 +1 리턴...

....

이었던 것 같다.

int height_recursive(BTNode *node){

    if(node == NULL)
        return 0;

    if(node != NULL){
        int leftHeight = height_recursive(node->left);
        int rightHeight =  height_recursive(node->right);
        return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
    }
}


int maxHeight(BTNode *node)

{
    if(node == NULL){
        return -1;
    }
    else{
        return height_recursive(node)-1;
    }


}

근데 사실 왼쪽 오른쪽 자식은 null이든 아니든 +1이므로
기존값 +1 이면 되긴 한다.
지피티 향기가 느껴지는가? 그렇다.
나는 재귀가 어려웠다.

Q3. countOneChildNodes

자식이 하나인 노드의 갯수를 세는 함수.

트리 전체를 순회하되,
이제 자식이 하나인 노드를 재귀로 거둬와야한다니.

.....

근데 사실 이게 그렇다.
왼쪽 오른쪽 값을 반환해서 가져오지만,
이제 만약 자식이 하나인경우만 +1 시켜서 리턴하고,
올릴때도 왼쪽과 오른쪽 중 큰 값을 올려주면,
최종 루트가 가장 많은 1을....가져서
총 갯수를 알게된다.

int count_recursive(BTNode *node){
    if(node == NULL)
        return 0;
    else{
        int leftcount = count_recursive(node->left);
        int rightcount = count_recursive(node->right);
        if((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)){
            return leftcount+rightcount+1;
        }
        return leftcount+rightcount;
    }

}


int countOneChildNodes(BTNode *node)
{

    int total = 0;

    if(node == NULL){
        return 0;
    }
    else{
        total = count_recursive(node);
        return total;
    }
}

큰 값이 아니라 합이군.
생각해보니 그렇네.

Q4. sumOfOddNodes

홀수인 노드들의 합을 구하는 것이다.
노드를 전체 순회하되 홀수인 노드의 합만 구한다.

... 간단하다!
이제 순회하되
노드의 키값을 일일이 꺼내서
홀수라면 리턴할때 자기 키값을 더해서 돌려주고
아니면 그냥 현재 값을 리턴한다.

int sum_odd_recursive(BTNode *node){


    if(node != NULL){
        int leftcount = sum_odd_recursive(node->left);
        int rightcount = sum_odd_recursive(node->right);
        if(node->item %2 == 1){
            return leftcount+rightcount+(node->item);
        }
        return leftcount+rightcount;
    }


}

int sumOfOddNodes(BTNode *node)
{
    if(node == NULL){
        return 0;
    }
    else{
        return sum_odd_recursive(node);
    }

    
}

Q5. mirrorTree

현재의 트리를
거울상으로 반전시킨다.

......

.....

왜 이런..
일이 필요할때도 있겠지

이건 왼쪽 오른쪽 자식을 바꾸면 되는데
이제 트리 전체에서 바꾸면 된다.

단 처음부터 바꾸면
나중에 추적할때 헷갈릴 수 있으니까

재귀로 왼쪽 오른쪽 들어가고
나중에 왼쪽 = 오른쪽값
오른쪽 = 왼쪽값

하고 지내면 될거같다.
(그렇지만 노드 자체는 고정이니까
딱히 순서는 상관없을지도.)

void mirror_recursive(BTNode *node){
    if(node != NULL){
        BTNode *right = node->right;
        BTNode *left = node->left;

        node->left = right;
        node->right = left;
        mirror_recursive(node->left);
        mirror_recursive(node->right);

    }
    
}

void mirrorTree(BTNode *node)
{

    mirror_recursive(node);

	
}

이거 나눌 필요가 있는 건가?
모르겠다. (없어보인다.)

Q6. printSmallerValues

내가 준 값보다 작은 값만 출력한다.
갑자기 왜 쉬운 문제 내주지?

트리를 전체 순회하면서
값이 작은 놈을 족족 출력.

void printSmallerValues(BTNode *node, int m)
{
	if(node != NULL){

        if(node->item < m){
            printf("%d ", node->item);
        }
        printSmallerValues(node->left, m);
        printSmallerValues(node->right, m);
    }
}

Q7. smallestValue

가장 작은 놈을 출력.

아... 위에 그래서 헷갈린 거네.
아무튼 전체 순회해서
smallest를 갱신해서

순회를 전부 끝낸 후
걔를 출력.

int small_recursive(BTNode *node){

	if(node != NULL){

        int left = small_recursive(node->left);
        int rigth = small_recursive(node->right);
        if(left >= rigth && (left != 0 || rigth != 0)){
            return rigth;
        }
        else if(left < rigth &&(left != 0 || rigth != 0)) {
            return left;
        }
        else{
            return node->item;
        }

    }
    return 0;

}


int smallestValue(BTNode *node)
{

    int min_n = node->item;

	if(node != NULL){
        int smaller = small_recursive(node);
        return smaller;
    }
}

아 근데 그걸로는 갱신이 안되니까
재귀라서.....
올려줄 값을.... 골라서....
걔를 리턴해서 최종 순위 올렸구나...ok...

Q8. hasGreatGrandchild

손자 이상 가진 놈만 출력.

그럼 직전 놈의 정보로만
출력할 수 있는 게 아닌데....
하고 고민하다가 어떻게했는데

전부...
잊어버린 얼굴...

아마 height 처럼 올리되
이제 특정 height에 도달한 애를 출력시킨것 같다.

스택에 넣어야하나했는데 그냥 출력하면 되길래.
그래서 중간중간 그 height에 도달했는지 확인해서
도달했으면 출력!

int Great_recursive(BTNode *node)
{

    if(node == NULL){
        return 0;
    }

    int left = Great_recursive(node->left);
    int rigth = Great_recursive(node->right);
    if(left != 0 && rigth == 0){
        if(left > 1){
           printf("%d ",node->item);
        }
        // printf("현재 나의 노드 위치는 %d\n", node->item);
        // printf("내 가장 많은 자식은... %d\n", left);
        return ++left;
    }
    else if(rigth !=0 && left ==0){
        if(rigth >1){
           printf("%d ",node->item);
        }
        // printf("현재 나의 노드 위치는 %d\n", node->item);
        // printf("내 가장 많은 자식은... %d\n", rigth);
        return ++rigth;
    }
    else if (left != 0 && rigth != 0)
    {
        left++;
        rigth++;
        if(left > rigth){
            if(left > 1 || rigth > 1){
                printf("%d ",node->item);
            }
            // printf("현재 나의 노드 위치는 %d\n", node->item);
            // printf("자식이 둘인데, 내 가장 많은 자식은... %d\n", left);
            return left;
        }
        if(rigth>left){
            if(left>1 || rigth > 1){
                printf("%d ",node->item);
            }
            // printf("현재 나의 노드 위치는 %d\n", node->item);
            // printf("자식이 둘인데, 내 가장 많은 자식은... %d\n", rigth);
            return rigth;
        }
    }
    else{
        if(node->left != NULL || node->right != NULL){
            // printf("현재 나의 노드 위치는 %d\n", node->item);
            // printf("슬하에 자식 하나는 있다.\n");
            return 1;
        }
        // printf("현재 나의 노드 위치는 %d\n", node->item);
        // printf("무자식이 상팔자.\n");
        return 0;
    }
}




int hasGreatGrandchild(BTNode *node)
{
	if(node == NULL){
        return 0;
    }
    else{
        int result = Great_recursive(node);
        // if(result >1){
        //     printf("%d ", node->item);
        // }
        return 1;

    }
}

노고가 느껴지는 코드네.........
전위 연산자로 해야했다..는데 뭐 사실 상관없지않나
어차피 리턴 시점에는 다 연산해서 리턴할텐데...

왼쪽 자식만 있는 경우,
오른쪽 자식만 있는 경우,
자식이 둘인 경우,
(근데 왼쪽이 더 많음/오른쪽이 더 많음)
리턴 받은 값은 0이긴 한데 자식은 있는 경우,
리턴 받은값도 0이고 자식도 없는 경우.....

....
왜이렇게 복잡하게 풀었대.
하지만 난 힘냈다.

Binary_Search_Tree

Q1. levelOrderTraversal

레벨 순으로 출력하는 법...

(1레벨 루트 출력
2레벨 루트 자식 출력
3레벨 루트 자식 자식 출력
왼->오 순으로.)

간단하다...

루트 출력함
왼, 오 자식 큐에 넣음.

큐에서 하나 꺼냄.
출력함.
왼, 오 자식 큐에 넣음.

큐는 넣은순으로 나가니까 완성!

void levelOrderTraversal(BSTNode* root)
{

	Queue *q = malloc(sizeof(Queue));
	q->head = NULL;
	q->tail = NULL;

	enqueue(&q->head,&q->tail, root);

	BSTNode *node;
	while (q->head != NULL)
	{
		node = dequeue(&q->head, &q->tail);
		printf("%d ", node->item);
		if(node->left != NULL){
			enqueue(&q->head, &q->tail, node->left);}
		if(node->right != NULL){
			enqueue(&q->head, &q->tail, node->right);}

	}
	

    
}

Q2. inOrderIterative

오직!
스택만 써서, 중위순회를 구현하라.

근데 사실 스택이 중위 순회다....

스택에 현재 노드 넣음.
스택에 오른쪽 노드 넣음.
스택에 왼쪽 노드 넣음.

가장 위에 노드 꺼내서 확인.

현재 노드 넣음.
오른쪽 노드 넣음.
왼쪽 노드 넣음...
...

...
하다가 null에 도달하면
그제서야 스택을 다 꺼내서 하나둘석삼너구리뭐시기 하는것이다.

void inOrderTraversal(BSTNode *root)
{
	Stack *s = malloc(sizeof(Stack));
	s->top = NULL;

	push(s, root);

	while (s->top != NULL)
	{
		BSTNode *node = pop(s);
		if(node->left != NULL){
			push(s, node->left);}
		printf("%d ", node->item);
		if(node->right != NULL){
			push(s, node->right);}
	}
	


}

어라 그냥 중위순회 했네
헤헤

재귀같은 구조인대신에 Push, pop으로만 썼네...

Q3. preOrderIterative

스택만 써서 전위 순회 구현하기.

.....

그냥 그대로 하면 안되나?
(아까같은 구조인데 맨 처음에 프린트..)

void preOrderIterative(BSTNode *root)
{
	Stack *s = malloc(sizeof(Stack));
	s->top = NULL;

	push(s, root);

	while (s->top != NULL)
	{
		BSTNode *node = pop(s);
		printf("%d ", node->item);
		if(node->right != NULL){
			push(s, node->right);}
		if(node->left != NULL){
			push(s, node->left);}
	}
	
}

안 되네.
그래도 원래 구조에서 수정하려고 용씀.
아예 대신 오른쪽부터 넣고..왼쪽부터 넣고..

재귀와 달리
거기서 끝나는게 아니라
단지 꺼내는 순서가 다를 뿐이니까
...
print를 사실 어디서 하든
현재 노드를 출력한다면 값이 똑같거든....

근데 이제...
그게.... 후위 순회가 되면
루트를 맨 마지막에 출력하면서 부터 이제 대환장이 된다.

Q4. preOrderIterativeS1

후위 순회를 스택 한 개로 구현해라.

.........

하....

// 이건 진짜 지피티가 짜줬는데 하........대충 알겠으면서도 
// 전혀 납득이 안된다....... 나중에 복습해야지.
void postOrderIterativeS1(BSTNode *root)
{	

	Stack *stack = malloc(sizeof(Stack));
    stack->top = NULL;

    BSTNode *current = root;
    BSTNode *lastVisited = NULL;

    while (current != NULL || !isEmpty(stack))
    {
    	// 현재 값이 비지 않았다면 저장하고 왼쪽을 현재로.
        if (current != NULL)
        {
            push(stack, current);
            current = current->left;
        }
        // 그렇게 왼쪽을 전부 넣었다면 스택의 가장 위쪽을 슬쩍 봐서
        else
        {
            BSTNode *temp = peek(stack);
			// 확인한 값의 오른쪽이 안 비었고, 방문한 적도 없다면.
            if (temp->right != NULL && lastVisited != temp->right)
            {
            //또 오른쪽 탐험해야지.
                current = temp->right;
            }
            // 여기 탐험 끝냈다면 이제부터 확인할게.
            else
            {
                pop(stack);
                printf("%d ", temp->item);
                lastVisited = temp;
            }
        }
    }

    // 메모리 해제
    free(stack);

}

...
...

스택으로 다음 왼쪽으로 움직이는걸
while과 현재 변수 current로 깔끔하게 구현했군.

그리고 오른쪽이 방문했는지 아닌지도
last visitied 같은 요소를 써서
이미 프린트한 건 프린트 안 하되
다 뽑게 구현했어.

그래서 최종적으로는
오른쪽을 다 방문하면
남은 왼쪽이 스택에서 다 뽑히겠지....

push 해놓고 current 갱신,
그리고
출력한 경우를 변수로 저장하는 건 꽤 인상깊다.

Q5. postOrderIterativeS2

후위 순회를 스택 두 개로 구현해라.

........

후위 순회가 아마
왼->오->루트 인데

그래서 관건은 내가 지금 스택에 넣을 루트가
나중에 프린트 되어야한다는 점이다.

그래서...

루트 봄
(두번째 스택에 루트넣음)
왼쪽 넣음
오른쪽 넣음

그리고 왼쪽 봄....
해서 현재의 스택에서 확인하되
진행 상황은 두번째 스택에 저장하는 거지....

void postOrderIterativeS2(BSTNode *root)
{
	Stack *s1 = malloc(sizeof(Stack));
	Stack *s2 = malloc(sizeof(Stack));
	s1->top = NULL;
	s2->top = NULL;

	push(s1, root);

	while (s1->top != NULL)
	{
		BSTNode *node = pop(s1);
		push(s2, node);
		if(node->left != NULL){
			push(s1, node->left);}
		if(node->right != NULL){
			push(s1, node->right);}
	}

	while (s2->top != NULL)
	{
		BSTNode *node = pop(s2);
		printf("%d ", node->item);
	}
	
	free(s2);
	free(s1);

}