如何实现二叉树？
哪个是可以用来在Python中实现二叉树的最好的数据结构？
这是我简单的二叉树recursion实现。
#!/usr/bin/python class Node: def __init__(self, val): self.l = None self.r = None self.v = val class Tree: def __init__(self): self.root = None def getRoot(self): return self.root def add(self, val): if(self.root == None): self.root = Node(val) else: self._add(val, self.root) def _add(self, val, node): if(val < node.v): if(node.l != None): self._add(val, node.l) else: node.l = Node(val) else: if(node.r != None): self._add(val, node.r) else: node.r = Node(val) def find(self, val): if(self.root != None): return self._find(val, self.root) else: return None def _find(self, val, node): if(val == node.v): return node elif(val < node.v and node.l != None): self._find(val, node.l) elif(val > node.v and node.r != None): self._find(val, node.r) def deleteTree(self): # garbage collector will do this for us. self.root = None def printTree(self): if(self.root != None): self._printTree(self.root) def _printTree(self, node): if(node != None): self._printTree(node.l) print str(node.v) + ' ' self._printTree(node.r) # 3 # 0 4 # 2 8 tree = Tree() tree.add(3) tree.add(4) tree.add(0) tree.add(8) tree.add(2) tree.printTree() print (tree.find(3)).v print tree.find(10) tree.deleteTree() tree.printTree() # simple binary tree # in this implementation, a node is inserted between an existing node and the root class BinaryTree(): def __init__(self,rootid): self.left = None self.right = None self.rootid = rootid def getLeftChild(self): return self.left def getRightChild(self): return self.right def setNodeValue(self,value): self.rootid = value def getNodeValue(self): return self.rootid def insertRight(self,newNode): if self.right == None: self.right = BinaryTree(newNode) else: tree = BinaryTree(newNode) tree.right = self.right self.right = tree def insertLeft(self,newNode): if self.left == None: self.left = BinaryTree(newNode) else: tree = BinaryTree(newNode) tree.left = self.left self.left = tree def printTree(tree): if tree != None: printTree(tree.getLeftChild()) print(tree.getNodeValue()) printTree(tree.getRightChild()) # test tree def testTree(): myTree = BinaryTree("Maud") myTree.insertLeft("Bob") myTree.insertRight("Tony") myTree.insertRight("Steven") printTree(myTree)
阅读更多关于它在这里： – 这是一个非常简单的二叉树实现 。
这是一个很好的教程之间的问题
在Python中简单的实现BST
class TreeNode: def __init__(self, value): self.left = None; self.right = None; self.data = value; class Tree: def __init__(self): self.root = None; def addNode(self, node, value): if(node==None): self.root = TreeNode(value); else: if(value<node.data): if(node.left==None): node.left = TreeNode(value) else: self.addNode(node.left, value); else: if(node.right==None): node.right = TreeNode(value) else: self.addNode(node.right, value); def printInorder(self, node): if(node!=None): self.printInorder(node.left) print(node.data) self.printInorder(node.right) def main(): testTree = Tree() testTree.addNode(testTree.root, 200) testTree.addNode(testTree.root, 300) testTree.addNode(testTree.root, 100) testTree.addNode(testTree.root, 30) testTree.printInorder(testTree.root)
使用列表实现二叉树的一种非常快速的肮脏方法。 不是最有效的，也不是处理零值。 但这是非常透明的（至less对我来说）：
def _add(node, v): new = [v, [], []] if node: left, right = node[1:] if not left: left.extend(new) elif not right: right.extend(new) else: add(left, v) else: node.extend(new) def binary_tree(s): root = [] for e in s: _add(root, e) return root def traverse(n, order): if n: v = n[0] if order == 'pre': yield v for left in traverse(n[1], order): yield left if order == 'in': yield v for right in traverse(n[2], order): yield right if order == 'post': yield v
从一个可迭代的构造树：
>>> t = binary_tree('ABCD E'.split()) >>> print t ['A', ['B', ['D', [], []], ['E', [], []]], ['C', [], []]]
遍历树：
>>> list(traverse(t, 'pre')), list(traverse(t, 'in')), list(traverse(t, 'post')) (['A', 'B', 'D', 'E', 'C'], ['D', 'B', 'E', 'A', 'C'], ['D', 'E', 'B', 'C', 'A'])
你不需要有两个class级
class Tree: val = None left = None right = None def __init__(self, val): self.val = val def insert(self, val): if self.val is not None: if val < self.val: if self.left is not None: self.left.insert(val) else: self.left = Tree(val) elif val > self.val: if self.right is not None: self.right.insert(val) else: self.right = Tree(val) else: return else: self.val = val print("new node added") def showTree(self): if self.left is not None: self.left.showTree() print(self.val, end = ' ') if self.right is not None: self.right.showTree()
#!/usr/bin/python class BinaryTree: def __init__(self, left, right, data): self.left = left self.right = right self.data = data def pre_order_traversal(root): print(root.data, end=' ') if root.left != None: pre_order_traversal(root.left) if root.right != None: pre_order_traversal(root.right) def in_order_traversal(root): if root.left != None: in_order_traversal(root.left) print(root.data, end=' ') if root.right != None: in_order_traversal(root.right) def post_order_traversal(root): if root.left != None: post_order_traversal(root.left) if root.right != None: post_order_traversal(root.right) print(root.data, end=' ')
多一点“Pythonic”？
class Node: def __init__(self, value): self.value = value self.left = None self.right = None def __repr__(self): return str(self.value) class BST: def __init__(self): self.root = None def __repr__(self): self.sorted = [] self.get_inorder(self.root) return str(self.sorted) def get_inorder(self, node): if node: self.get_inorder(node.left) self.sorted.append(str(node.value)) self.get_inorder(node.right) def add(self, value): if not self.root: self.root = Node(value) else: self._add(self.root, value) def _add(self, node, value): if value <= node.value: if node.left: self._add(node.left, value) else: node.left = Node(value) else: if node.right: self._add(node.right, value) else: node.right = Node(value) from random import randint bst = BST() for i in range(100): bst.add(randint(1, 1000)) print (bst)
import random class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None self.p = None class BinaryTree: def __init__(self): self.root = None def length(self): return self.size def inorder(self, node): if node == None: return None else: self.inorder(node.left) print node.key, self.inorder(node.right) def search(self, k): node = self.root while node != None: if node.key == k: return node if node.key > k: node = node.left else: node = node.right return None def minimum(self, node): x = None while node.left != None: x = node.left node = node.left return x def maximum(self, node): x = None while node.right != None: x = node.right node = node.right return x def successor(self, node): parent = None if node.right != None: return self.minimum(node.right) parent = node.p while parent != None and node == parent.right: node = parent parent = parent.p return parent def predecessor(self, node): parent = None if node.left != None: return self.maximum(node.left) parent = node.p while parent != None and node == parent.left: node = parent parent = parent.p return parent def insert(self, k): t = TreeNode(k) parent = None node = self.root while node != None: parent = node if node.key > t.key: node = node.left else: node = node.right tp = parent if parent == None: self.root = t elif t.key < parent.key: parent.left = t else: parent.right = t return t def delete(self, node): if node.left == None: self.transplant(node, node.right) elif node.right == None: self.transplant(node, node.left) else: succ = self.minimum(node.right) if succ.p != node: self.transplant(succ, succ.right) succ.right = node.right succ.right.p = succ self.transplant(node, succ) succ.left = node.left succ.left.p = succ def transplant(self, node, newnode): if node.p == None: self.root = newnode elif node == node.p.left: node.p.left = newnode else: node.p.right = newnode if newnode != None: newnode.p = node.p
Python中的二叉树
class Tree(object): def __init__(self): self.data=None self.left=None self.right=None def insert(self, x, root): if root==None: t=node(x) t.data=x t.right=None t.left=None root=t return root elif x<root.data: root.left=self.insert(x, root.left) else: root.right=self.insert(x, root.right) return root def printTree(self, t): if t==None: return self.printTree(t.left) print t.data self.printTree(t.right) class node(object): def __init__(self, x): self.x=x bt=Tree() root=None n=int(raw_input()) a=[] for i in range(n): a.append(int(raw_input())) for i in range(n): root=bt.insert(a[i], root) bt.printTree(root)
