python 搜索樹

二叉搜索樹（bst）是一棵樹，其中所有節點都遵循下述屬性 - 節點的左子樹具有小于或等于其父節點密鑰的密鑰。節點的右子樹具有大于其父節點密鑰的密鑰。因此，bst將其所有子樹分成兩部分; 左邊的子樹和右邊的子樹，可以定義為 -

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

在b-tree中搜索一個值

在樹中搜索值涉及比較輸入值與退出節點的值。在這里，我們也從左到右遍歷節點，最后是父節點。如果搜索到的值與任何exitign值都不匹配，則返回未找到的消息，否則返回找到的消息。

class node:

    def __init__(self, data):

        self.left = none
        self.right = none
        self.data = data

# insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is none:
                    self.left = node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is none:
                    self.right = node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is none:
                return str(lkpval)+" not found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is none:
                return str(lkpval)+" not found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# print the tree
    def printtree(self):
        if self.left:
            self.left.printtree()
        print( self.data),
        if self.right:
            self.right.printtree()

root = node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

當上面的代碼被執行時，它會產生以下結果 -

7 not found
14 is found