Btree

Dec 2, 2010 at 1:27am
swalton (94)
Implement a template binary tree class in C++. A binary tree is composed of nodes each of which has two children, left and right. Each tree has a calculated depth equal to the number of levels required to store the nodes in the tree. For example, a tree of 8 nodes would require 4 levels total, level 0 would have 1 node, level 1 would have 2 nodes (3 total now), level 2 would have 4 nodes (7 total) and the 8th node would land in the 4th level (n=3). The depth is a calculated value, not a stored one.

I was given the .h file and need to implement the code on .cpp file.

btree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
#ifndef MY_BTREE_H
#define MY_BTREE_H

// my_btree.h  - binary tree class (no balancing)
using namespace std;

// forward declaration of classes defined in this header
template <class T> class btree;
template <class T> class node;

template <class T> 
class btree
{
public:
  // constructors
  btree();  // no-arg constructor 
  btree(const btree & tree); // copy constructor

  ~btree(); // destructor

  // operations
  bool empty() const;
  int size() const;
  T & root() const;
  // print in-order traversal of the tree
  void print() const; 
  // insert x into tree (wherever it goes)
  void add_element(const T & x); 
  // calculate height of tree
  int height() const; 
  
protected:
  node<T> * rootnode;
  unsigned int my_size();
  
// internal methods used recursively
private: 
  // calculate height of a tree rooted at n
  int height(node<T> *n) const; 
  // print subtree rooted at n (recursive)
  void print(node<T> *n); 
  // insert x in tree rooted at node n (keep in order!)
  void insert(node<T> * n, const T & x); 
  
};

template <class T> 
class node
{

private:
  node(const T & x); // private constructor
  
  T x; // data
  node<T> * left; // left child
  node<T> * right; // right child

  friend class btree<T>;
};


#include "my_btree.cpp"

#endif



here is the .cpp file i have done so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include<iostream>
#include<string>

using namespace std;

template <class T> 
btree<T>::btree()
{
	T element;
	node<T>* parent;
	node<T>* left;
	node<T>* right;
}
template <class T>
btree<T>::btree(const btree & tree)
{

}
template <class T>
btree<T>::~btree()
{
	if (rootnode !=NULL)
		delete tree(rootnode);
}
template <class T>
bool btree<T>::empty() const
{
return 0;
}
template <class T>
int btree<T>::size() const
{
return 0;
}
template <class T>
T & btree<T>::root() const
{
return 0;
}
template <class T>
void btree<T>::print() const
{

}
template <class T>
void btree<T>::add_element(const T & x)
{

}
template <class T>
int btree<T>::height() const
{
return 0;
}
template <class T>
unsigned int btree<T>::my_size()
{
return 0;
}
template <class T>
int btree<T>::height(node<T> *n) const
{
	
return 0;
}
template <class T>
void btree<T>::print(node<T> *n)
{

}
template <class T>
void btree<T>::insert(node<T> * n, const T & x)
{

}
template <class T>
node<T>::node(const T & x)
{

}


Someone help me by finishing this practice assignment so i can work on the actual problem. Thank you
Last edited on Dec 2, 2010 at 1:30am
Dec 2, 2010 at 2:21am
swalton (94)
Someone please help me with this.
Dec 2, 2010 at 3:03am
Disch (13742)
1) Give us more than an hour to respond. Many of us work during the day and aren't here posting 24/7

2) You didn't ask an actual question. What exactly are you looking for? Do you want us to just do your work for you?
Dec 2, 2010 at 7:10am
swalton (94)
Alright then i will be patient.

I want someone to finish off this code so i can see how its done so i can study it can prepare for my final.
Topic archived. No new replies allowed.