¿Cómo implementar un árbol binario?

Question

¿Cuál es la mejor estructura de datos que se puede usar para implementar Binary Tree en Python?

Answer 1

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

Lea más sobre esto aquí: -Este es un muy simple implementation de un árbol binario.

This es un buen tutorial con preguntas en el medio

Answer 2

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 
     t.p = 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 

Answer 3

Una forma muy rápida 'n sucia de la implementación de un árbol binario utilizando listas. No es el más eficiente, ni maneja valores nulos demasiado bien. pero es muy transparente (al menos para mí):

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 

La construcción de un árbol de un iterable:

>>> t = binary_tree('A B C D E'.split()) 
>>> print t 
['A', ['B', ['D', [], []], ['E', [], []]], ['C', [], []]] 

recorrer un árbol:

>>> 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']) 

Answer 4

Aquí es mi sencilla implementación recursiva del árbol binario.

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

Answer 5

usted no necesita tener dos clases

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

Answer 6

implementación sencilla de BST en 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) 

Answer 7

árbol binario en 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) 

Answer 8

Un poco más "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) 

Answer 9

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

Answer 10

Esta aplicación es compatible con inserto, encontrar y eliminar operaciones sin destruir la estructura del árbol. Este no es un árbol balanceado.

# Class for construct the nodes of the tree. (Subtrees) 
class Node: 
def __init__(self, key, parent_node = None): 
    self.left = None 
    self.right = None 
    self.key = key 
    if parent_node == None: 
     self.parent = self 
    else: 
     self.parent = parent_node 

# Class with the structure of the tree. 
# This Tree is not balanced. 
class Tree: 
def __init__(self): 
    self.root = None 

# Insert a single element 
def insert(self, x): 
    if(self.root == None): 
     self.root = Node(x) 
    else: 
     self._insert(x, self.root) 

def _insert(self, x, node): 
    if(x < node.key): 
     if(node.left == None): 
      node.left = Node(x, node) 
     else: 
      self._insert(x, node.left) 
    else: 
     if(node.right == None): 
      node.right = Node(x, node) 
     else: 
      self._insert(x, node.right) 

# Given a element, return a node in the tree with key x. 
def find(self, x): 
    if(self.root == None): 
     return None 
    else: 
     return self._find(x, self.root) 
def _find(self, x, node): 
    if(x == node.key): 
     return node 
    elif(x < node.key): 
     if(node.left == None): 
      return None 
     else: 
      return self._find(x, node.left) 
    elif(x > node.key): 
     if(node.right == None): 
      return None 
     else: 
      return self._find(x, node.right) 

# Given a node, return the node in the tree with the next largest element. 
def next(self, node): 
    if node.right != None: 
     return self._left_descendant(node.right) 
    else: 
     return self._right_ancestor(node) 

def _left_descendant(self, node): 
    if node.left == None: 
     return node 
    else: 
     return self._left_descendant(node.left) 

def _right_ancestor(self, node): 
    if node.key <= node.parent.key: 
     return node.parent 
    else: 
     return self._right_ancestor(node.parent) 

# Delete an element of the tree 
def delete(self, x): 
    node = self.find(x) 
    if node == None: 
     print(x, "isn't in the tree") 
    else: 
     if node.right == None: 
      if node.left == None: 
       if node.key < node.parent.key: 
        node.parent.left = None 
        del node # Clean garbage 
       else: 
        node.parent.right = None 
        del Node # Clean garbage 
      else: 
       node.key = node.left.key 
       node.left = None 
     else: 
      x = self.next(node) 
      node.key = x.key 
      x = None 


# tests 
t = Tree() 
t.insert(5) 
t.insert(8) 
t.insert(3) 
t.insert(4) 
t.insert(6) 
t.insert(2) 

t.delete(8) 
t.delete(5) 

t.insert(9) 
t.insert(1) 

t.delete(2) 
t.delete(100) 

# Remember: Find method return the node object. 
# To return a number use t.find(nº).key 
# But it will cause an error if the number is not in the tree. 
print(t.find(5)) 
print(t.find(8)) 
print(t.find(4)) 
print(t.find(6)) 
print(t.find(9))