1. Tree

• 트리구조란 자료구조중 하나로 나무형태의 구조를 갖고 있다. 자식의 최대 갯수의 따라 Binary Search Tree(2개), Ternary Search Tree(3개)로 명칭이 바뀐다.

• Properties

  • children : 자식노드
  • parentNode : 부모노드
  • siblingsNode : 형제노드
  • rootNode : 뿌리노드, 최초노드, 부모노드가 없는 노드
  • leafNode : 가장 끝의 노드, 자식노드가 없는 노드
  • Edge : 노드와 노드를 이어주는 선

• Methods

  • addChild() : 자식노드를 추가하는 함수
  • contains() : 값을 넣어 그 값을 가진 자식노드가 존재하는지 Boolean타입으로 반환하는 함수
  • removeChild() : 자식노드를 없애주는 함수

2. Binary Search Tree(이진탐색트리)

• 이진탐색트리란

  A binary search tree is a binary tree with the following properties:
  1) The data stored at each node has a distinguished key which is unique in the tree and belongs to a total order.
  2)The key of any node is greater than all keys occurring in its left subtree and less than all keys occurring in its right subtree.
  이진 탐색 트리란 다음의 속성을 충족하는 2개의 자식노드를 갖고 있는 트리구조이다.
  1) 각 노드에 저장된 데이터에는 트리에서 고유하고 전체 순서에 속하는 고유한 키가 있다.
  2) 노드의 키는 왼쪽 하위 트리에서 발생하는 모든 키보다 크고, 오른쪽 하위 트리에서 발생하는 모든 키보다 작다.

   //이진탐색트리란 최대 2개이상의 자식노드를 가진 노드를 말하며, 
   이진탐색(Binary Search)와, 연결리스트(Linked List)를 결합한 자료구조의 일종이며,
   이진탐색의 효율적인 탐색능력을 유지하면서도 입력과 삭제를 사용가능하게끔 만들어진 자료구조//

• Properties

  • leftNode : 현재 값보다 갖고있는 값이 낮은 노드
  • rightNode : 현재 값보다 높은 노드
    이외는 1.에서 언급했던 Tree구조의 속성들과 동일하다.

• Methods

  • insert() : 원하는 장소에 원하는 값을 넣어줄수 있는 함수
  • DFS,깊이우선검색(DepthFirstSearch) : rootNode로부터 자식노드 하나를 끝까지 탐색하고, 없다면 다시 되돌아와 탐색했던 자식노드의 형제노드를 다시 탐색하는 함수, Stack을 이용해 구현가능
    • inOrder : 0 1 3 4 2 5 6
    • preOrder : 3 1 4 0 5 2 6
    • postOrder : 3 4 1 5 6 2 0
  • BFS,넓이우선검색(BreadthFirstSearch) : rootNode의 자식노드들을 하나씩 탐색하고, 원하는 결과가 나오지 않을시 그 자식노드의 자식노드를 탐색해 나가는 함수, Queue를 이용해 구현가능

3.Graph

• 그래프란