Pythonは二叉検索ツリーBSTを実現

Python実装BST
二叉ソートツリー(BST)は二叉検索ツリー、二叉検索ツリーとも呼ばれる
バイナリ・チャート・ツリー(Binary Sort Tree)は、バイナリ・ツリーとも呼ばれます.あるいは空の木ですあるいは以下の性質を有する二叉木:1.左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はルートノードの値より小さい.2.右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値より大きい.3.左、右のサブツリーもそれぞれ二叉ソートツリーです.

木の深さを求めます

ノード値をシーケンスで出力(中シーケンスを使用)

.

は、二叉検索ツリーのポイントキーを持つノードをクエリーし、ノードの位置を返します.時間的複雑度はO(h),hは木の高さである.

再帰/反復最大キーワード要素

を求める

再帰/反復最小キーワード要素

を求める

# -*- coding:utf-8 -*-
'''
 Python       。
'''


class Node():
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

#     
def depth(root):
        if root is None:
            return 0
        else:
            return 1 + max(depth(root.left), depth(root.right))


#       （    ）
def input_in_order(root):
    if root is  None:
        return
    input_in_order(root.left)
    print(root.val)
    input_in_order(root.right)



#（     、    ）                    ，        。      O(h),h     。
#    
def search1(root, value):
    if root is None or root.val == value:
        return root
    if root.val > value:
        return search1(root.left, value)
    if root.val < value:
        return search1(root.right, value)


#    
def search2(root, value):
    while root != None and root.val != value:
        if root.val > value:
            root = root.left
        elif root.val < value:
            root = root.right
    return root


#        
#    
def max_value1(root):
    while root != None and root.left != None:
        root = root.right
    if root is None:
        return root
    else:
        return root.val

#    
def max_value2(root):
    if root == None:
        return root
    elif root.right == None:
        return root.val
    else:
        return max_value2(root.right)


#        
#    
def min_value1(root):
    if root is None:
        return root
    elif root.left is None:
        return root.val
    else:
        return min_value1(root.left)


#    
def min_value2(root):
    if root is None:
        return root
    while root.left !=None:
        root = root.left
    return root.val


if __name__ == '__main__':
    a = Node(15)
    b = Node(6)
    c = Node(18)
    d = Node(4)
    e = Node(8)
    f = Node(17)
    g = Node(20)
    h = Node(13)
    i = Node(9)
    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.left = f
    c.right = g
    e.right = h
    h.left = i
    print(search1(a, 13))
    print(search2(a,13))
    print(max_value1(a))
    print(max_value2(a))
    print(min_value1(a))
    print(min_value2(a))

ps:ツリーBSTから要素Xを検索し、そのノードのアドレスを返します.検索回数はツリーの高さに依存します.