Как реализовать двоичное дерево?

Какая лучшая структура данных может использоваться для реализации двоичного дерева в Python?

8 Solutions collect form web for “Как реализовать двоичное дерево?”

Вот моя простая рекурсивная реализация двоичного дерева.

#!/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) 

Подробнее об этом здесь: -Это очень простая реализация двоичного дерева.

Это хороший учебник с вопросами между

Простая реализация BST в Python

 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) 

Очень быстрый «грязный способ реализации двоичного дерева с использованием списков. Не самый эффективный и не слишком хорошо справляется с нулевыми значениями. Но это очень прозрачно (по крайней мере для меня):

 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 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() 

Чуть больше «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) 
Python - лучший язык программирования в мире.