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