Skip to content

Commit a64fd3f

Browse files
poncoeponcoe
committed
improv bab 7 - binnarytree
1 parent a56bc3f commit a64fd3f

3 files changed

Lines changed: 163 additions & 0 deletions

File tree

‎bab7_binnarytree/main.cpp‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
#include"tree.cpp"
2+
3+
4+
int main()
5+
{
6+
tree a;
7+
a = alokasinode(13);
8+
9+
left(a) = alokasinode(14);
10+
left(left(a)) = alokasinode(39);
11+
left(left(left(a))) = alokasinode(31);
12+
right(left(left(a))) = alokasinode(50);
13+
right(left(a)) = alokasinode(28);
14+
left(right(left(a))) = alokasinode(14);
15+
right(a) = alokasinode(2);
16+
left(right(a)) = alokasinode(18);
17+
right(right(a)) = alokasinode(19);
18+
left(right(right(a))) = alokasinode(15);
19+
right(left(right(right(a)))) = alokasinode(41);
20+
right(right(right(a))) = alokasinode(21);
21+
22+
cout<<"Banyak Vertex : "<<nVertex(a);
23+
cout<<endl;
24+
25+
cout<<"Banyak Daun : "<<nLeaves(a);
26+
cout<<endl;
27+
28+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 13))<<endl;
29+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 14))<<endl;
30+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 39))<<endl;
31+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 31))<<endl;
32+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 50))<<endl;
33+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 28))<<endl;
34+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 14))<<endl;
35+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 2))<<endl;
36+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 18))<<endl;
37+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 19))<<endl;
38+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 15))<<endl;
39+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 21))<<endl;
40+
cout<<"Harusnya : "<<id(depthFirstSearch(a, 41))<<endl;
41+
cout<<"Harusnya : "<<depthFirstSearch(a, 12)<<endl;
42+
cout<<"Harusnya : "<<depthFirstSearch(NULL, 12)<<endl;
43+
44+
cout<<"Harusnya : "<<height(a)-1<<endl;
45+
cout<<"Harusnya true(1) : "<<balanced(a)<<endl;
46+
47+
48+
return 0;
49+
}

‎bab7_binnarytree/tree.cpp‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
#include"tree.h"
2+
3+
4+
tree alokasinode(int id){
5+
tree a;
6+
a = new node;
7+
left(a) = NULL;
8+
right(a) = NULL;
9+
id(a) = id;
10+
return a;
11+
}
12+
13+
int nVertex(tree T){
14+
if(T==NULL){
15+
return 0;
16+
}
17+
else{
18+
return 1 + nVertex(left(T)) + nVertex(right(T));
19+
}
20+
}
21+
22+
23+
int nLeaves(tree T){
24+
if(T==NULL){
25+
return 0;
26+
}
27+
else if(left(T)==NULL && right(T)==NULL){
28+
return 1;
29+
}
30+
else{
31+
return nLeaves(left(T)) + nLeaves(right(T));
32+
}
33+
}
34+
35+
36+
adrnode depthFirstSearch(tree T, int X){
37+
if(T == NULL){
38+
return NULL;
39+
}
40+
else{
41+
if(id(T) == X){
42+
return T;
43+
}
44+
else{
45+
adrnode L = depthFirstSearch(left(T),X);
46+
adrnode R = depthFirstSearch(right(T),X);
47+
if(L != NULL){
48+
return L;
49+
}
50+
else if(R != NULL){
51+
return R;
52+
}
53+
else{
54+
return NULL;
55+
}
56+
}
57+
}
58+
}
59+
60+
int height(tree T){
61+
if (T != NULL){
62+
int l;
63+
int r;
64+
l = 1 + height(left(T));
65+
r = 1 + height(right(T));
66+
if (l>r){
67+
return l;
68+
}else{
69+
return r;
70+
}
71+
}
72+
}
73+
74+
bool balanced(tree T){
75+
if (T != NULL){
76+
int l = height(left(T));
77+
int r = height(right(T));
78+
if(abs(l-r)<=1){
79+
return 1;
80+
}
81+
return 0;
82+
}
83+
}

‎bab7_binnarytree/tree.h‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#ifndef TREE_H_INCLUDED
2+
#define TREE_H_INCLUDED
3+
4+
#include<iostream>
5+
#include<stdlib.h>
6+
#define Nil NULL
7+
#define id(a) (a)->id
8+
#define left(a) (a)->left
9+
#define right(a) (a)->right
10+
11+
using namespace std;
12+
13+
typedef struct node *adrnode;
14+
15+
struct node{
16+
int id;
17+
adrnode left;
18+
adrnode right;
19+
};
20+
21+
typedef adrnode tree;
22+
23+
tree alokasinode(int id);
24+
25+
int nLeaves(tree T);
26+
int nVertex(tree root);
27+
adrnode depthFirstSearch(tree T, int X);
28+
int height(tree T);
29+
bool balanced(tree T);
30+
31+
#endif // TREE_H_INCLUDED

0 commit comments

Comments
 (0)