首页 > 代码库 > [数据结构与算法分析(Mark Allen Weiss)]二叉树的插入与删除 @ Python
[数据结构与算法分析(Mark Allen Weiss)]二叉树的插入与删除 @ Python
二叉树的插入与删除,来自Mark Allen Weiss的《数据结构与算法分析》。
# Definition for a binary tree nodeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass BinarySearchTree: # @param root, a tree node # @return a list of integers def Insert(self, root, x): if root == None: root = TreeNode(x) else: if x < root.val: root.left = self.Insert(root.left, x) if x > root.val: root.right = self.Insert(root.right, x) return root def Delete(self, root, x): if root: if x < root.val: root.left = self.Delete(root.left, x) elif x > root.val: root.right = self.Delete(root.right, x) elif root.left and root.right: tmp = self.FindMin(root.right) root.val = tmp.val root.right = self.Delete(root.right, root.val) elif root.left: root = root.left elif root.right: root = root.right return root def FindMin(self, root): if root: while root.left: root = root.left return root def preorder(self, root): if root: print root.val self.preorder(root.left) self.preorder(root.right)Tree = BinarySearchTree()root = Nonelist = [6, 2, 8, 1, 5, 3, 4]for i in range(len(list)): root = Tree.Insert(root, list[i])Tree.preorder(root)Tree.Delete(root, 2)Tree.preorder(root)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。