|
 |
Run the file as is for some demo output.
ingo
---%<------%<------%<---
/*
POV-Ray include file: bst.inc
Author : Ingo Janssen
Date : 2024-03-16
Version: 0.5
A POV-Ray include file for a Binary Seach Tree (BST)
*/
#version 3.7;
#declare _Sentinel = -999999;
// Enums for BST struct
#declare _bstNodeVal = 0;
#declare _bstLeft = 1;
#declare _bstRight = 2;
#declare _bstSize = 3;
#macro BSTDebug(BST)
#for(I, 0, dimension_size(BST[_bstNodeVal], 1) - 1)
#debug concat("Value : ",str(BSTree[_bstNodeVal][I], 14, -1), ", ")
#debug concat("Left : ",str(BSTree[_bstLeft][I], 7, 0), ", ")
#debug concat("Right : ",str(BSTree[_bstRight][I], 7, 0), "\n")
#end
#debug"\n"
#end
#macro BSTInit(MaxNodes)
/*InitBST(MaxNodes)
Creates a "struct" for a Binar Search Tree.
Parameters:
MaxNodes (int): maximum nuber of nodes the tree can contain.
Result:
Returns an array of arrays
array{
array[MaxNodes]; // Value array
array[MaxNodes]; // Left pointer array
array[MaxNodes]; // Right pointer arra
array[1]; // BST size, is updated during inserts
};
*/
#local BST = array[4];
#local BST[_bstNodeVal] = array[MaxNodes]; // Value array
#local BST[_bstLeft] = array[MaxNodes]; // Left pointer array
#local BST[_bstRight] = array[MaxNodes]; // Right pointer array
#local BST[_bstSize] = array[1];
#local BST[_bstSize][0] = 0;
#for(I, 0, MaxNodes-1)
#local BST[_bstNodeVal][I] = _Sentinel;
#local BST[_bstLeft][I] = _Sentinel;
#local BST[_bstRight][I] = _Sentinel;
#end
BST
#end
#macro BSTInsert(BST, Value)
/*: BSTInsert(BST, Value)
Insert data in the BST.
*/
//#debug concat("\nBSTsize: ",str(BST[_bstSize][0],0,0), "\n\n")
#if(BST[_bstSize][0] < dimension_size(BST[_bstNodeVal], 1))
#local Node = 0;
#local NodeAdded = false;
#while(NodeAdded = false)
#if(BST[_bstNodeVal][Node] = _Sentinel)
// Found an empty node, insert the value here
#local BST[_bstNodeVal][Node] = Value;
#local BST[_bstSize][0] = BST[_bstSize][0] + 1;
#local NodeAdded = true;
#else
#if(Value < BST[_bstNodeVal][Node])
#if(BST[_bstLeft][Node] = _Sentinel)
// Found an empty left child, insert the value here
#local BST[_bstLeft][Node] = BST[_bstSize][0];
#local BST[_bstNodeVal][BST[_bstSize][0]] = Value;
#local BST[_bstSize][0] = BST[_bstSize][0] + 1;
#local NodeAdded = true;
#else
// Traverse the left subtree
#local Node = BST[_bstLeft][Node];
#end
#else
#if(Value > BST[_bstNodeVal][Node])
#if(BST[_bstRight][Node] = _Sentinel)
// Found an empty right child, insert the value here
#local BST[_bstRight][Node] = BST[_bstSize][0];
#local BST[_bstNodeVal][BST[_bstSize][0]] = Value;
#local BST[_bstSize][0] = BST[_bstSize][0] + 1;
#local NodeAdded = true;
#else
// Traverse the right subtree
#local Node = BST[_bstRight][Node];
#end
#else
// Value already exists in the tree, do nothing
#local NodeAdded = true;
#end
#end
#end
#end
#else
#error "Binary search tree is full"
#end
#end
#macro BSTSearch(BST, Value)
/*: BSTSearch(BST, Value)
Finds the index the given value is at.
Returns -1 if the value is not found in the BST.
*/
#local Node = 0;
#while(Node != _Sentinel)
#if(Value < BST[_bstNodeVal][Node])
#local Node = BST[_bstLeft][Node];
#else
#if(Value > BST[_bstNodeVal][Node])
#local Node = BST[_bstRight][Node];
#else
// Value found in the tree
#break
#end
#end
#end
Node
#end
#macro BSTMinVal(BST, Node)
/*: BSTMinVal(BST, Node)
Returns the minimum value in the tree, starting from Node.
*/
#while(BST[_bstLeft][Node] != _Sentinel)
#local Node = BST[_bstLeft][Node];
#end
BST[_bstNodeVal][Node]
#end
#macro BSTMinIdx(BST, Node)
/*: BSTMinIdx(BST, Node)
Returns the index of the minimum value in the tree, starting from Node.
*/
#while(BST[_bstLeft][Node] != _Sentinel)
#local Node = BST[_bstLeft][Node];
#end
Node
#end
#macro BSTiot(BST, Node)
/*: BSTiot(BST, Node)
BST In Order Traversal : Left - Root - Right pattern traversal of the tree,
starting from Node
Returns an array with values.
*/
#macro _BSTIOTraverse(BST, Node, Traversed, I)
#if(Node != _Sentinel)
// Visit the left subtree
_BSTIOTraverse(BST, BST[_bstLeft][Node], Traversed, I)
// Visit the current node
//#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
#local Traversed[I] = BST[_bstNodeVal][Node];
#local I = I + 1;
// Visit the right subtree
_BSTIOTraverse(BST, BST[_bstRight][Node], Traversed, I)
#end
#end
#local I = 0;
#local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
_BSTIOTraverse(BST, Node, Traversed, I)
Traversed
#end
#macro BSTpre(BST, Node)
/*: BSTpre(BST, Node)
BST Pre Order Traversal: Root - Left - Right pattern traversal of the tree,
starting from Node
Returns an array with values.
*/
#macro _BSTpreTraverse(BST, Node, Traversed, I)
#if(Node != _Sentinel)
//#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
#local Traversed[I] = BST[_bstNodeVal][Node];
#local I = I + 1;
_BSTpreTraverse(BST, BST[_bstLeft][Node] , Traversed, I)
_BSTpreTraverse(BST, BST[_bstRight][Node], Traversed, I)
#end
#end
#local I = 0;
#local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
_BSTpreTraverse(BST, Node, Traversed, I)
Traversed
#end
#macro BSTpro(BST, Node)
/*: BSTpost(BST, Node)
BST Post Order Traversal: Left - Right - Root patern traversal of the tree,
starting from Node.
Returns an array with values.
*/
#macro _BSTpostTraverse(BST, Node, Traversed, I)
#if(Node != _Sentinel)
_BSTpostTraverse(BST, BST[_bstLeft][Node] , Traversed, I)
_BSTpostTraverse(BST, BST[_bstRight][Node], Traversed, I)
//#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
#end
#end
#local I = 0;
#local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
_BSTpostTraverse(BST, Node, Traversed, I)
Traversed
#end
#macro BSTDelete(BST, Value)
/*: BSTDelete(BST, Value)
Deletes the given value from the BST.
*/
#local Root = 0;
#local NodeToDelete = BSTSearch(BST, Value);
#if (NodeToDelete != _Sentinel)
// Node found, proceed with deletion
#local ParentOfNodeToDelete = _Sentinel;
// Find the parent of the node to be deleted
#while (Root != NodeToDelete)
#if (Value < BST[_bstNodeVal][Root])
#local ParentOfNodeToDelete = Root;
#local Root = BST[_bstLeft][Root];
#else
#local ParentOfNodeToDelete = Root;
#local Root = BST[_bstRight][Root];
#end
#end
// Handle the case of a leaf node
#if (BST[_bstLeft][NodeToDelete] = _Sentinel & BST[_bstRight][NodeToDelete]
= _Sentinel)
#if (ParentOfNodeToDelete = _Sentinel)
// Node to be deleted is the root node
#local BST[_bstNodeVal][0] = _Sentinel;
#local BST[_bstLeft][0] = _Sentinel;
#local BST[_bstRight][0] = _Sentinel;
#else
#if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
#local BST[_bstLeft][ParentOfNodeToDelete] = _Sentinel;
#else
#local BST[_bstRight][ParentOfNodeToDelete] = _Sentinel;
#end
#end
#end
// Handle the case of a node with one child
#if (BST[_bstLeft][NodeToDelete] != _Sentinel & BST[_bstRight][NodeToDelete]
= _Sentinel)
#if (ParentOfNodeToDelete = _Sentinel)
// Node to be deleted is the root node
#local BST[_bstNodeVal][0] =
BST[_bstNodeVal][BST[_bstLeft][NodeToDelete]];
#local BST[_bstLeft][0] = BST[_bstLeft][BST[_bstLeft][NodeToDelete]];
#local BST[_bstRight][0] = BST[_bstRight][BST[_bstLeft][NodeToDelete]];
#else
#if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
#local BST[_bstLeft][ParentOfNodeToDelete] =
BST[_bstLeft][NodeToDelete];
#else
#local BST[_bstRight][ParentOfNodeToDelete] =
BST[_bstLeft][NodeToDelete];
#end
#end
#elseif (BST[_bstLeft][NodeToDelete] = _Sentinel &
BST[_bstRight][NodeToDelete] != _Sentinel)
#if (ParentOfNodeToDelete = _Sentinel)
// Node to be deleted is the root node
#local BST[_bstNodeVal][0] =
BST[_bstNodeVal][BST[_bstRight][NodeToDelete]];
#local BST[_bstLeft][0] = BST[_bstLeft][BST[_bstRight][NodeToDelete]];
#local BST[_bstRight][0] = BST[_bstRight][BST[_bstRight][NodeToDelete]];
#else
#if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
#local BST[_bstLeft][ParentOfNodeToDelete] =
BST[_bstRight][NodeToDelete];
#else
#local BST[_bstRight][ParentOfNodeToDelete] =
BST[_bstRight][NodeToDelete];
#end
#end
#end
// Handle the case of a node with two children
#if (BST[_bstLeft][NodeToDelete] != _Sentinel & BST[_bstRight][NodeToDelete]
!= _Sentinel)
// Find the in-order successor (smallest value in the right subtree)
#local InOrderSuccessor = BSTMinIdx(BST, BST[_bstRight][NodeToDelete]);
// Copy the value of the in-order successor to the node to be deleted
#local BST[_bstNodeVal][NodeToDelete] =
BST[_bstNodeVal][InOrderSuccessor];
// Delete the in-order successor node
BSTDelete(BST, BST[_bstNodeVal][InOrderSuccessor]);
#end
// Decrement the size of the BST
#local BST[_bstSize][0] = BST[_bstSize][0] - 1;
#else
// Node not found, do nothing
#end
#end
//=====
#if(input_file_name="bst.inc")
#declare MAX_NODES = 15; // Maximum number of nodes in the tree
// for demo sake a bigger array then used is defined
#declare BSTree = BSTInit(MAX_NODES);
#declare ValArr = array[13]{3.33,432,90,pi,6,8,-1,34,9,0,13,12,23};
#for(I, 0, dimension_size(ValArr,1) - 1)
BSTInsert(BSTree, ValArr[I])
#debug concat("I : ", str(I, 1, 1), "\n")
BSTDebug(BSTree)
#end
#debug "\n"
#declare SearchVal = 90;
#declare IsNode = BSTSearch(BSTree, SearchVal);
#debug concat("Searched value ",str(SearchVal,7,-1) ," is at index ",
str(IsNode, 0, 0),"\n\n")
#debug concat("The MinVal is ", str(BSTMinVal(BSTree, 5),7,-1)," and is at index
", str(BSTMinIdx(BSTree, 5),0,0),"\n\n")
#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
#if(defined(InOrderVals[I])) // because one can define a bigger array than is
actually used.
#debug concat(str(InOrderVals[I],7,-1), ", ")
#end
#end
#debug "\n\n"
#declare PreOrderVals = BSTpre(BSTree, 0);
#debug "BSTpre : "
#for(I, 0, dimension_size(PreOrderVals,1) - 1)
#if(defined(PreOrderVals[I]))
#debug concat(str(PreOrderVals[I],7,-1), ", ")
#end
#end
#debug "\n\n"
#declare PostOrderVals = BSTpre(BSTree, 0);
#debug "BSTpost: "
#for(I, 0, dimension_size(PostOrderVals,1) - 1)
#if(defined(PostOrderVals[I]))
#debug concat(str(PostOrderVals[I],7,-1), ", ")
#end
#end
#debug "\n\n"
BSTDelete(BSTree, 12)
#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
#if(defined(InOrderVals[I])) // because one can define a bigger array than is
actually used.
#debug concat(str(InOrderVals[I],7,-1), ", ")
#end
#end
#debug "\n\n"
BSTDebug(BSTree)
#debug "\n"
#end // if inc..
---%<------%<------%<---
Post a reply to this message
|
|
