用Python构建二叉搜索树
###### 问题遇到的现象和发生背景
给定一个整数序列v1
二叉搜索树T是从 vi通过插入值v1,v2,v3为该顺序
建树T并逐层输出其顶点。
我们假设所有键在搜索树中都是唯一的。因此，当您尝试添加树中已有的键时，应将其忽略。
输入数据格式
输入包含一个数字序列 vi，顶点的键按插入树的顺序排列。每行包含一个数字。
输出数据格式
打印与树中的级别一样多的行 T. 在每一行中按升序打印相应级别顶点的键。
###### 例子
输入数据格式 输出数据格式
###### 我想要达到的结果
用Python编写并写一下注释
class TreeNode:
def init(self, item, less=None, more=None, parent=None):
self.item = item # 代表当前节点
self.less = less # 小于当前节点的分支
self.more = more # 大于当前节点的分支
if parent is not None:
self.parent = parent
@property
def parent(self):
return self.parent_ref()
@parent.setter
def parent(self,value):
# 使用弱引用，方便内存回收。
self.parent_ref = weakref.ref(value)
def __repr__(self):
return ("TreeNode({item!r},{less!r},{more!r})".format(**self.__dict__))
def find(self, item):
if self.item is None:
# 为None时代表当前为根节点，所以向more分支递归搜索。
if self.more:
return self.more.find(item)
elif self.item == item:
# 相等时为找到了节点
return self
elif self.item > item and self.less:
# 如果当前节点大于目标对象，并且小于分支存在的话，那么向less分支递归搜索
return self.less.find(item)
elif self.item < item and self.more:
# 如果当前节点小于目标对象，并且大于分支存在的话，那么向more分支递归搜索
return self.more.find(item)
# 如果以上判断都不符合条件，那么搜索的元素不存在
raise KeyError
def __iter__(self):
# 如果当前节点小于分支存在，那么遍历并返回。
# 使用yield可以节省开销。
if self.less:
for item in iter(self.less):
yield item
# 返回当前节点
yield self.item
# 如果当前节点大于分支存在，那么遍历并返回。
if self.more:
for item in iter(self.more):
yield item
def add(self, item):
# 为None时代表当前为根节点，向more分支添加节点
if self.item is None:
if self.more:
self.more.add(item)
else:
self.more = TreeNode(item, parent=self)
# 如果当前节点大于等于添加节点，那么向less分支添加节点
elif self.item >= item:
if self.less:
self.less.add(item)
else:
self.less = TreeNode(item, parent=self)
# 如果当前节点小于添加节点，那么向more节点
elif self.item < item:
if self.more:
self.more.add(item)
else:
self.more = TreeNode(item, parent=self)
def remove(self, item):
# 如果当前节点为None或者目标节点大于当前节点，那么向more分支递归
if self.item is None or item> self.item:
if self.more:
self.more.remove(item)
else:
raise KeyError
# 如果目标节点小于当前节点，那么向less分支递归
elif item < self.item:
if self.less:
self.less.remove(item)
else:
raise KeyError
else: # self.item == item 即找到了目标元素
# 如果当前节点具有less分支和more分支
if self.less and self.more:
successor = self.more._least() # 递归找当前节点more分支中的最小节点
self.item = successor.item # 并将当前节点的值设置为最小节点的值
successor.remove(successor.item) # 继续递归寻找合适的_replace操作
# 如果当前节点仅有less分支
elif self.less:
self._replace(self.less)
elif self.more:
self._replace(self.more)
# 叶子节点
else:
self._replace(None)
def _least(self):
# 递归搜索最小的节点
if self.less is None:
return self
return self.less._least()
def _replace(self,new=None):
# 如果当前节点存在父节点
if self.parent:
# 如果当前节点在父节点的小于分支，那么将小于分支设置为new值
if self == self.parent.less:
self.parent.less = new
# 如果当前节点在父节点的大于分支，那么将大于分支设置为new值
else:
self.parent.more = new
# 如果指定了父节点，那么替换父节点指向
if new is not None:
new.parent = self.parent
from collections import MutableSet
import weakref
class Tree(MutableSet):
# 根节点没有值，即None
def init(self, iterable=None):
self.root = TreeNode(None) # 代表根节点
self.size = 0 # 这个树结构的大小
if iterable: # 接受一个可迭代对象，并加载对象的所有元素
for item in iterable:
self.root.add(item)
def add(self, item):
# 每有元素添加，当将大小加1，这样当我们需要知道当前节点总数时就不需要遍历了。
self.root.add(item)
self.size += 1
def discard(self, item):
# 每有元素添加，当将大小减1，这样当我们需要知道当前节点总数时就不需要遍历了。
try:
self.root.remove(item)
self.size -= 1
except KeyError:
pass
def __contains__(self, item):
# 如果当前结构包含item即返回Treu 否则返回False
try:
self.root.more.find(item)
return True
except KeyError:
return False
def __iter__(self):
# 这个函数是控制生成器的函数。
# root节点为None，所以后续的节点在more分支上。
for item in iter(self.root.more):
yield item
def __len__(self):
# 这个函数是控制len(obj)的
return self.size
好久不写算法了。先看看构造显示是否正确
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。
通常采取二叉链表作为二叉查找树的存储结构。
class BinarySearchTree(object):
def __init__(self, data, left=None, right=None, parent=None):
self.data = data
self.left = left
self.right = right
self.parent = parent
class BST(object):
def __init__(self):
self.root = None
self.size = 0
def lenght(self):
return self.size
def find(self, key):
if self.root:
result = self._find(key, self.root)
if result:
return result
else:
return None
else:
None
def _find(self, key, node):
if not node:
return None
elif node.data == key:
return node
elif key < node.data:
return self._find(key, node.left)
else:
return self._find(key, node.right)
def insert(self, key):
node = BinarySearchTree(key)
if not self.root:
self.root = node
self.size += 1
else:
currentNode = self.root
while True:
if key < currentNode.data:
if currentNode.left:
currentNode = currentNode.left
else:
currentNode.left = node
node.parent = currentNode
self.size += 1
break
elif key > currentNode.data:
if currentNode.right:
currentNode = currentNode.right
else:
currentNode.right = node
node.parent = currentNode
self.size += 1
break
else:
break
def findMin(self):
if self.root:
return self._findMin(self.root)
else:
return None
def findMax(self):
if self.root:
currentNode = self.root
while currentNode.right:
currentNode = currentNode.right
return currentNode
else:
return None
def _findMin(self, node):
if node:
currentNode = node
while currentNode.left:
currentNode = currentNode.left
return currentNode
def delete(self, key):
if self.size > 1:
nodeToDelete = self.find(key)
if nodeToDelete:
self._delete(nodeToDelete)
self.size -= 1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.data == key:
self.root = BinarySearchTree(None)
self.size = 0
else:
raise KeyError('Error, key not in tree')
def _delete(self, node):
if not node.left and node.right: #node为树叶
if node == node.parent.left: #node为父节点的左子树
node.parent.left = None
else:
node.parent.right = None
elif node.right and node.left: #node有两个儿子
minNone = self._findMin(node.right)
node.data = minNone.data
self._delete(minNone)
else: #node有一个儿子
if node.left: #node有左儿子
if node.parent and node.parent.left == node: #node为父节点的左子树
node.left.parent = node.parent
node.parent.left = node.left
elif node.parent and node.parent.right == node: #node为父节点的右子树
node.left.parent = node.parent
node.parent.right = node.left
else: # node为根
self.root = node.left
node.left.parent = None
node.left = None
else:
if node.parent and node.parent.left == node:
node.right.parent = node.parent
node.parent.left = node.right
elif node.parent and node.parent.right == node:
node.right.parent = node.parent
node.parent.right = node.right
else:
self.root = node.right
node.right.parent = None
node.right = None
def printTree(self):
if self.size == 0:
print("Empty Tree")
else:
self._printTree(self.root)
def _printTree(self, node):
if node: #中序遍历
self._printTree(node.left)
print(node.data)
self._printTree(node.right)
通过递归创建地方法即可完成二叉树搜索