C++

Forum

 
Binary Trees

nwd3 (6)
Hello.
I am trying to recursively find the height of a binary tree.
This is what I have. It is passing the tests through 4a. The tests are right but I think I am doing something wrong.
Thanks for any help.
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
//here is the methods
unsigned BST::getHeight()const{
	int result;
if(myNumItems==0){
	return 0;
}else if(myNumItems==1 or myNumItems==2){
	return myNumItems;
}
else{
	result= myRoot->Node::getHeight();
	if(result==0){

		return myNumItems-1;
	}if(result==19034){
		return myNumItems;
	}}
return result;
}
unsigned BST::Node::getHeight(){
	int a =0;
	int b=0;
while(myLeft->contains(NULL)){
	 a++;
}
while(myLeft->contains(NULL)){
	 b++;
}
if(a-b<2){
	return 0;
}else{
	return 19034;
}
}
//here is the tests for the methods it will only pass through 4a.
void BST_Tester::testGetHeight() {
	cout << "Testing getHeight()..." << flush;
	BST bst;
	// empty
	assert( bst.getHeight() == 0 );
	cout << " 0 " << flush;
	// balanced
	bst.insert(44);
	assert( bst.getHeight() == 1 );
	cout << " 1 " << flush;
	bst.insert(22);
	assert( bst.getHeight() == 2 );
	cout << " 2 " << flush;
	bst.insert(66);
	assert( bst.getHeight() == 2 );
	cout << " 3 " << flush;
	bst.insert(77);
	assert( bst.getHeight() == 3 );
	cout << " 4a " << flush;
	bst.insert(55);
	assert( bst.getHeight() == 3 );
	cout << " 4b " << flush;
	bst.insert(33);
	assert( bst.getHeight() == 3 );
	cout << " 4c " << flush;
	bst.insert(11);
	assert( bst.getHeight() == 3 );
	cout << " 4d " << flush;
	bst.insert(88);
	assert( bst.getHeight() == 4 );
	cout << " 4e " << flush;
	// chained ascending
      BST bst2a;
      bst2a.insert(11);
      bst2a.insert(22);
      bst2a.insert(33);
      bst2a.insert(44);
      bst2a.insert(55);
      bst2a.insert(66);
      bst2a.insert(77);
      assert( bst2a.getHeight() == 7 );
      cout << " 5a " << flush;
	// chained descending
      BST bst2b;
      bst2b.insert(77);
      bst2b.insert(66);
      bst2b.insert(55);
      bst2b.insert(44);
      bst2b.insert(33);
      bst2b.insert(22);
      bst2b.insert(11);
      assert( bst2b.getHeight() == 7 );
      cout << " 5b " << flush;
	// four 4-node permutations
	BST bst3;
	bst3.insert(44);
	assert( bst3.getHeight() == 1 );
      cout << " 6a " << flush;
	bst3.insert(22);
	assert( bst3.getHeight() == 2 );
      cout << " 6b " << flush;
	bst3.insert(33);
	assert( bst3.getHeight() == 3 );
      cout << " 6c " << flush;
	bst3.insert(55);
	assert( bst3.getHeight() == 3 );
      cout << " 6d " << flush;
	BST bst4;
	bst4.insert(44);
	assert( bst4.getHeight() == 1 );
      cout << " 7a " << flush;
	bst4.insert(33);
	assert( bst4.getHeight() == 2 );
      cout << " 7b " << flush;
	bst4.insert(22);
	assert( bst4.getHeight() == 3 );
      cout << " 7c " << flush;
	bst4.insert(55);
	assert( bst4.getHeight() == 3 );
      cout << " 7d " << flush;
	BST bst5;
	bst5.insert(44);
	assert( bst5.getHeight() == 1 );
      cout << " 8a " << flush;
	bst5.insert(33);
	assert( bst5.getHeight() == 2 );
      cout << " 8b " << flush;
	bst5.insert(55);
	assert( bst5.getHeight() == 2 );
      cout << " 8c " << flush;
	bst5.insert(66);
	assert( bst5.getHeight() == 3 );
      cout << " 8d " << flush;
	BST bst6;
	bst6.insert(44);
	assert( bst6.getHeight() == 1 );
      cout << " 9a " << flush;
	bst6.insert(33);
	assert( bst6.getHeight() == 2 );
      cout << " 9b " << flush;
	bst6.insert(66);
	assert( bst6.getHeight() == 2 );
      cout << " 9c " << flush;
	bst6.insert(55);
	assert( bst6.getHeight() == 3 );
      cout << " 9d " << flush;
	cout << " Passed!" << endl;
}
cire (8284)
What's with the magic numbers?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <algorithm> // for std::max

    unsigned BST::getHeight() const {
        if (!myRoot)
            return 0;

        return myRoot->getHeight();
    }

    unsigned BST::Node::getHeight() const 
    {
        using std::max;

        unsigned h_left = myLeft ? myLeft->getHeight() : 0;
        unsigned h_right = myRight ? myRight->getHeight() : 0;

        return 1 + max(h_left, h_right);
    }
Topic archived. No new replies allowed.