help me ! , about Binary Search Tree

B

bushido

bstree.hpp

#ifndef DSALAB_BSTREE_HPP
#define DSALAB_BSTREE_HPP

#include <cstdlib>

template<class T_>
struct Bst_node {
public:
typedef T_ value_type;

Bst_node* left;
Bst_node* right;
value_type data;

explicit Bst_node(const value_type& val = value_type())
: left(0), right(0), data(val) {}

Bst_node(const value_type& val, Bst_node* l, Bst_node* r)
: left(l), right(r), data(val) {}
};

template<class T_>
void destroy_tree(Bst_node<T_>* root)
{
if (0 == root)
return;
destroy_tree(root->left);
destroy_tree(root->right);
delete root;
}

template<class T_>
void insert(Bst_node<T_>*& root, const T_& val)
{
if (0 == root) {
root = new Bst_node<T_>(val);
return;
}

Bst_node<T_>* p = root;
for (;;) {
if (val < p->data) {
if (0 == p->left) {
p->left = new Bst_node<T_>(val);
return;
}
p = p->left;
}
else if (val > p->data) {
if (0 == p->right) {
p->right = new Bst_node<T_>(val);
return;
}
p = p->right;
}
else
return;
}
}

template<class T_>
void erase_root(Bst_node<T_>*& root)
{
if (0 == root)
return;

Bst_node<T_>* p = root;
if (0 == p->left)
root = p->right;
else if (0 == p->right)
root = p->left;
else {
Bst_node<T_>* p1 = p->right;
if (0 == p1->left) {
p1->left = p->left;
root = p1;
}
else {
Bst_node<T_>* p2 = p1->left;
while (p2->left != 0) {
p1 = p1->left;
p2 = p2->left;
}

p1->left = p2->right;

root = p2;
p2->left = p->left;
p2->right = p->right;
}
}

delete p;
}

template<class T_>
void erase(Bst_node<T_>*& root, const T_& val)
{
if (0 == root)
return;

Bst_node<T_>** pp = &root;
Bst_node<T_>* p;
for (;;) {
p = *pp;
if (val < p->data) {
if (0 == p->left)
return;
pp = &p->left;
}
else if (val > p->data) {
if (0 == p->right)
return;
pp = &p->right;
}
else {
erase_root(*pp);
break;
}
}
}

//----------------------------------------------------------------------------

template<class T_>
const Bst_node<T_>* find(const Bst_node<T_>* root, const T_& val)
{
if (0 == root)
return 0;

for (;;) {
if (val < root->data) {
if (0 == root->left)
return 0;
root = root->left;
}
else if (val > root->data) {
if (0 == root->right)
return 0;
root = root->right;
}
else
return root;
}
}

template<class T_>
bool contains(const Bst_node<T_>* root, const T_& val)
{ return find(root, val) != 0; }

template<class T_>
const Bst_node<T_>* min_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->left != 0)
root = root->left;
return root;
}

template<class T_>
const Bst_node<T_>* max_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->right != 0)
root = root->right;
return root;
}

template<class T_>
std::size_t height(const Bst_node<T_>* root, std::size_t h = 0)
{
if (0 == root)
return h;

const std::size_t lh = height(root->left, h + 1);
const std::size_t rh = height(root->right, h + 1);
return (lh > rh)? lh: rh;
}

//----------------------------------------------------------------------------

template<class T_>
class Bst_owner {
public:
typedef T_ value_type;

typedef Bst_node<value_type> node_type;

const node_type* root() const { return root_; }
node_type*& root() { return root_; }

// manipulator
void clear()
{
destroy_tree(root_);
root_ = 0;
}

Bst_owner& assign(node_type* root)
{
clear();
root_ = root;
return *this;
}

// accessor
bool empty() const { return 0 == root_; }

// ctor and dtor
Bst_owner(): root_(0) {}
~Bst_owner() { destroy_tree(root_); }
private:
node_type* root_;

// no copying allowed
Bst_owner(const Bst_owner&);
Bst_owner& operator=(const Bst_owner&);
};

#endif /* DSALAB_BSTREE_HPP */
















source.cpp

#include "bstree.hpp"

//----------------------------------------------------------------------------

template<class T_>
void erase_min(Bst_node<T_>*& root)
{
// TODO: do your work here


}

template<class T_>
void erase_max(Bst_node<T_>*& root)
{
// TODO: do your work here
}

template<class T_>
std::size_t count_at_depth(const Bst_node<T_>* root, std::size_t
depth)
{
// TODO: do your work here
return 0;
}

template<class T_>
std::size_t size(const Bst_node<T_>* root)
{
// TODO: do your work here
return 0;
}

//----------------------------------------------------------------------------

#include <ostream>

template<class T_>
void display_tree(
const Bst_node<T_>* root, std::eek:stream& os, unsigned indent = 0)
{
if (0 == root)
return;
display_tree(root->left, os, indent + 1);
for (unsigned i = 0; i != indent; ++i)
os << " ";
os << root->data << "\n";
display_tree(root->right, os, indent + 1);
}

template<class T_>
void print_preorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
os << ' ' << root->data;
print_preorder(root->left, os);
print_preorder(root->right, os);
}

template<class T_>
void print_postorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
print_postorder(root->left, os);
print_postorder(root->right, os);
os << ' ' << root->data;
}

template<class T_>
void print_inorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
print_inorder(root->left, os);
os << ' ' << root->data;
print_inorder(root->right, os);
}

template<class T_>
void print_tree(const Bst_node<T_>* tree, std::eek:stream& os)
{
using namespace std;
const size_t h = height(tree);
os << "size = " << size(tree) << ", height = "
<< h << " empty = " << (tree == 0);
if (tree != 0)
os << ", min = " << min_node(tree)->data
<< ", max = " << max_node(tree)->data;
os << '\n';

for (size_t i = 0; i < h; ++i)
os << "count_at_depth(" << i << ") = "
<< count_at_depth(tree, i) << '\n';

os << "\ninorder\n";
print_inorder(tree, os);
os << "\npreorder\n";
print_preorder(tree, os);
os << "\n----------" << endl;
}

//----------------------------------------------------------------------------

#include <iostream>
#include <vector>

#ifdef _MSC_VER
#ifdef _DEBUG
#include <crtdbg.h>
#endif
#endif

int main()
{
#ifdef _MSC_VER
#ifdef _DEBUG
// turn on memory leak checking
::_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
#endif
using namespace std;

cout << boolalpha;

Bst_owner<int> tree_owner;
Bst_node<int>*& tree = tree_owner.root();

print_tree(tree, std::cout);

// add some elements
const int elements[] = { 4, 11, 8, 8, 27, 7, 5, 6, 15, 32, -5 };
const size_t num_elements = sizeof(elements) /
sizeof(elements[0]);
for (size_t i = 0; i < num_elements; ++i) {
cout << "inserting " << elements << "\n";
insert(tree, elements);
}

print_tree(tree, std::cout);

display_tree(tree, std::cout);

// search for some elements
const int test_elements[] = { 4, 8, 7, 5, 32, 31, 10, 2 };
const size_t num_test_elements
= sizeof(test_elements) / sizeof(test_elements[0]);
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements << "? ";
cout << contains(tree, test_elements) << '\n';
}
cout << endl;

// remove some elements
const int elements_to_erase[] = { 32, 5, 6, 29, 16, 4 };
const size_t num_elements_to_erase
= sizeof(elements_to_erase) / sizeof(elements_to_erase[0]);
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "erasing " << elements_to_erase << '\n';
erase(tree, elements_to_erase);
}
cout << endl;

print_tree(tree, std::cout);

// search for some elements
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements << "? ";
cout << contains(tree, test_elements) << '\n';
}
cout << endl;

// insert elements back
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "inserting " << elements_to_erase << "\n";
insert(tree, elements_to_erase);
}
cout << endl;

print_tree(tree, std::cout);

cout << "remove_max 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_max(tree);
}
print_tree(tree, std::cout);

cout << "remove_min 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_min(tree);
}

print_tree(tree, std::cout);
}
 
J

Jensen Somers

Hello,
bstree.hpp

#ifndef DSALAB_BSTREE_HPP
#define DSALAB_BSTREE_HPP

#include <cstdlib>

template<class T_>
struct Bst_node {
public:
typedef T_ value_type;

Bst_node* left;
Bst_node* right;
value_type data;

explicit Bst_node(const value_type& val = value_type())
: left(0), right(0), data(val) {}

Bst_node(const value_type& val, Bst_node* l, Bst_node* r)
: left(l), right(r), data(val) {}
};

template<class T_>
void destroy_tree(Bst_node<T_>* root)
{
if (0 == root)
return;
destroy_tree(root->left);
destroy_tree(root->right);
delete root;
}

template<class T_>
void insert(Bst_node<T_>*& root, const T_& val)
{
if (0 == root) {
root = new Bst_node<T_>(val);
return;
}

Bst_node<T_>* p = root;
for (;;) {
if (val < p->data) {
if (0 == p->left) {
p->left = new Bst_node<T_>(val);
return;
}
p = p->left;
}
else if (val > p->data) {
if (0 == p->right) {
p->right = new Bst_node<T_>(val);
return;
}
p = p->right;
}
else
return;
}
}

template<class T_>
void erase_root(Bst_node<T_>*& root)
{
if (0 == root)
return;

Bst_node<T_>* p = root;
if (0 == p->left)
root = p->right;
else if (0 == p->right)
root = p->left;
else {
Bst_node<T_>* p1 = p->right;
if (0 == p1->left) {
p1->left = p->left;
root = p1;
}
else {
Bst_node<T_>* p2 = p1->left;
while (p2->left != 0) {
p1 = p1->left;
p2 = p2->left;
}

p1->left = p2->right;

root = p2;
p2->left = p->left;
p2->right = p->right;
}
}

delete p;
}

template<class T_>
void erase(Bst_node<T_>*& root, const T_& val)
{
if (0 == root)
return;

Bst_node<T_>** pp = &root;
Bst_node<T_>* p;
for (;;) {
p = *pp;
if (val < p->data) {
if (0 == p->left)
return;
pp = &p->left;
}
else if (val > p->data) {
if (0 == p->right)
return;
pp = &p->right;
}
else {
erase_root(*pp);
break;
}
}
}

//----------------------------------------------------------------------------

template<class T_>
const Bst_node<T_>* find(const Bst_node<T_>* root, const T_& val)
{
if (0 == root)
return 0;

for (;;) {
if (val < root->data) {
if (0 == root->left)
return 0;
root = root->left;
}
else if (val > root->data) {
if (0 == root->right)
return 0;
root = root->right;
}
else
return root;
}
}

template<class T_>
bool contains(const Bst_node<T_>* root, const T_& val)
{ return find(root, val) != 0; }

template<class T_>
const Bst_node<T_>* min_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->left != 0)
root = root->left;
return root;
}

template<class T_>
const Bst_node<T_>* max_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->right != 0)
root = root->right;
return root;
}

template<class T_>
std::size_t height(const Bst_node<T_>* root, std::size_t h = 0)
{
if (0 == root)
return h;

const std::size_t lh = height(root->left, h + 1);
const std::size_t rh = height(root->right, h + 1);
return (lh > rh)? lh: rh;
}

//----------------------------------------------------------------------------

template<class T_>
class Bst_owner {
public:
typedef T_ value_type;

typedef Bst_node<value_type> node_type;

const node_type* root() const { return root_; }
node_type*& root() { return root_; }

// manipulator
void clear()
{
destroy_tree(root_);
root_ = 0;
}

Bst_owner& assign(node_type* root)
{
clear();
root_ = root;
return *this;
}

// accessor
bool empty() const { return 0 == root_; }

// ctor and dtor
Bst_owner(): root_(0) {}
~Bst_owner() { destroy_tree(root_); }
private:
node_type* root_;

// no copying allowed
Bst_owner(const Bst_owner&);
Bst_owner& operator=(const Bst_owner&);
};

#endif /* DSALAB_BSTREE_HPP */
















source.cpp

#include "bstree.hpp"

//----------------------------------------------------------------------------

template<class T_>
void erase_min(Bst_node<T_>*& root)
{
// TODO: do your work here


}

template<class T_>
void erase_max(Bst_node<T_>*& root)
{
// TODO: do your work here
}

template<class T_>
std::size_t count_at_depth(const Bst_node<T_>* root, std::size_t
depth)
{
// TODO: do your work here
return 0;
}

template<class T_>
std::size_t size(const Bst_node<T_>* root)
{
// TODO: do your work here
return 0;
}

//----------------------------------------------------------------------------

#include <ostream>

template<class T_>
void display_tree(
const Bst_node<T_>* root, std::eek:stream& os, unsigned indent = 0)
{
if (0 == root)
return;
display_tree(root->left, os, indent + 1);
for (unsigned i = 0; i != indent; ++i)
os << " ";
os << root->data << "\n";
display_tree(root->right, os, indent + 1);
}

template<class T_>
void print_preorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
os << ' ' << root->data;
print_preorder(root->left, os);
print_preorder(root->right, os);
}

template<class T_>
void print_postorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
print_postorder(root->left, os);
print_postorder(root->right, os);
os << ' ' << root->data;
}

template<class T_>
void print_inorder(const Bst_node<T_>* root, std::eek:stream& os)
{
if (0 == root)
return;
print_inorder(root->left, os);
os << ' ' << root->data;
print_inorder(root->right, os);
}

template<class T_>
void print_tree(const Bst_node<T_>* tree, std::eek:stream& os)
{
using namespace std;
const size_t h = height(tree);
os << "size = " << size(tree) << ", height = "
<< h << " empty = " << (tree == 0);
if (tree != 0)
os << ", min = " << min_node(tree)->data
<< ", max = " << max_node(tree)->data;
os << '\n';

for (size_t i = 0; i < h; ++i)
os << "count_at_depth(" << i << ") = "
<< count_at_depth(tree, i) << '\n';

os << "\ninorder\n";
print_inorder(tree, os);
os << "\npreorder\n";
print_preorder(tree, os);
os << "\n----------" << endl;
}

//----------------------------------------------------------------------------

#include <iostream>
#include <vector>

#ifdef _MSC_VER
#ifdef _DEBUG
#include <crtdbg.h>
#endif
#endif

int main()
{
#ifdef _MSC_VER
#ifdef _DEBUG
// turn on memory leak checking
::_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
#endif
using namespace std;

cout << boolalpha;

Bst_owner<int> tree_owner;
Bst_node<int>*& tree = tree_owner.root();

print_tree(tree, std::cout);

// add some elements
const int elements[] = { 4, 11, 8, 8, 27, 7, 5, 6, 15, 32, -5 };
const size_t num_elements = sizeof(elements) /
sizeof(elements[0]);
for (size_t i = 0; i < num_elements; ++i) {
cout << "inserting " << elements << "\n";
insert(tree, elements);
}

print_tree(tree, std::cout);

display_tree(tree, std::cout);

// search for some elements
const int test_elements[] = { 4, 8, 7, 5, 32, 31, 10, 2 };
const size_t num_test_elements
= sizeof(test_elements) / sizeof(test_elements[0]);
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements << "? ";
cout << contains(tree, test_elements) << '\n';
}
cout << endl;

// remove some elements
const int elements_to_erase[] = { 32, 5, 6, 29, 16, 4 };
const size_t num_elements_to_erase
= sizeof(elements_to_erase) / sizeof(elements_to_erase[0]);
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "erasing " << elements_to_erase << '\n';
erase(tree, elements_to_erase);
}
cout << endl;

print_tree(tree, std::cout);

// search for some elements
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements << "? ";
cout << contains(tree, test_elements) << '\n';
}
cout << endl;

// insert elements back
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "inserting " << elements_to_erase << "\n";
insert(tree, elements_to_erase);
}
cout << endl;

print_tree(tree, std::cout);

cout << "remove_max 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_max(tree);
}
print_tree(tree, std::cout);

cout << "remove_min 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_min(tree);
}

print_tree(tree, std::cout);
}
Click to expand...


You don't really state what the problem is with this code. The only
thing I find are some TODO messages without further explanation of the
actual problem, which makes me believe this is some kind of homework
assignment. Nobody is going to do that for you.

- Jensen
 
S

sassa

You don't really state what the problem is with this code. The only
thing I find are some TODO messages without further explanation of the
actual problem, which makes me believe this is some kind of homework
assignment. Nobody is going to do that for you.

- Jensen
Click to expand...

I agree. If you cant manage this stuff in college/university your
going to drown in a real job ;)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Is there in memory tree structure faster than std::map? 11
Binary Search Tree Verification Help 1
Tree driving me nuts! 13
Binary Search Tree Input Problem 4
Main for binary search tree 2
Binary Search Tree Problems 0
bench: binary trees 10
Can anyone help me whats wrong with this 2

Members online

No members online now.
Total: 34 (members: 1, guests: 33)
Robots: 89

Forum statistics

Threads
473,754
Messages
2,569,521
Members
44,995
Latest member
PinupduzSap

Latest Threads

Top