二分探索木の実装

• 練習としてpythonで書いてみました
• こちらの記事を参考にさせて頂きました

BST.py

import random

class Node:
    """
    nodeをクラスとして実装する
    """
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None
        
class Binary_search_tree: #binary search tree
    """
    二分探索木本体の実装
    機能としては、挿入処理、検索（インターフェース）、検索機能本体、ソート出力
    """
    def __init__(self,value_list):
        self.root = None
        for value in value_list:
            self.insert(value)
            
    def insert(self,new_value):
        root_node = self.root
        if root_node is None:
            self.root = Node(new_value)
            return
        current_node = root_node
        while True:
            current_node_value = current_node.value
            if new_value < current_node_value:
                if current_node.left is None:
                    current_node.left = Node(new_value)
                    return
                current_node = current_node.left
            elif new_value > current_node.value:
                if current_node.right is None:
                    current_node.right = Node(new_value)
                    return
                current_node = current_node.right
            else:
                current_node.value = new_value
                return
            
    def search(self,value):
        is_value = self._is_value(value)
        if is_value is None:
            print('検索対象がありません')
        elif is_value:
            print(str(value) + 'が見つかりました！')
        elif not is_value:
            print(str(value) + 'は見つかりませんでした')
            
    def _is_value(self,value):
        root_node = self.root
        if root_node is None:
            return None
        
        search_list = []
        search_list.append(root_node)
        while len(search_list) > 0:
            node = search_list.pop()
            if node.value == value:
                return True
            if node.right is not None:
                search_list.append(node.right)
            if node.left is not None:
                search_list.append(node.left)
        return False
     
    def inorder(self,node):
        if node:
            self.inorder(node.left)
            print(node.value)
            self.inorder(node.right)

テスト

test.py

# 整数列Aの生成---------------------------------------------
# ランダム整数列Aの生成
iarray_A = list(range(50))
random.shuffle(iarray_A)
print(iarray_A)
# ---------------------------------------------------------

# テスト----------------------------------------------------
tree = Binary_search_tree(iarray_A) #配列から二分探索木生成し、treeに代入
tree.search(10)#１０がtreeに存在するか検索
tree.inorder(tree.root) #中順走査、１～順にソート
# ---------------------------------------------------------

テスト結果

10が見つかりました！
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49