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
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);
}
}
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, 07: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
}