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

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の21章(質問するにもお金がかかる)、練習問題(問題1、問題2)の解答を求めてみる。

コード

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()

入出力結果(cmd(コマンドプロンプト)、Terminal、Jupyter(IPython))

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\...>