如何实现二叉树？

Question

哪种数据结构可用于在Python中实现二叉树？

Answer 1

这是二进制搜索树的简单递归实现。#!/usr/bin/pythonclass Node:&nbsp; &nbsp; def __init__(self, val):&nbsp; &nbsp; &nbsp; &nbsp; self.l = None&nbsp; &nbsp; &nbsp; &nbsp; self.r = None&nbsp; &nbsp; &nbsp; &nbsp; self.v = valclass Tree:&nbsp; &nbsp; def __init__(self):&nbsp; &nbsp; &nbsp; &nbsp; self.root = None&nbsp; &nbsp; def getRoot(self):&nbsp; &nbsp; &nbsp; &nbsp; return self.root&nbsp; &nbsp; def add(self, val):&nbsp; &nbsp; &nbsp; &nbsp; if(self.root == None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.root = Node(val)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._add(val, self.root)&nbsp; &nbsp; def _add(self, val, node):&nbsp; &nbsp; &nbsp; &nbsp; if(val < node.v):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.l != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._add(val, node.l)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.l = Node(val)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.r != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._add(val, node.r)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.r = Node(val)&nbsp; &nbsp; def find(self, val):&nbsp; &nbsp; &nbsp; &nbsp; if(self.root != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return self._find(val, self.root)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return None&nbsp; &nbsp; def _find(self, val, node):&nbsp; &nbsp; &nbsp; &nbsp; if(val == node.v):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node&nbsp; &nbsp; &nbsp; &nbsp; elif(val < node.v and node.l != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._find(val, node.l)&nbsp; &nbsp; &nbsp; &nbsp; elif(val > node.v and node.r != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._find(val, node.r)&nbsp; &nbsp; def deleteTree(self):&nbsp; &nbsp; &nbsp; &nbsp; # garbage collector will do this for us.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; self.root = None&nbsp; &nbsp; def printTree(self):&nbsp; &nbsp; &nbsp; &nbsp; if(self.root != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._printTree(self.root)&nbsp; &nbsp; def _printTree(self, node):&nbsp; &nbsp; &nbsp; &nbsp; if(node != None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._printTree(node.l)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print str(node.v) + ' '&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self._printTree(node.r)#&nbsp; &nbsp; &nbsp;3# 0&nbsp; &nbsp; &nbsp;4#&nbsp; &nbsp;2&nbsp; &nbsp; &nbsp; 8tree = Tree()tree.add(3)tree.add(4)tree.add(0)tree.add(8)tree.add(2)tree.printTree()print (tree.find(3)).vprint tree.find(10)tree.deleteTree()tree.printTree()

Answer 2

# simple binary tree# in this implementation, a node is inserted between an existing node and the rootclass BinaryTree():&nbsp; &nbsp; def __init__(self,rootid):&nbsp; &nbsp; &nbsp; self.left = None&nbsp; &nbsp; &nbsp; self.right = None&nbsp; &nbsp; &nbsp; self.rootid = rootid&nbsp; &nbsp; def getLeftChild(self):&nbsp; &nbsp; &nbsp; &nbsp; return self.left&nbsp; &nbsp; def getRightChild(self):&nbsp; &nbsp; &nbsp; &nbsp; return self.right&nbsp; &nbsp; def setNodeValue(self,value):&nbsp; &nbsp; &nbsp; &nbsp; self.rootid = value&nbsp; &nbsp; def getNodeValue(self):&nbsp; &nbsp; &nbsp; &nbsp; return self.rootid&nbsp; &nbsp; def insertRight(self,newNode):&nbsp; &nbsp; &nbsp; &nbsp; if self.right == None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.right = BinaryTree(newNode)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree = BinaryTree(newNode)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree.right = self.right&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.right = tree&nbsp; &nbsp; def insertLeft(self,newNode):&nbsp; &nbsp; &nbsp; &nbsp; if self.left == None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.left = BinaryTree(newNode)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree = BinaryTree(newNode)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree.left = self.left&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.left = treedef printTree(tree):&nbsp; &nbsp; &nbsp; &nbsp; if tree != None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printTree(tree.getLeftChild())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print(tree.getNodeValue())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printTree(tree.getRightChild())# test treedef testTree():&nbsp; &nbsp; myTree = BinaryTree("Maud")&nbsp; &nbsp; myTree.insertLeft("Bob")&nbsp; &nbsp; myTree.insertRight("Tony")&nbsp; &nbsp; myTree.insertRight("Steven")&nbsp; &nbsp; printTree(myTree)在此处了解更多信息：-这是二进制树的非常简单的实现。

Answer 3

BST在Python中的简单实现class TreeNode:&nbsp; &nbsp; def __init__(self, value):&nbsp; &nbsp; &nbsp; &nbsp; self.left = None&nbsp; &nbsp; &nbsp; &nbsp; self.right = None&nbsp; &nbsp; &nbsp; &nbsp; self.data = valueclass Tree:&nbsp; &nbsp; def __init__(self):&nbsp; &nbsp; &nbsp; &nbsp; self.root = None&nbsp; &nbsp; def addNode(self, node, value):&nbsp; &nbsp; &nbsp; &nbsp; if(node==None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.root = TreeNode(value)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(value<node.data):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.left==None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.left = TreeNode(value)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.addNode(node.left, value)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.right==None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.right = TreeNode(value)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.addNode(node.right, value)&nbsp; &nbsp; def printInorder(self, node):&nbsp; &nbsp; &nbsp; &nbsp; if(node!=None):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.printInorder(node.left)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print(node.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; self.printInorder(node.right)def main():&nbsp; &nbsp; testTree = Tree()&nbsp; &nbsp; testTree.addNode(testTree.root, 200)&nbsp; &nbsp; testTree.addNode(testTree.root, 300)&nbsp; &nbsp; testTree.addNode(testTree.root, 100)&nbsp; &nbsp; testTree.addNode(testTree.root, 30)&nbsp; &nbsp; testTree.printInorder(testTree.root)