## 2019年4月12日金曜日

### Algorithm - Python - 質問するにもお金がかかる - オブジェクト指向プログラミング、二分探索木 - データ構造の変更、節点数

コード

Python 3

```#!/usr/bin/env python3
from unittest import TestCase, main

class BSTreeTest(TestCase):
def setUp(self):
self.t0 = BSTree()
self.t1 = BSTree(BSTVertex(22))
self.t2 = BSTree(BSTVertex(22,
BSTVertex(21)))
self.t3 = BSTree(BSTVertex(22,
BSTVertex(21),
BSTVertex(23, None, BSTVertex(24))))

def tearDown(self):
pass

def test_size_zero(self):
self.assertEqual(0, self.t0.size())

def test_size_one(self):
self.assertEqual(1, self.t1.size())

def test_size_two(self):
self.assertEqual(2, self.t2.size())

def test_size_four(self):
self.assertEqual(4, self.t3.size())

class BSTVertex:
def __init__(self, val, left_child=None, right_child=None):
self.val = val
self.left_child = left_child
self.right_child = right_child

class BSTree:
def __init__(self, root=None):
self.root = root

def lookup(self, val) -> bool:
def helper(val, vertex):
if vertex == None:
return False
if val == vertex.val:
return True
if val < vertex.val:
return helper(val, vertex.left_child)
return lookup(val, vertex.right_child)
return helper(val, self.root)

def size(self) -> int:
def helper(vertex) -> int:
if vertex is None:
return 0
return 1 + helper(vertex.left_child) + helper(vertex.right_child)
return helper(self.root)

if __name__ == '__main__':
main()
```

```C:\Usrs\...>py sample1.py
F
======================================================================
FAIL: test_size_zero (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample1.py", line 21, in test_size_zero
self.assertEqual(1, tree.size())
AssertionError: 1 != None

----------------------------------------------------------------------
Ran 1 test in 0.000s

FAILED (failures=1)
C:\Usrs\...>py sample1.py
.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK

C:\Usrs\...>py sample1.py
...
----------------------------------------------------------------------
Ran 3 tests in 0.000s

OK

C:\Usrs\...>py sample1.py
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK

C:\Usrs\...>py sample1.py -v
test_size_four (__main__.BSTreeTest) ... ok
test_size_one (__main__.BSTreeTest) ... ok
test_size_two (__main__.BSTreeTest) ... ok
test_size_zero (__main__.BSTreeTest) ... ok

----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK

C:\Users\...>
```