Help with AVL Tree

Syknasty12 (5)
Hi, I am getting errors for my AVL Tree and I can not figure out how to fix them. I believe it is the struct that has the problems, but I am stumped. Any help is greatly appreciated.

My AvlTree.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
 
#ifndef _AVLTREE_H_
#define _AVLTREE_H_

#include <iostream>
using namespace std;

struct AvlNode
{

Comparable element;
AvlNode *left;
AvlNode *right;
int height;

  AvlNode(const Comparable & Element, AvlNode *lt, AvlNode *rt, int h = 0)
  : element(Element), left(lt), right(rt),height(h) 

};

int height(AvlNode *t) const
{
return t == NULL ? -1: t->height;

}

class AvlTree
{

 public:
  AvlTree();
  ~AvlTree();
  void insert(const Comparable & x, AvlNode * & t);
  void erase(const Comparable & x);
  Comparable find(const Comparable & x)
    

 private:
  AvlNode *root;
  AvlNode *temp;
  AvlNode *k1, *k2, *k3;
  void  rotateRightChild(AvlNode * & k1);
 void rotateLeftChild(AvlNode * & k2);
void  doubleRotateLeftChild(AvlNode * & k3);
 void  doubleRotateRightChild(AvlNode * & k1);
 int size;
};
 
#endif


My AvlTree.cpp
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
82
83
84
85
86
87
88
 
#include "AvlTree.h"

AvlTree::AvlTree()
{
size = 0;

root = NULL;

}

AvlTree::~AvlTree()
{

}


void AvlTree::insert(const Comparable & x, AvlNode * & t)
{

  if(t == NULL)
    t = new AvlNode(x, NULL,NULL);
  else if(x < t->element)
    {
      insert(x, t->left);
      if (height(t->left) - height(t->right) == 2)
	if(x < t->left->element)
	  rotateLeftChild(t);
	else
	  doubleRotateLeftChild(t);
    }
  else if(t->element < x)
    {
      insert(x,t->right);
      if(height(t->right) - height(t->left) == 2)
	if(t->right->element < x)
	  rotateRightChild(t);
	else
	  doubleRotateRightChild(t);
    }
  else
    ;
  t->height = max(height(t->left),height(t->right))+ 1;

}

void AvlTree::erase(const Comparable & x)
{

}

Comparable AvlTree::find(const Comparable & x)
{

}


void AvlTree::rotateRightChild(AvlNode * & k1)
{
  AvlNode * k2 = k1->right;
  k1->right = k2->left;
  k2->left = k1;
  k1->height = max(height(k1->left), height(k1->right)) + 1;
  k2->height = max(height(k2->right), k1->height) + 1;
  k1 = k2;
}

void AvlTree::rotateLeftChild(AvlNode * & k2)
{
  AvlNode * k1 = k2->left;
  k2->left = k1->right;
  k1->right =k2;
  k2->height = max(height (k2->left), height(k2->right)) + 1;
  k1->height = max(height (k1->left), k2->height ) + 1;
  k2 = k1;
}


void AvlTree::doubleRotateLeftChild(AvlNode * & k3)
{
  rotateRightChild(k3->left);
  rotateLeftChild(k3);
}

void AvlTree::doubleRotateRightChild(AvlNode * & k1)
{
  rotateLeftChild(k1->right);
  rotateRightChild(k1);
}


My errors:
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
 
AvlTree.h:10: error: ‘Comparable’ does not name a type
AvlTree.h:15: error: expected ‘,’ or ‘...’ before ‘&’ token
AvlTree.h:15: error: ISO C++ forbids declaration of ‘Comparable’ with no type
AvlTree.h:24: error: declaration of ‘int AvlNode::height(AvlNode*) const’
AvlTree.h:13: error: conflicts with previous declaration ‘int AvlNode::height’
AvlTree.h:32: error: expected ‘,’ or ‘...’ before ‘&’ token
AvlTree.h:32: error: ISO C++ forbids declaration of ‘Comparable’ with no type
AvlTree.h:33: error: expected ‘,’ or ‘...’ before ‘&’ token
AvlTree.h:33: error: ISO C++ forbids declaration of ‘Comparable’ with no type
AvlTree.h:34: error: ‘Comparable’ does not name a type
AvlTree.cpp:3: error: cannot define member function ‘AvlNode::AvlTree::AvlTree’ within ‘AvlNode’
AvlTree.cpp:11: error: cannot define member function ‘AvlNode::AvlTree::AvlTree’ within ‘AvlNode’
AvlTree.cpp:17: error: expected ‘,’ or ‘...’ before ‘&’ token
AvlTree.cpp:17: error: ISO C++ forbids declaration of ‘Comparable’ with no type
AvlTree.cpp:17: error: cannot define member function ‘AvlNode::AvlTree::insert’ within ‘AvlNode’
AvlTree.cpp:46: error: expected ‘,’ or ‘...’ before ‘&’ token
AvlTree.cpp:46: error: ISO C++ forbids declaration of ‘Comparable’ with no type
AvlTree.cpp:46: error: cannot define member function ‘AvlNode::AvlTree::erase’ within ‘AvlNode’
AvlTree.cpp:51: error: ‘Comparable’ does not name a type
AvlTree.cpp:57: error: cannot define member function ‘AvlNode::AvlTree::rotateRightChild’ within ‘AvlNode’
AvlTree.cpp:67: error: cannot define member function ‘AvlNode::AvlTree::rotateLeftChild’ within ‘AvlNode’
AvlTree.cpp:78: error: cannot define member function ‘AvlNode::AvlTree::doubleRotateLeftChild’ within ‘AvlNode’
AvlTree.cpp:84: error: cannot define member function ‘AvlNode::AvlTree::doubleRotateRightChild’ within ‘AvlNode’
AvlTree.cpp:88: error: expected `}' at end of input
AvlTree.h: In constructor ‘AvlNode::AvlNode(int)’:
AvlTree.h:16: error: class ‘AvlNode’ does not have any field named ‘element’
AvlTree.h:16: error: ‘Element’ was not declared in this scope
AvlTree.h:16: error: ‘lt’ was not declared in this scope
AvlTree.h:16: error: ‘rt’ was not declared in this scope
AvlTree.h:16: error: class ‘AvlNode’ does not have any field named ‘height’
AvlTree.h:16: error: ‘h’ was not declared in this scope
AvlTree.h:18: error: expected `{' before ‘}’ token
AvlTree.h: In member function ‘int AvlNode::height(AvlNode*) const’:
AvlTree.h:22: error: invalid use of member (did you forget the ‘&’ ?)
AvlTree.h: At global scope:
AvlTree.h:24: error: expected unqualified-id at end of input
make: *** [AvlTree.o] Error 1
Topic archived. No new replies allowed.