8
【Python数据结构5】Binary Search Tree
source link: https://www.guofei.site/2018/08/06/binary_search_tree.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【Python数据结构5】Binary Search Tree
2018年08月06日Author: Guofei
文章归类: 8-数据结构与算法 ，文章编号: 555
版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2018/08/06/binary_search_tree.html
介绍
Binary Search Tree(BST) is a special form of a binary tree.
- The value in each node must be greater than (or equal to) any values in its left subtree
- but less than (or equal to) any values in its right subtree
设计一个Binary Search Tree Iterator
并定义next()和hasNext()方法，并且有 O(1) time 和 O(h) memory
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.stack=[]
while root:
self.stack.append(root)
root=root.left
def hasNext(self):
"""
:rtype: bool
"""
return len(self.stack)>0
def next(self):
"""
:rtype: int
"""
node=self.stack.pop()
x=node.right
while x:
self.stack.append(x)
x=x.left
return node.val
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())基本功能
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 注意，标准的二叉树遍历算法中，遇到空节点返回[],而不是[None]
def InOrder(self, root): # LDR
return [] if (root is None) else self.InOrder(root.left) + [root.val] + self.InOrder(root.right)
def PreOrder(self, root): # DLR
return [] if (root is None) else [root.val] + self.PreOrder(root.left) + self.PreOrder(root.right)
def PostOrder(self, root): # LRD
return [] if (root is None) else self.PostOrder(root.left) + self.PostOrder(root.right) + [root.val]
def PrintTree(self, root, i=0):
'''
打印二叉树，凹入表示法。原理是RDL遍历，旋转90度看
'''
tree_str = ''
if root.right:
tree_str += self.PrintTree(root.right, i + 1)
if root.val:
tree_str += (' ' * i + '-' * 3 + str(root.val) + '\n')
if root.left:
tree_str += self.PrintTree(root.left, i + 1)
return tree_str
def find_track(self, num, root, track_str=''):
'''
二叉树搜索
:param num:
:param root:
:param track_str:
:return:
'''
track_str = track_str + str(root.val)
if root.val == num:
return track_str
if root.left is not None:
self.find_track(num, root.left, track_str + ' ->left-> ')
if root.right is not None:
self.find_track(num, root.right, track_str + ' ->right-> ')
def buildTree(self, inorder, postorder):
"""
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
中序+后序确定一棵树，前提是list中没有重复的数字
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not inorder or not postorder:
return None
root = TreeNode(postorder.pop())
inorder_index = inorder.index(root.val)
root.right = self.buildTree(inorder[inorder_index + 1:], postorder)
root.left = self.buildTree(inorder[:inorder_index], postorder)
return root
def buildTree(self, preorder, inorder):
"""
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
前序+中序确定一棵树，前提是list中没有重复的数字
pop(0)效率很低，看看怎么解决
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder or not inorder:
return None
root=TreeNode(preorder.pop(0))
inorder_index=inorder.index(root.val)
root.left=self.buildTree(preorder,inorder[:inorder_index])
root.right=self.buildTree(preorder,inorder[inorder_index+1:])
return root
def list2tree(self, i=1, list_num=[]):
# 顺序结构转链式结构
# 节点标号从1开始
if i > len(list_num):
return None
treenode = TreeNode(list_num[i - 1])
treenode.left = self.list2tree(2 * i, list_num)
treenode.right = self.list2tree(2 * i + 1, list_num)
return treenode
# 还未完成
def tree2list(self):
pass
def levelOrder(self, root):
"""
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
import collections
level = 0
deque = collections.deque([(root,0)])
output=[]
while deque:
tmp_root,level = deque.popleft()
if tmp_root.left: deque.append((tmp_root.left,level+1))
if tmp_root.right: deque.append((tmp_root.right,level+1))
if len(output)<=level:
output.append([tmp_root.val])
else:
output[level].append(tmp_root.val)
return output
def list2tree2(self, nums):
# 与 list2tree 的区别是：对空值不再生成子节点，之后的数据也不会作为这个空节点的子节点，而是跳过，因此更加节省空间。
if not nums:
return None
nodes = [None if val is None else TreeNode(val) for val in nums]
kids = nodes[::-1]
root = kids.pop()
for node in nodes:
if node:
if kids: node.left = kids.pop()
if kids: node.right = kids.pop()
return root
def deserialize(self, string):
# LeetCode官方版本
# https://leetcode.com/problems/recover-binary-search-tree/discuss/32539/Tree-Deserializer-and-Visualizer-for-Python
# deserialize('[2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7]')
# 这里是 deserialize 和 serialize 的案例
# https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/discuss
if string == '{}':
return None
nodes = [None if val == 'null' else TreeNode(int(val)) for val in string.strip('[]{}').split(',')]
kids = nodes[::-1]
root = kids.pop()
for node in nodes:
if node:
if kids: node.left = kids.pop()
if kids: node.right = kids.pop()
return root
def drawtree(self, root):
# 用 turtle 画 Tree，比纯字符串美观，但慢
def height(root):
return 1 + max(height(root.left), height(root.right)) if root else -1
def jumpto(x, y):
t.penup()
t.goto(x, y)
t.pendown()
def draw(node, x, y, dx):
if node:
t.goto(x, y)
jumpto(x, y - 20)
t.write(node.val, align='center', font=('Arial', 12, 'normal'))
draw(node.left, x - dx, y - 60, dx / 2)
jumpto(x, y - 20)
draw(node.right, x + dx, y - 60, dx / 2)
import turtle
t = turtle.Turtle()
t.speed(0);
turtle.delay(0)
h = height(root)
jumpto(0, 30 * h)
draw(root, 0, 30 * h, 40 * h)
t.hideturtle()
turtle.mainloop()
# 以下是BST方法
def isValidBST(self, root):
# 判断是否是BST，返回 True/False
inorder = self.inorder(root)
return inorder == list(sorted(set(inorder)))
def searchBST(self, root, val):
# 搜索 BST，如果val在 BST中，返回对应节点，否则返回None
if root and val < root.val:
return self.searchBST(root.left, val)
elif root and val > root.val:
return self.searchBST(root.right, val)
return root
def insertIntoBST(self, root, val):
"""
把值 val 插入到BST中
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if root is None:
return TreeNode(val)
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
elif root.val > val:
root.left = self.insertIntoBST(root.left, val)
return root
def deleteNode(self, root, key):
"""
删除节点的方式有很多种：左子节点提升，右子节点提升，下面这个思路是把右子树的最左左叶节点作为替换被删节点的值
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root:
return root
if root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
else:
if not root.right:
return root.left
if not root.left:
return root.right
else:
tmp, mini = root.right, root.right.val
while tmp.left:
tmp, mini = tmp.left, tmp.left.val
root.val = mini
root.right = self.deleteNode(root.right, root.val)
return root
def sortedArrayToBST(self, nums):
"""
从一个sorted list生成平衡的BST
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
实用方法
https://leetcode.com/problems/trim-a-binary-search-tree/description/
class Solution(object):
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root:
return None
if root.val < L:
return self.trimBST(root.right, L, R)
if root.val > R:
return self.trimBST(root.left, L, R)
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
您的支持将鼓励我继续创作！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK