{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Tree 이진트리\n",
    "\n",
    "이진트리를 어떻게 정의할지 알아보기로 합시다.\n",
    "\n",
    "일단 이진트리라는 데이터 구조 자체도 약간씩 다른 버전으로 정의할 수 있습니다.\n",
    " * 트리의 어느 부분에 원소를 놓을지\n",
    "     * 트리 노드(가지가 갈라지는 부분)에\n",
    "     * 트리의 잎사귀(더 이상 가지가 갈라지지 않는 끄트머리)에\n",
    "     * 위의 두 곳에 다\n",
    " * 아무 원소도 없는 빈 경우 이진트리로 간주할지 아니면 최소한 한 개의 값이 있는 경우부터 이진트리로 간주할지\n",
    "\n",
    "이 중에서 우리는 트리의 노드 부분에만 원소가 나타나고 아무 원소도 없는 빈 이진트리도 포함하는 정의를 따릅시다.\n",
    "\n",
    "그러니까 이진트리를 구성하는 다음의 두 가지란 말이죠.\n",
    "  1. 아무것도 없는 빈 노드\n",
    "  2. 하나의 원소와 두 개의 하위 이진트리로 구성된 노드\n",
    "  \n",
    "이렇게 정의를 하나로 고정시켜 놓더라도 Java로 이것을 작성하는 방법이 또 여러가지가 있을 수 있다.\n",
    "\n",
    "사실 Java에서만 그런 게 아니라 공통점이 많은 C++이나 C# 등에서도 이건 마찬가지."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## `null`을 활용한 가장 간단한 방법\n",
    "\n",
    "Java, C#, C++/C 등으로 이진트리 소스코드를 찾아보면 이 방법으로 가장 많이 소개됨"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "// null 을 빈 이진트리라고 생각하자\n",
    "\n",
    "// 노드를 나타내는 class 딱 하나만 정의하면 끝!!\n",
    "class Tree {\n",
    "    int value;\n",
    "    Tree left;\n",
    "    Tree right;\n",
    "    // 생성자\n",
    "    Tree(int v, Tree l, Tree r) { value=v; left=l; right=r; }\n",
    "    @Override\n",
    "    public String toString() {\n",
    "        return value+\"@{ \"+left+\"; \"+right+\" }\";\n",
    "    }\n",
    "    \n",
    "    boolean has(int v) { // 매번 has를 호출하기 전에 null인지 아닌지 검사를 해줘야 함\n",
    "        return v == value\n",
    "            || (left !=null) && left.has(v)\n",
    "            || (right!=null) && right.has(v);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*\n",
    "  2\n",
    " / \\\n",
    "1   3\n",
    "     \\\n",
    "      4\n",
    "*/\n",
    "\n",
    "Tree t0 = null; // 빈 트리는 이렇게 정의하겠죠\n",
    "\n",
    "Tree t1 = new Tree(2,\n",
    "                   new Tree(1, null, null),\n",
    "                   new Tree(3,\n",
    "                            null,\n",
    "                            new Tree(4, null, null) ) );"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2@{ 1@{ null; null }; 3@{ null; 4@{ null; null } } }"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// t1의 정의를 직접 코드에서 하지 않고 입력받거나 프로그램에서 계산했다면 항상 null인지 아닌지 검사하면서\n",
    "(t1!=null) && t1.has(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "null == null"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// t0의 정의를 직접 코드에서 하지 않고 입력받거나 프로그램에서 계산했다면 항상 null인지 아닌지 검사하면서\n",
    "(t0!=null) && t0.has(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## 파일/폴더 예제처럼 좀더 일반적인 방법(composite pattern)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "abstract class ATree {\n",
    "    abstract boolean has(int v);\n",
    "}\n",
    "\n",
    "class Null extends ATree {\n",
    "    @Override\n",
    "    public String toString() { return \"Null\"; }\n",
    "    @Override\n",
    "    boolean has(int v) { return false; }\n",
    "}\n",
    "\n",
    "class Node extends ATree {\n",
    "    int value;\n",
    "    ATree left;\n",
    "    ATree right;\n",
    "    // 생성자\n",
    "    Node(int v, ATree l, ATree r) { value=v; left=l; right=r; }\n",
    "    @Override\n",
    "    public String toString() {\n",
    "        return value+\"@{ \"+left+\"; \"+right+\" }\";\n",
    "    }\n",
    "    @Override // ATree를 구성하기 위해서 null을 활용하지 않으므로 널포인터 검사 불필요\n",
    "    boolean has(int v) { return v == value || left.has(v) || right.has(v); }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "ATree nil = new Null(); // 나도 빈 트리인데\n",
    "ATree nil2 = new Null(); // 너도 빈 트리구나"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "ATree t2 = new Node(2,\n",
    "                   new Node(1, nil, nil),\n",
    "                   new Node(3,\n",
    "                            nil,\n",
    "                            new Node(4, nil, nil) ) );"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2@{ 1@{ Null; Null }; 3@{ Null; 4@{ Null; Null } } }"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t2.has(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nil == nil"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nil2 == nil"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nil.has(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "name": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}