方法一(粗暴)
#二叉排序树
class BTree():
def __init__(self,data):
self.left = None
self.right = None
if type(data) == list:
self.data = data[0]
for d in data[1:]:
self.insert(d)
else:
self.data = data
def insert(self,data):
bt = self
while True:
if data <= bt.data:
if bt.left == None:
bt.left = BTree(data)
break
else:
bt = bt.left
else:
if bt.right == None:
bt.right = BTree(data)
break
else:
bt = bt.right
def mid_order(self):
res = []
stack = []
node = self
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.data)
node = node.right
return res
data = [5,1,2,3,6,8,9]
bt = BTree(data)
print(bt.mid_order())
方法二(递归)
class TreeNode(object):
def __init__(self,data):
self.data = data
self.left = None
self.right = None
class BinaryTree(object):
def insert(self,root, node):
if root is None:
return node
if node.data < root.data:
root.left = self.insert(root.left, node)
else:
root.right = self.insert(root.right, node)
return root
def mid_order(self,root):
node = root
stack = []
res = []
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.data)
node = node.right
return res
data = [5,1,2,3,6,8,9]
root = TreeNode(data[0])
tree = BinaryTree()
for i in data[1:]:
tree.insert(root,TreeNode(i))
print(tree.mid_order(root))
到此这篇关于python实现二叉排序树的文章就介绍到这了,更多相关python二叉排序树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!