기억보단 기록을

다른게 어려운게 아니라, 트리를 구성후 leaf node에서 순서쌍을 통해 명제식을 검사하는데

순열알고리즘이 들어간다. (자료구조수업인데 ㅠ)

재귀함수를 통해 leafnode까지 내려간후, leafnode에는 true 혹은 false를 담게 된다.

이는 switch 문의 default값을 통해 처리하게되는데, testcase는 알파벳순으로 a,b,c... 입력되는 값에 맞추어

node->data - 'a'를 통해 인덱스값을 확인하게된다. (a는 0번인덱스, b는 1번인덱스 ... 이런식)

이렇게 값을 정해주고 root까지 거슬러 올라가며 이 순서쌍은 참인지 정하게 된다.

그렇다면 모든 순서쌍을 어떻게 구할까.

순열을 통해 모든 순서쌍을 구해준다.

물론 이진수개념인 비트마스크를 통해 구할수 있을것 같기도 하다.

앞서 inorder preorder postorder 방식은 다루었었다.

이번에는 스택에서 다룬 postfix expression을 한번 트리로 구현해보자.

input: AB/C*D*E+

원리는 먼저  연산자가 나올때까지 operand를 스택에 넣고, 연산자가 나온다면 pop해서 오른쪽자식, 왼쪽자식에 하나씩 넣어준다. 그러면 그 부모노드가 또 스택에 들어가 다음번 연산자의 자식으로 되기때문에 inorder traversal을 통해 infix notation을 얻을수 있다.

추가로 구현한 leverOrder traversal

트리는 구조체로써 leftchild와 rightchild를 가짐

트리의 모양을 유지하며 노드를 추가하기 위해선, 큐를 사용해야 한다.

먼저 들어오는 모든 노드에 대해 큐에 넣고, 큐의 front에 있는 노드의 왼쪽자식과 오른쪽자식이둘다모두 존재할때 비로소 ,delete 큐를 해준다. 그렇게 되면 자연스럽게큐의 front는 항상 부모노드가 되며, 이 부모노드의 자식이 모두있을경우 다음노드로 이동하게 된다.

트리의 순회방식

inorder :  왼쪽 방문 오른쪽

preorder :  방문 왼쪽 오른쪽

postorder : 왼쪽 오른쪽 방문

leverorder : 트리노드의 순서대로순회 (다음장에서 다룸)

이번에 해볼 문제는 러시안룰렛 게임이라고 부르는 요셉의문제이다.

총 게임에 임하는 인원수와 건너뛸 점프숫자를 입력받아 마지막 생존자가 나올때까지 인원을 줄여나가는 프로그램이다.

원형연결리스트(CIrcular Linked List)로 구현해보았다.

인터페이스(Interface) 는 추상클래스의 개념과 거의 동일하다. 하지만 추상클래스보다 조금더 추상적으로나아가, 단지 설계만을 위해 존재한다. 또한 자바에서 원래 다중상속은 불가능하지만, 다중상속과 비슷한기능을 제공할수 있게한다.

인터페이스는 추상클래스보다 더욱더 설계를 위한것이기에, 함수내용의 정의를 할 수 없다. 하려하면 에러가 난다.

extends 대신 implements 사용하면된다. 

단 interface를 하나만 상속할수있는것은 아니다.

Abstract보다 더 설계를위한것이니, 나중에 프로젝트를 위해선 abstract 보단 interface를 더 많이 쓸것 같다.

객체를 직접 생성할 수 있는 클래스를 실체클래스라고 하는데, 실체클래스들의 공통적인 특성을 추출해서 선언한 클래스를 추상클래스라고 한다. 여기서 추상클래스와 실체클래스는 상속적인 관계를 가지고 있다.

한마디로 꼭필요한 특성들을 빼먹지 마라고 만든것같은데, 실전에서 어떻게 쓰이는진 잘 모르겠다.

추상클래스 Animald을 정의했다. 모든동물은 종이있고, 다리가있으며 숨을쉰다. 

메서드의 경우 따로 정의하지않고 abstract로써 추후 포함하는것만 의미할수도 있다.

abstract 된 메소드는 상속받은 클래스에서 꼭 넣어줘야한다.