python二叉排序树
咕嘟咕嘟_ 人气:0方法一(粗暴)
#二叉排序树 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))
加载全部内容