Binary Trees

Raziel078

So I'm pretty sure I wrote my funtion for printing all the elements between two points. But I can't figure out how to actually implement a tree. Could someone show me some sample code? also heres my function. Very simple but I think it will get the job done.


// Return range of two given points of tree rooted at t.
template <class Object>
int BinaryNode<Object>::hilo( BinaryNode<Object> A, BinaryNode<Object> B )
{
if( A == NULL || B == NULL )
return 0;
else
{
// cout << "The elements between" << A << "and" << B << "are /n";
do
{
cout << A << "/n";
A++;
} while(A <= ;
}
}

Doc

Man what. Unless you have the ++ operator overloaded to do some pretty tricky stuff, I can't imagine how that would work.

jclast

It's coded in Python, but you should be able to understand it and implement something similar in C++.

http://www.cason-family.com/justin/binary_search_tree.py

Raziel078

see thats why I need to see some implementation. The other functions were treating the indiviual nodes as integers. So I was hoping that it would be enough to iterate through from point A to point B.

Raziel078

If it helps here is my assignment word for word

Write a binary search tree method that takes two keys, low and high, and prints all elements X that are in the range specified by low and High. your program should run in O(k + logN) where K is the number of keys printed. Thus if K is small you should be examining only a small part of the tree. Use a recursive method and do not use an inorder iterator.

racyrefinedraj

I think what you are not reading the assignment carefully enough.

You are attempting to move from one key to the next key using

A++;

Which would only work if A was some sort of iterator.

Problem is, the assignment says

Use a recursive method and do not use an inorder iterator.

So no dice. Note also that your method is not recursive.

I'm going to write out in really vague pseudocode what I think the assignment is asking you to do

-Find key A by traversing the tree (should take O(log N) assuming the tree is balanced)
-Traverse through the tree , visiting every key that is between A and B HINT:What is the defining characteristic of a Binary Search Tree? This should take K steps where K is the number of nodes visited. This is the recursive part.
-When you get to B, stop.

As far as actually getting a binary tree implementation, I would recommend the STL unless your class/text provided you with some other data structures library.

localh77

If you haven't already done this, I would first try writing a function to print out the entire binary tree, in order. Basically, it'll be a recursive function that does the following:

1. print the node to the left (less than) the current node
2. print the current node
3. print the node to the right (greater than) the current node

Then just call this function with the root of the tree and see what happens. Once you have that working, writing a function to print just the subset of the tree between A and B will be easier.

Zek

First of all, have you overloaded the ++ and <= operators for your BinaryNode class? Otherwise you can't just use them for any old class, it won't compile. If the BinaryNode class has been defined for you then you need to show us that too.

Raziel078

oh, that would probably help, this will be long
So thats the code provided.

#include <stdio.h>

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include <cstdlib>
#include <iostream>
#include <stdlib.h>

template <class Object>
class BinaryTree;

// BinaryNode class; stores a node in a tree.
//
// CONSTRUCTION: with (a) no parameters, or (b) an Object,
// or (c) an Object, left pointer, and right pointer.
//
// *******************PUBLIC OPERATIONS**********************
// int size( ) --> Return size of subtree at node
// int height( ) --> Return height of subtree at node
// void printPostOrder( ) --> Print a postorder tree traversal
// void printInOrder( ) --> Print an inorder tree traversal
// void printPreOrder( ) --> Print a preorder tree traversal
// BinaryNode * duplicate( ) --> Return a duplicate tree
// *******************ERRORS*********************************
// None.

template <class Object>
class BinaryNode
{
public:
BinaryNode( const Object & theElement = Object( ),
BinaryNode *lt = NULL, BinaryNode *rt = NULL );

static int size( BinaryNode *t );
static int height( BinaryNode *t );
static int hilo( BinaryNode A, BinaryNode ;

void printPreOrder( ) const;
void printPostOrder( ) const;
void printInOrder( ) const;

BinaryNode *duplicate( ) const;

public: // To keep things simple
Object element;
BinaryNode *left;
BinaryNode *right;
};

template <class Object>
class TreeIterator;


// BinaryTree class; stores a binary tree.
//
// CONSTRUCTION: with (a) no parameters or (b) an object to
// be placed in the root of a one-element tree.
//
// *******************PUBLIC OPERATIONS**********************
// Various tree traversals, size, height, isEmpty, makeEmpty.
// Also, the following tricky method:
// void merge( Object root, BinaryTree t1, BinaryTree t2 )
// --> Construct a new tree
// *******************ERRORS*********************************
// Error message printed for illegal merges.

template <class Object>
class BinaryTree
{
public:
BinaryTree( ) : root( NULL ) { }
BinaryTree( const Object & rootItem )
: root( new Node( rootItem ) ) { }
BinaryTree( const BinaryTree & rhs )
: root( NULL ) { *this = rhs; }

~BinaryTree( )
{ makeEmpty( ); }

const BinaryTree & operator= ( const BinaryTree & rhs );

// Recursive traversals, with printing
void printPreOrder( ) const
{ if( root != NULL ) root->printPreOrder( ); }
void printInOrder( ) const
{ if( root != NULL ) root->printInOrder( ); }
void printPostOrder( ) const
{ if( root != NULL ) root->printPostOrder( ); }

void makeEmpty( )
{ makeEmpty( root ); }
bool isEmpty( ) const
{ return root == NULL; }

// Combine t1 and t2
void merge( const Object & rootItem, BinaryTree & t1, BinaryTree & t2 );

int size( ) const
{ return Node::size( root ); }
int height( ) const
{ return Node::height( root ); }

private:
typedef BinaryNode<Object> Node;
Node *root;

friend class TreeIterator<Object>;
void makeEmpty( BinaryNode<Object> * & t );
};

#endif


// Constructor.
template <class Object>
BinaryNode<Object>::BinaryNode( const Object & theElement,
BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt )
{
}

// Return size of tree rooted at t.
template <class Object>
int BinaryNode<Object>::size( BinaryNode<Object> * t )
{
if( t == NULL )
return 0;
else
return 1 + size( t->left ) + size( t->right );
}

#define max MAX

template <class Comparable>
Comparable max( const Comparable & a, const Comparable & b )
{
return a > b ? a : b;
}

// Return height of tree rooted at t.
template <class Object>
int BinaryNode<Object>::height( BinaryNode<Object> * t )
{
if( t == NULL )
return -1;
else
return 1 + max( height( t->left ), height( t->right ) );
}

#undef max

// Print the tree rooted at current node using preorder traversal.
template <class Object>
void BinaryNode<Object>::printPreOrder( ) const
{
cout << element << endl; // Node
if( left != NULL )
left->printPreOrder( ); // Left
if( right != NULL )
right->printPreOrder( ); // Right
}

// Print the tree rooted at current node using postorder traversal.
template <class Object>
void BinaryNode<Object>::printPostOrder( ) const
{
if( left != NULL ) // Left
left->printPostOrder( );
if( right != NULL ) // Right
right->printPostOrder( );
cout << element << endl; // Node
}

// Print the tree rooted at current node using inorder traversal.
template <class Object>
void BinaryNode<Object>::printInOrder( ) const
{
if( left != NULL ) // Left
left->printInOrder( );
cout << element << endl; // Node
if( right != NULL )
right->printInOrder( ); // Right
}

// Return a pointer to a node that is the root of a
// duplicate of the tree rooted at the current node.
template <class Object>
BinaryNode<Object> * BinaryNode<Object>::duplicate( ) const
{
BinaryNode<Object> *root =
new BinaryNode<Object>( element );

if( left != NULL ) // If there's a left subtree
root->left = left->duplicate( ); // Duplicate; attach
if( right != NULL ) // If there's a right subtree
root->right = right->duplicate( ); // Duplicate; attach

return root; // Return resulting tree
}

// Deep copy.
template <class Object>
const BinaryTree<Object> &
BinaryTree<Object>::operator= ( const BinaryTree<Object> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
if( rhs.root != NULL )
root = rhs.root->duplicate( );
}

return *this;
}

// Merge routine for BinaryTree class.
// Forms a new tree from rootItem, t1 and t2.
// Does not allow t1 and t2 to be the same.
// Correctly handles other aliasing conditions.
template <class Object>
void BinaryTree<Object>::merge( const Object & rootItem,
BinaryTree<Object> & t1, BinaryTree<Object> & t2 )
{
if( t1.root == t2.root && t1.root != NULL )
{
cerr << "Cannot merge a tree with itself; merge aborted." << endl;
return;
}

Node *oldRoot = root; // Save old root

// Allocate new node
root = new Node( rootItem, t1.root, t2.root );

// Deallocate nodes in the original tree
if( this != &t1 && this != &t2 )
makeEmpty( oldRoot );

// Ensure that every node is in one tree
if( this != &t1 )
t1.root = NULL;
if( this != &t2 )
t2.root = NULL;
}

// Make tree rooted at t empty, freeing nodes, and setting t to NULL.
template <class Object>
void BinaryTree<Object>::makeEmpty( BinaryNode<Object> * & t )
{
if( t != NULL )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
t = NULL;
}
}

// Return range of two give points of tree rooted at t.
template <class Object>
int BinaryNode<Object>::hilo( BinaryNode<Object> A, BinaryNode<Object> B )
{
if( A == NULL || B == NULL )
return 0;
else
{
// cout << "The elements between" << A << "and" << B << "are /n";
do
{
cout << A << "/n";
A++;
} while(A <= ;
}
}

int main()
{
BinaryTree Tr
return 0;
}

Zek

Okay, for starters, you can't do A++ or A <= B because those operators are not defined for the class. Those only work by default for basic types; the compiler doesn't have common sense, it has no idea what you want those operations to do for a custom class. I'm guessing you haven't learned how to overload those functions yet so don't worry about it, for the comparison just use A.element <= B.element. Like you said, what you really need here is a basic understanding of how trees work. Look over your course material again and try to write a basic function to give yourself the idea. For example, write a program that outputs the elements in a binary tree from lowest to highest.

The best way to imagine a recursive function is to pretend that it already works: try to think about how you would write your function if you already had access to a function that did that. For example, say the function I talked about was called Output(). Imagine that Output() already works as described, printing the elements of a tree from low to high. Think about how you would make that function if you already had access to it. Given the parent node of a tree, you would call Output() on its low branch(which contains every number lower in the tree lower than it), output its element, then call Output() on its high branch. The result is the sorted list. Then just add a base case for when one or both branches are empty, and it's done. That's the basic premise of implementing trees with recursion.

Pheezer

racyrefinedraj wrote: »

I think what you are not reading the assignment carefully enough.

You are attempting to move from one key to the next key using

A++;

Which would only work if A was some sort of iterator.

Problem is, the assignment says

Use a recursive method and do not use an inorder iterator.

So no dice. Note also that your method is not recursive.

I'm going to write out in really vague pseudocode what I think the assignment is asking you to do

-Find key A by traversing the tree (should take O(log N) assuming the tree is balanced)
-Traverse through the tree , visiting every key that is between A and B HINT:What is the defining characteristic of a Binary Search Tree? This should take K steps where K is the number of nodes visited. This is the recursive part.
-When you get to B, stop.

As far as actually getting a binary tree implementation, I would recommend the STL unless your class/text provided you with some other data structures library.

For serious. If you need more help than has been provided by this post, you need to go through your professor or your lab instructors. No one is going to do your homework for you here because that's against the rules. And if you really need a code example, Google has many.