Pythonで２分探索木の実装 (1)

python algorithm

完全２分木はターゲットせずに、ALDS1_8をターゲットとして考える。

ALDS1_8を基準に実装していくので以下のようになっている。

  • ノードの検索には、再帰ではなくWhileを用いる
  • ParentもNodeの情報として持つ
  • ノードの追加時に再配置について加味しない

削除については別途記事にする。

巡回について

実装上は、どこで print するか。という話なる。

f:id:clavier:20190616205716p:plain

先行順巡回(Preorder Tree Walk)

根節点、左部分木、右部分木の順で節点の番号を出力する。

 1 3 7 14 21 35 42 56 70 80 81 86 99
中間順巡回(Inorder Tree Walk)

左部分木、根節点、右部分木の順で節点の番号を出力する。

 35 3 1 14 7 21 80 42 70 56 86 81 99
後行順巡回(Postorder Tree Walk)

左部分木、右部分木、根節点の順で節点の番号を出力する。

 1 7 21 14 3 56 70 42 81 99 86 80 35

削除以外の実装

ノードの削除以外は特に考えること無く実装していくことが出来ると思う。 入出力は ALDS1_8 に合わせている。 先頭の insert が根(root) になる。という実装になっている。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None


# BinarySearchNode
class BTS(list):
    def __init__(self):
        list.__init__(self)
        self.root = None
    
    def insert(self, value):
        z = Node(value)
        y = None
        x = self.root

        while x is not None:
            y = x
            if z.value < x.value:
                x = x.left
            else:
                x = x.right
        
        z.parent = y
        if y is None:
            self.root = z
        elif z.value < y.value:
            y.left = z
        else:
            y.right = z
    
    def recursiveFind(self, value):
        print("find", value)
        def findBTS(node):
            
            if node == None:
                return None
            if node.value == value:
                return node
            elif node.value > value:
                return findBTS(node.left)
            else:
                return findBTS(node.right)
        return findBTS(self.root)

    def find(self, value):
        x = self.root
        while x is not None and value != x.value:
            if value < x.value:
                x = x.left
            else:
                x = x.right
        return x
    
    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.value), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.value), end="")
            inParse(u.right)
        inParse(self.root)
        print("")
    
    def postorder(self):
        def postParse(u):
            if u == None:
                return
            postParse(u.left)
            postParse(u.right)
            print(" " + str(u.value), end="")
        postParse(self.root)
        print("")


if __name__ == '__main__':
    n = int(input())
    T = BTS()

    for _ in range(n):
        c = input().split(" ")
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            z = T.find(int(c[1]))
            if z is None:
                print("no")
            else:
                print("yes")
        elif c[0] == "delete":
            z = T.find(int(c[1]))
            T.delete(z)
        else:
            T.inorder()
            T.preorder()
            T.postorder()

入力として以下のような値を渡す。

15
insert 35
insert 3
insert 1
insert 14
insert 7
insert 21
insert 80
insert 42
insert 70
insert 56
insert 86
insert 81
insert 99
print
find 50

実行結果は以下のような感じになる。

 1 3 7 14 21 35 42 56 70 80 81 86 99
 35 3 1 14 7 21 80 42 70 56 86 81 99
 1 7 21 14 3 56 70 42 81 99 86 80 35
no