Vollständige Version anzeigen : [Python] BinaryTree (binärer Suchbaum)


cable
10.02.2010, 16:06

Hoi!

Hatte heute ein wenig Langeweile und hab mal einen Binärbaum in Python zusammengeschrieben. Die Grundfunktionalitäten sind implementiert, d;h;: Werte einfügen, Werte löschen, InOrder Traversierung, kleinster Wert finden, größter Wert finden.
Geschrieben mit Python 3;1;1, sollte aber auch mit 2;5/6 laufen.
Wenn ein Element schon vorhanden sein sollte, dann wird es NICHT eingefügt, sondern ignoriert.

Ich habe die Funktionalitäten rudimentär getestet. Wenn ihr Fehler findet, dann gebt mir Bescheid!

Beispielcode:
import random

bTree = BinaryTree(6) #initialisiert den Baum mit der Zahl 6
for i in range(100):
bTree;insert(random;randint(1, 9999) #fuellt den Baum mit Zufallszahlen (1-9999)

for i in bTree;inOrder():
print(i) #gibt den Baum in aufsteigender Reihenfolge aus

b = bTree;find(5) #sucht den Knoten mit der Value 5
if b:
bTree;remove(b) #wenn b vorhanden ist, dann entferne den Knoten

del bTree #gibt alle Knoten frei und loescht den Baum


Classes:

class BinaryNode:
def __init__(self, value, parent=None):
self;__value = value
self;__left = None
self;__right = None
self;__parent = parent

def __del__(self):
del self;__left
del self;__right
del self;__parent
del self;__value

def getValue(self):
return self;__value

def setValue(self, value):
self;__value = value

def getLeft(self):
return self;__left

def setLeft(self, left):
self;__left = left

def getRight(self):
return self;__right

def setRight(self, right):
self;__right = right

def getParent(self):
return self;__parent

def setParent(self, parent):
self;__parent = parent

Value = property(getValue, setValue)
Left = property(getLeft, setLeft)
Right = property(getRight, setRight)
Parent = property(getParent, setParent)


class BinaryTree:
def __init__(self, rootval):
self;__root = BinaryNode(rootval)

def __del__(self):
while self;__root;Right or self;__root;Left:
if self;__root;Left:
self;remove(self;__root;Left)
else:
self;remove(self;__root;Right)
del self;__root

def insert(self, value):
if self;Empty:
self;__root;Value = value
else:
self;__insertRecur(value, self;__root)

def __insertRecur(self, value, start):
if value < start;Value:
if not start;Left:
start;Left = BinaryNode(value, start)
else:
self;__insertRecur(value, start;Left)
elif value > start;Value:
if not start;Right:
start;Right = BinaryNode(value, start)
else:
self;__insertRecur(value, start;Right)

def getRoot(self):
return self;__root

Root = property(getRoot)

def isEmpty(self):
if self;__root;Value:
return False
else:
return True

Empty = property(isEmpty)

def inOrder(self):
inorder = []
self;__inOrderRecur(self;__root, inorder)
return inorder

def __inOrderRecur(self, start, elems):
if start;Left:
self;__inOrderRecur(start;Left, elems)

elems;append(start;Value)

if start;Right:
self;__inOrderRecur(start;Right, elems)

def findMin(self):
return self;__findMinBelow(self;__root)

def __findMinBelow(self, start):
tmp = start
while tmp;Left:
tmp = tmp;Left
return tmp

def findMax(self):
return self;__findMaxBelow(self;__root)

def __findMaxBelow(self, start):
tmp = start
while tmp;Right:
tmp = tmp;Right
return tmp

def find(self, value):
return self;__findIter(self;__root, value)

def __findIter(self, start, value):
tmp = start
while True:
if value == tmp;Value:
return tmp
elif value < tmp;Value:
if tmp;Left:
tmp = tmp;Left
else:
return None
else:
if tmp;Right:
tmp = tmp;Right
else:
return None

def remove(self, node):
if node;Left == None and node;Right == None:
self;__removeLeaf(node)
elif node;Left == None or node;Right == None:
self;__removeSingle(node)
else:
minRight = self;__findMinBelow(node;Right)
node;Value = minRight;Value
self;remove(minRight)

def __removeLeaf(self, node):
if node is self;__root:
self;__root;Value = None
else:
if node;Parent;Right is node:
node;Parent;Right = None
else:
node;Parent;Left = None
del node

def __removeSingle(self, node):
child = None
if node;Left:
child = node;Left
else:
child = node;Right

if node is self;__root:
self;__root = child
child;Parent = None
del node
else:
parent = node;Parent
if node is parent;Left:
parent;Left = child
else:
parent;Right = child
child;Parent = parent
del node


greez


Murdoc
10.02.2010, 17:31

mir war ein wenig langweilig auf der arbeit, deshalb hab ich den code mal zu php5;3 portiert :D

<?php
$tree = new xbinary::Tree(6); // "::" mit "\" ersetzen

for($i = 0; $i < 100; ++$i)
$tree->insert(rand(1, 9999));

foreach($tree->inOrder() as $value)
print $value . "<br />\n";

$node = $tree->find(5);
if(null !== $node)
$tree->remove($node);

unset($tree);


<?php
/**
*
* ;author murdoc
* ;see <Link>
*/
namespace xbinary;

// node
class Node
{
public $value,
$left = null,
$right = null,
$parentNode; //"parent" is reserved

/**
* constructor
*
* ;param int value
* ;param Node|null parent
*/
public function __construct($value, Node &$parent = null)
{
$this->value = $value;
$this->parentNode = $parent;
}

/**
* destructor
*/
public function __destruct()
{
if($this->right)
unset($this->right);
}
}

//tree
class Tree
{
private $_root;

/**
* constructor
*
* ;param int $rootval
*/
public function __construct($rootval)
{
$this->_root = new Node($rootval);
}

/**
* destructor
*/
public function __destruct()
{}

/**
* insert a value
*
* ;param int $value
* ;void
*/
public function insert($value)
{
$this->insertRecur($value, $this->_root);
}

/**
*
* ;param int $value
* ;param Node $start
* ;void
*/
protected function insertRecur($value, Node &$start)
{
if($value < $start->value) {
if(null === $start->left)
$start->left = new Node($value, $start);
else
$this->insertRecur($value, $start->left);
} elseif($value > $start->value) {
if(null === $start->right)
$start->right = new Node($value, $start);
else
$this->insertRecur($value, $start->right);
}
}

/**
*
* ;return array
*/
public function inOrder()
{
$stack = array();
$this->inOrderRecur($this->_root, $stack);
return $stack;
}

/**
*
* ;param Node $start
* ;param array $stack
* ;void
*/
protected function inOrderRecur(Node &$start, array &$stack)
{
if(null !== $start->left)
$this->inOrderRecur($start->left, $stack);

$stack[] = $start->value;

if(null !== $start->right)
$this->inOrderRecur($start->right, $stack);
}

/**
*
* ;param boolean $int
* ;return Node|int
*/
public function findMin($int = false)
{
$tmp = $this->findMinBelow($this->_root);
return $int ? $tmp->value : $tmp;
}

/**
*
* ;param Node $node
* ;return Node
*/
protected function findMinBelow(Node $node)
{
while(null !== $node->left)
$node = $node->left;

return $node;
}

/**
*
* ;param boolean $int
* ;return Node|int
*/
public function findMax($int = false)
{
$tmp = $this->findMaxBelow($this->_root);
return $int ? $tmp->value : $tmp;
}

/**
*
* ;param Node $node
* ;return Node
*/
protected function findMaxBelow(Node $node)
{
while(null !== $node->right)
$node = $node->right;

return $node;
}

/**
*
* ;param int $value
* ;param int $limit
* ;return Node|int
*/
public function find($value, $limit = 0)
{
if(!is_int($limit) || $limit === 0)
$limit = PHP_MAX_INT;

$tmp = $this->_root;
$itr = 0;

do {
if($value == $tmp->value)
return $int ? $tmp->value : $tmp;

if($value < $tmp->value) {
if(null === $tmp->left)
return null;

$tmp = $tmp->left;
continue;
} else {
if(null === $tmp->right)
return null;

$tmp = $tmp->right;
continue;
}
} while(++$itr < $limit);
}

/**
*
* ;param Node $node
* ;void
*/
public function remove(Node &$node)
{
if(null === $node->left && null === $node->right)
$this->removeLeaf($node);
elseif(null === $node->left || null === $node->right)
$this->removeSingle($node);
else {
$minRight = $this->findMinBelow($node->right);
$node->value = $minRight->value;
$this->remove($minRight);
}
}

/**
*
* ;param Node $node
* ;void
*/
protected function removeLeaf(Node &$node)
{
if(null !== $node->parentNode->right)
$node->parentNode->right = null;
else
$node->parentNode->left = null;

unset($node);
}

/**
*
* ;param Node $node
* ;void
*/
protected function removeSingle(Node &$node)
{
if(null !== $node->right) {
if($node === $this->_root) {
$node->right->parentNode = null;
$this->_root = $node->right;
} else {
$node->right->parentNode = $node->parentNode;
$node->parentNode->right = $node->right;
}
} else {
if($node === $this->_root) {
$node->left->parentNode = null;
$this->_root = $node->right;
} else {
$node->left->parentNode = $node->parentNode;
$node->parentNode->left = $node->left;
}
}

unset($node);
}
}


cable
05.03.2010, 15:27

Ähnliche Themen: [Python] BinaryTree (binärer Suchbaum) Hoi! Hatte heute ein wenig Langeweile und hab mal einen Binärbaum in Python zusammengeschrieben. Die Grundfunktionalitäten sind implemen[...]
Binärer Code: Zahl 666 Mich interessiert grade mal, welchen binären Code die Zahl 666 hat. Ich hoffe, ich habs ins richtige Forum gestellt, ansonsten bitte versch[...]
[Python] BinaryTree (binärer Suchbaum)
Hab mal 2 kleine Fehler behoben. Hatte wohl am Ende nicht mehr so viel Lust und dann ein Logikfehler drin :/

Nun sollte alles richtig funktionieren ;)

greez


Ragnaroek
28.12.2010, 08:42

Hier noch eine C#~NET Konsolenanwendungs-Variante:

Main Program

using System;
using BinaryTreeLib;

namespace TreeTest
{
// class TreeTest definition
public class TreeTest
{
// test class Tree
static void Main( string[] args )
{
Tree tree = new Tree();
int insertValue;
int deleteValue = 0;

Console;WriteLine("Delete nothing:");
tree;DeleteNode(1);

Console;WriteLine( "Inserting values: " );
Random random = new Random();

// insert 10 random integers from 0-99 in tree
for ( int i = 1; i <= 10; i++ )
{
insertValue = random;Next( 100 );
Console;Write( insertValue + " " );

tree;InsertNode( insertValue );
}
// perform preorder traversal of tree
Console;WriteLine( "\n\nPreorder traversal" );
tree;PreorderTraversal();

// perform inorder traversal of tree
Console;WriteLine( "\n\nInorder traversal" );
tree;InorderTraversal();

// perform postorder traversal of tree
Console;WriteLine( "\n\nPostorder traversal" );
tree;PostorderTraversal();

while (true)
{
Console;Write("\n\nEnter a Value to delete (Stop with -1): ");
deleteValue = Convert;ToInt32(Console;ReadLine());

if (deleteValue == -1)
break;

tree;DeleteNode(deleteValue);

// perform preorder traversal of tree
Console;WriteLine("\n\nPreorder traversal");
tree;PreorderTraversal();

// perform inorder traversal of tree
Console;WriteLine("\n\nInorder traversal");
tree;InorderTraversal();

// perform postorder traversal of tree
Console;WriteLine("\n\nPostorder traversal");
tree;PostorderTraversal();
Console;WriteLine();
}

Console;Read();
}

} // end class TreeTest
}


Class BinaryTreeLib

using System;
using System;Collections;Generic;
using System;Linq;
using System;Text;

namespace BinaryTreeLib
{
// class TreeNode definition
class TreeNode
{
private TreeNode leftNode;
private int data;
private TreeNode rightNode;

// initialize data and make this a leaf node
public TreeNode( int nodeData )
{
data = nodeData;
leftNode = rightNode = null; // node has no children
}

// LeftNode property
public TreeNode LeftNode
{
get
{
return leftNode;
}

set
{
leftNode = value;
}
}

// Data property
public int Data
{
get
{
return data;
}

set
{
data = value;
}
}

// RightNode property
public TreeNode RightNode
{
get
{
return rightNode;
}

set
{
rightNode = value;
}
}


// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public void Insert( int insertValue )
{
// insert in left subtree
if ( insertValue < data )
{
// insert new TreeNode
if ( leftNode == null )
leftNode = new TreeNode( insertValue );

// continue traversing left subtree
else
leftNode;Insert( insertValue );
}

// insert in right subtree
else if ( insertValue > data )
{
// insert new TreeNode
if ( rightNode == null )
rightNode = new TreeNode( insertValue );

// continue traversing right subtree
else
rightNode;Insert( insertValue );
}

} // end method Insert


// delete TreeNode from Tree that contains nodes;
public void Delete(int deleteValue)
{
if (deleteValue < Data) //Value in left Side of Tree
{
if (LeftNode;Data == deleteValue)
{
if (LeftNode;IsLeaf())
{
LeftNode = null; //delete
Console;WriteLine("Value found and deleted (was a Leaf on the left Side);");
}
else if (LeftNode;HasAChild())
{
if (LeftNode;LeftNode == null) //Replace with its Child != null
LeftNode = LeftNode;RightNode;
else
LeftNode = LeftNode;LeftNode;

Console;WriteLine("Value found and replaced with its next (found on the left Side);");
}
else
{
TreeNode tmp = LeftNode;RightNode;GetMinNode();//Get smallest Node of the right Side
tmp;LeftNode = LeftNode;LeftNode;
tmp;RightNode = LeftNode;RightNode;
LeftNode = tmp; //Replace searched Value with the smallest Node of the right Side
Console;WriteLine("Value replaced with smallest Node (Value found on left Side);");
}
}
else
{
Console;WriteLine("Searching for Value on the left Side..;");
LeftNode;Delete(deleteValue);
}
}
else if (deleteValue > Data) //Value in right Side of Tree
{
if (RightNode;Data == deleteValue)
{
if (RightNode;IsLeaf())
{
RightNode = null; //delete
Console;WriteLine("Value found and deleted (was a Leaf on the right Side);");
}
else if (RightNode;HasAChild())
{
if (RightNode;LeftNode == null) //Replace with its Child != null
RightNode = RightNode;RightNode;
else
RightNode = RightNode;LeftNode;

Console;WriteLine("Value found and replaced with its next (found on the right Side);");
}
else
{
TreeNode tmp = RightNode;RightNode;GetMinNode(); //Get smallest Node of the right Side
tmp;LeftNode = RightNode;LeftNode;
tmp;RightNode = RightNode;RightNode;
RightNode = tmp; //Replace searched Value with the smallest Node of the right Side
Console;WriteLine("Value replaced with smallest Node (Value found on right Side);");
}
}
else
{
Console;WriteLine("Searching for Value on the right Side..;");
RightNode;Delete(deleteValue);
}
}
else
Console;WriteLine("The searched Value is the root Value - it's not deletable");
} // end method DeleteNode

//Helper Methods
private bool IsLeaf()
{
if (this;LeftNode == null && this;RightNode == null)
return true;
else
return false;
}

private bool HasAChild()
{
if ((this;LeftNode != null && this;RightNode == null) || (this;LeftNode == null && this;RightNode != null))
return true;
else
return false;
}

private TreeNode GetMinNode()
{
if (LeftNode;LeftNode != null && LeftNode != null)
return LeftNode;GetMinNode();
else
{
int value = LeftNode;Data;
LeftNode = LeftNode;RightNode;

return new TreeNode (value);
}
}
} // end class TreeNode

// class Tree definition
public class Tree
{
private TreeNode root;

// construct an empty Tree of integers
public Tree()
{
root = null;
}

// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public void InsertNode( int insertValue )
{
lock ( this )
{
if ( root == null )
root = new TreeNode( insertValue );

else
root;Insert( insertValue );
}
}

public void DeleteNode(int deleteValue)
{
lock (this)
{
if (root == null)
Console;WriteLine("Baum leer - kann nicht gelöscht werden;\n");
else
root;Delete(deleteValue);
}
}

// begin preorder traversal
public void PreorderTraversal()
{
lock ( this )
{
PreorderHelper( root );
}
}

// recursive method to perform preorder traversal
private void PreorderHelper( TreeNode node )
{
if ( node == null )
return;

// output node data
Console;Write( node;Data + " " );

// traverse left subtree
PreorderHelper( node;LeftNode );

// traverse right subtree
PreorderHelper( node;RightNode );
}

// begin inorder traversal
public void InorderTraversal()
{
lock ( this )
{
InorderHelper( root );
}
}

// recursive method to perform inorder traversal
private void InorderHelper( TreeNode node )
{
if ( node == null )
return;

// traverse left subtree
InorderHelper( node;LeftNode );

// output node data
Console;Write( node;Data + " " );

// traverse right subtree
InorderHelper( node;RightNode );
}

// begin postorder traversal
public void PostorderTraversal()
{
lock ( this )
{
PostorderHelper( root );
}
}

// recursive method to perform postorder traversal
private void PostorderHelper( TreeNode node )
{
if ( node == null )
return;

// traverse left subtree
PostorderHelper( node;LeftNode );

// traverse right subtree
PostorderHelper( node;RightNode );

// output node data
Console;Write( node;Data + " " );
}

} // end class Tree
}




raid-rush.ws | Imprint & Contact pr