Python TreeNode如何实现树的二叉搜索树

   2024-10-01 9410
核心提示:要实现一个树的二叉搜索树,需要定义一个TreeNode类,并实现插入、查找、删除等操作。下面是一个示例代码实现:class TreeNode:d

要实现一个树的二叉搜索树,需要定义一个TreeNode类,并实现插入、查找、删除等操作。下面是一个示例代码实现:

class TreeNode:    def __init__(self, key):        self.val = key        self.left = None        self.right = None        def insert(self, key):        if self.val is None:            self.val = key        else:            if key < self.val:                if self.left is None:                    self.left = TreeNode(key)                else:                    self.left.insert(key)            else:                if self.right is None:                    self.right = TreeNode(key)                else:                    self.right.insert(key)        def find(self, key):        if key == self.val:            return True        elif key < self.val:            if self.left is None:                return False            else:                return self.left.find(key)        else:            if self.right is None:                return False            else:                return self.right.find(key)        def delete(self, key):        if key < self.val:            if self.left:                self.left = self.left.delete(key)        elif key > self.val:            if self.right:                self.right = self.right.delete(key)        else:            if self.left is None:                return self.right            elif self.right is None:                return self.left            temp = self.right            min_val = temp.val            while temp.left:                temp = temp.left                min_val = temp.val            self.val = min_val            self.right = self.right.delete(min_val)        return self        def inorder_traversal(self):        result = []        if self:            result += self.left.inorder_traversal() if self.left else []            result.append(self.val)            result += self.right.inorder_traversal() if self.right else []        return result# 示例代码root = TreeNode(6)root.insert(3)root.insert(9)root.insert(1)root.insert(5)root.insert(7)root.insert(11)print(root.find(5))  # Trueprint(root.find(8))  # Falseroot.delete(3)print(root.inorder_traversal())  # [1, 5, 6, 7, 9, 11]

在上面的示例代码中,我们定义了一个TreeNode类,包括插入、查找、删除和中序遍历等方法。通过这些方法,我们可以实现一个二叉搜索树,并进行相关操作。

 
举报打赏
 
更多>同类物流大全
推荐图文
推荐物流大全
点击排行

网站首页  |  关于我们  |  联系方式网站留言    |  赣ICP备2021007278号