欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python构建一颗二分搜索树

程序员文章站 2023-12-29 11:31:40
...

二分搜索树特点:

  • 二分搜索树的每个节点的值,大于其左子树的所有节点的值;小于其右子树的所有节点的值;
  • 每一颗子树也是二分搜索树。
    Python构建一颗二分搜索树
    Python代码实现:
class Node:
    '''定义节点'''
    def __init__(self, val):
        self.val = val      # 当前值
        self.left = None    # 左孩子
        self.right = None   # 右孩子


class BST:
    def __init__(self):
        self.root = None  # 根节点
        self.count = 0    # 节点个数

    def size(self):
        '''返回节点个数'''
        return self.count

    def is_empty(self):
        '''二分搜索树是否为空'''
        return self.count == 0

    def insert(self, item):
        '''
        调用_insert函数添加元素item,
        返回新二分搜索树的根节点
        '''
        self.root = self._insert(self.root, item)

    def is_contain(self, item):
        '''查看该二分搜索树中是否包含某个元素'''
        return self._contain(self.root, item)

    def _insert(self, node, item):
        '''递归实现添加元素'''

        # 如果此节点为空,则将元素添加到此节点
        if node is None:
            self.count += 1
            return Node(item)
        # 传入的值若小于此节点值,则应放入该节点的左子树中
        if item < node.val:  
            node.left = self._insert(node.left, item)
        # 传入的值若大于此节点值,则应放入该节点的右子树中
        elif item > node.val:
            node.right = self._insert(node.right, item)
        # 传入的值若等于此节点值,则不做事情
        else:
            pass
        return node

    def _contain(self, node, item):
        '''递归查找是否包含某个元素'''

        # 当前传入节点为空,未找到该元素
        if node is None:
            return False
        # 等于当前节点值,找到了该元素
        if item == node.val:
            return True
        # item小于当前节点值,则继续在左子树中查找
        elif item < node.val:
            return self._contain(node.left, item)
        # item大于当前节点值,则继续在右子树中查找
        else:
            return self._contain(node.right, item)

    def breadth_travel(self):
        '''广度遍历'''
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.val, end=' ')
            if cur_node.left is not None:
                queue.append(cur_node.left)
            if cur_node.right is not None:
                queue.append(cur_node.right)

    def preorder(self, node):
        '''前序遍历'''
        if node is None:
            return
        print(node.val, end=' ')
        self.preorder(node.left)
        self.preorder(node.right)

    def inorder(self, node):
        '''中序遍历'''
        if node is None:
            return
        self.inorder(node.left)
        print(node.val, end=' ')
        self.inorder(node.right)

    def postorder(self, node):
        '''后序遍历'''
        if node is None:
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val, end=' ')


if __name__ == '__main__':
    import random
    random.seed(666)
    tree = BST()
    for _ in range(10):
        tree.insert(random.randint(10, 100))
    # 中序遍历可将二分搜索树值从小到大排列
    print('中序遍历: ', end='')
    tree.inorder(tree.root)
    print()
    print('是否存在"80":', tree.is_contain(80))
相关标签: 二叉树

上一篇:

下一篇: