Untitled
unknown
plain_text
2 years ago
28 kB
13
Indexable
// Search & Sort
// Bai 1
#include <iostream>
using namespace std;
int main()
{
int n, m, x;
cin >> n;
int *a = new int[n];
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> m;
while (m != 0){
cin >> x;
int i = 0;
for (i = 0; i < n; i++){
if (a[i] == x){
cout << i << endl;
m--;
break;
}
}
if (i == n) {
cout << "-1" << endl;
m--;
}
}
return 0;
}
// Bai 2
#include <iostream>
using namespace std;
void inputArray (int *&a, int &n){
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
void findElements(int a[], int n, int m){
int x;
cin >> m;
while (m != 0){
cin >> x;
int i = 0;
for (i = 0; i < n; i++){
if (a[i] == x){
cout << i << endl;
m--;
break;
}
}
if (i == n) {
cout << "-1" << endl;
m--;
}
}
}
int main()
{
int n,m;
int *a=NULL;
inputArray(a,n);
findElements(a,n,m);
return 0;
}
// Bai 3
#include <iostream>
using namespace std;
void inputArray (int *&a, int &n){
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
void findElements(int a[], int n, int m){
int x;
cin >> m;
while (m != 0){
cin >> x;
cout << binarySearch(a, 0, n - 1, x) << endl;
m--;
}
}
int main()
{
int n,m;
int *a=NULL;
inputArray(a,n);
findElements(a,n,m);
return 0;
}
// Bai 4
#include <iostream>
using namespace std;
void inputArray (int *&a, int &n){
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
int binarySearch2(int arr[], int n, int x){
int low = 0, high = n - 1;
while (low <= high){
int mid = low + (high - low) / 2;
if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
return mid;
else if (x < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
/* int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
low = mid + 1;
}
}
return res;
*/
}
int main()
{
int n, *a = NULL;
inputArray(a,n); //Luu y van de tham chieu cho con tro a va n
// nhap cac gia tri can tim, neu nhap -1 thi ket thuc viec tim kiem
int x;
while(1)
{
cin>>x;
if(x==-1)break;
cout<<binarySearch2(a,n,x)<<endl;
}
return 0;
}
// Selection Sort
#include <iostream>
using namespace std;
void Swap (int &a, int & b){
int c = a;
a = b;
b = c;
return;
}
void Selection_Sort(int a[], int n){
int Min;//vị trí phần tử nhỏ nhất trong dãy hiện hành
for(int i = 0; i < n - 1; i++){
Min = i;
for(int j = i + 1; j < n; j++){
if (a[j] < a[Min]){
Min = j;//ghi nhận vị trí phần tử nhỏ nhất
}
}
if (i != Min) Swap(a[Min], a[i]);
}
}
int main()
{
int a[5] = {8, 4, 1, 6, 5};
Selection_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
return 0;
}
// Insertion Sort
#include <iostream>
using namespace std;
void inputArray (int a[], int &n){
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
void printArray (int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << ' ';
}
return;
}
void Swap (int &a, int &b){
int c = a;
a = b;
b = c;
return;
}
void Insertion_Sort(int a[], int n){
int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
x = a[i]; pos = i-1;
//tìm vị trí chèn x
while((pos>=0)&&(a[pos]>x)){
//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chèn x vào danh sách
}
}
int main()
{
int a[5] = {8, 4, 1, 6, 5};
Insertion_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
return 0;
}
// Binary Insertion Sort
#include <iostream>
using namespace std;
void inputArray (int a[], int &n){
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
void printArray (int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << ' ';
}
return;
}
void Swap (int &a, int &b){
int c = a;
a = b;
b = c;
return;
}
int binarySearch(int arr[], int l, int r, int x)
{
while (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid + 1;
else if (arr[mid] > x)
r = mid - 1;
else l = mid + 1;
}
return l;
}
void Insertion_Sort(int a[], int n){
int pos, i, location;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
x = a[i]; pos = i-1;
//tìm vị trí chèn x
location = binarySearch(a, 0, pos, x);
while((pos >= location)){
//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chèn x vào danh sách
// location == pos + 1
}
}
int main()
{
int a[5] = {8, 4, 1, 6, 5};
Insertion_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
return 0;
}
// Quick Sort
/*###Begin banned keyword - each of the following line if appear in code will raise error. regex supported
define
include
using
###End banned keyword*/
#include <iostream>
using namespace std;
void inputArray (int a[], int &n){
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
return;
}
void printArray (int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << ' ';
}
return;
}
void Swap (int &a, int &b){
int c = a;
a = b;
b = c;
return;
}
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
int main()
{
int a[100],n;
inputArray(a,n);
// In mang ban dau
//printArray(a, n);
//Dao mang
quickSort(a, 0, n - 1);
// In mang sau khi dao
//cout << "QuickSort array is" << endl;
printArray(a, n);
return 0;
}
// Bubble Sort
#include<iostream>
using namespace std;
void Swap (int &a, int &b){
int c = a;
a = b;
b = c;
return;
}
void BubbleSort(int a[], int n){
for(int i = n - 1; i >= 1; i--){ // Cải tiến 2: i = n - 1, bth i = 0
bool swapped= true;
for(int j = 0; j < n - i + 1; j++){ // Cải tiến 1: j < n - i + 1, bth j < i
if (a[j] > a[j+1]){
Swap(a[j], a[j + 1]);
swapped = false;
}
}
if (swapped){ // Cải tiến 3: đặt cờ đổi chỗ
break;
}
}
}
int main()
{
int a[5] = {8, 4, 1, 6, 5};
BubbleSort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
return 0;
}
// List
// Bai 1
/*###Begin banned keyword - each of the following line if appear in code will raise error. regex supported
define
include
[
###End banned keyword*/
#include <iostream>
using namespace std;
struct node{
int data; // SV, struct dinh nghia truoc
node *next;
};
struct List{
node *head, *tail;
// int n; // so phan tu trong danh sach
};
node *getnode(int x){
node *temp = new node;
if (temp != NULL){
temp -> next = NULL;
temp -> data = x;
}
return temp;
}
void addHead(List &l, int x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else{
temp -> next = l.head; // l khong phai con tro nen cham
l.head = temp;
}
}
int main(){
List L;
L.head = L.tail = NULL;
int n, x;
while (1){
cin >> n;
if (n == 3) break;
else if (n == 0){
cin >> x;
addHead(L, x);
}
}
node *p = L.head;
while (p != NULL){
cout << p -> data << " ";
p = p -> next;
}
return 0;
}
// Bai 2
/*###Begin banned keyword - each of the following line if appear in code will raise error. regex supported
define
include
###End banned keyword*/
#include <iostream>
using namespace std;
struct node{
int data; // SV, struct dinh nghia truoc
node *next;
};
struct List{
node *head, *tail;
// int n; // so phan tu trong danh sach
};
node *getnode(int x){
node *temp = new node;
if (temp != NULL){
temp -> next = NULL;
temp -> data = x;
}
return temp;
}
void addHead(List &l, int x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else{
temp -> next = l.head; // l khong phai con tro nen cham
l.head = temp;
}
}
void addTail(List &l, int x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else {
l.tail -> next = temp;
l.tail = temp;
}
}
int main(){
List L;
L.head = L.tail = NULL;
int n, x;
while (1){
cin >> n;
if (n == 3) break;
else if (n == 0){
cin >> x;
addHead(L, x);
}
else if (n == 1){
cin >> x;
addTail(L, x);
}
}
node *p = L.head;
while (p != NULL){
cout << p -> data << " ";
p = p -> next;
}
return 0;
}
// Bai 3
/*###Begin banned keyword - each of the following line if appear in code will raise error. regex supported
define
include
###End banned keyword*/
#include <iostream>
using namespace std;
struct node{
int data; // SV, struct dinh nghia truoc
node *next;
};
struct List{
node *head, *tail;
// int n; // so phan tu trong danh sach
};
node *getnode(int x){
node *temp = new node;
if (temp != NULL){
temp -> next = NULL;
temp -> data = x;
}
return temp;
}
void addHead(List &l, int x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else{
temp -> next = l.head; // l khong phai con tro nen cham
l.head = temp;
}
}
void addTail(List &l, int x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else {
l.tail -> next = temp;
l.tail = temp;
}
}
node* Search(List l, int x)
{
node* node = l.head;
while (node != NULL && node->data != x){
node = node->next;
}
if (node != NULL) return node;
return NULL;
}
void addAfter(List &l, int a, int b){
node* p = Search(l, a);
if (p == NULL) addHead(l, b);
else {
node* q = getnode(b);
q->next = p->next;
p->next = q;
if (l.tail == p)
l.tail = q;
}
return;
}
int main(){
List L;
L.head = L.tail = NULL;
int n, x, a, b;
while (1){
cin >> n;
if (n == 3) break;
else if (n == 0){
cin >> x;
addHead(L, x);
}
else if (n == 1){
cin >> x;
addTail(L, x);
}
else if (n == 2){
cin >> a >> b;
addAfter(L, a, b);
}
}
node *p = L.head;
while (p != NULL){
cout << p -> data << " ";
p = p -> next;
}
return 0;
}
// DList
// Bai 1
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
typedef struct PROVINCE{
int id;
string name;
int pop;
float area;
} pro;
struct node{
pro info; // SV, struct dinh nghia truoc
node *next;
};
struct List{
node *head, *tail;
// int n; // so phan tu trong danh sach
};
struct
node *getnode(pro x){
node *temp = new node;
if (temp != NULL){
temp -> next = NULL;
temp -> info.id = x.id;
temp -> info.name = x.name;
temp -> info.pop = x.pop;
temp -> info.area = x.area;
}
return temp;
}
void Init(List &L){
L.head = L.tail = NULL;
}
void addTail(List &l, pro x){
node *temp = getnode(x);
if(l.head == NULL){
l.head = l.tail = temp;
}
else {
l.tail -> next = temp;
l.tail = temp;
}
}
void inputProvince(pro &x){
cin >> x.id;
cin.ignore();
getline(std::cin, x.name);
cin >> x.pop;
cin >> x.area;
}
void inputListProvinces(List &L){
int n;
pro x;
cin >> n;
for (int i = 0; i < n; i++){
inputProvince(x);
addTail(L, x);
}
}
void outputProvince(pro x){
cout << x.id << "\t";
cout << x.name << "\t";
cout << x.pop << "\t";
cout << x.area << endl;
}
void outputListProvinces(List L){
node *p = L.head;
while (p != NULL){
outputProvince(p -> info);
p = p -> next;
}
}
void outputProvincesMore1MillionPop(List L){
node *p = L.head;
while (p != NULL){
if (p -> info.pop > 1000){
cout << p -> info.id << "\t";
cout << p -> info.name << "\t";
cout << p -> info.pop << "\t";
cout << p -> info.area << endl;
}
p = p -> next;
}
}
void Swap(node *&a, node *&b){
node* temp = a;
a = b;
b = temp;
return;
}
node* findProMaxArea(List l){
node *p = l.head;
node *MAX = l.head;
while (p != NULL){
if (p->info.area > MAX->info.area) Swap(p, MAX);
p = p->next;
}
return MAX;
}
void outputProvince(node *p){
cout << p -> info.id << "\t";
cout << p -> info.name << "\t";
cout << p -> info.pop << "\t";
cout << p -> info.area << endl;
return;
}
int main()
{
List L;
Init(L);
inputListProvinces(L);
cout<<"List of provinces:"<<endl;
cout<<"ID\t|Province\t|Population\t|Area"<<endl;
outputListProvinces(L);
cout<<"Provinces with a population of more than 1 million:"<<endl;
outputProvincesMore1MillionPop(L);
cout<<"The largest province:"<<endl;
node *p = findProMaxArea(L);
if(p) outputProvince(p->info);
return 0;
}
// Bai 2
#include <iostream>
using namespace std;
struct DNode
{
int info;
DNode *pNext, *pPrev;
};
struct DList
{
DNode *pHead, *pTail;
};
DNode *getnode(int x){
DNode *temp = new DNode;
if (temp != NULL){
temp -> pNext = temp -> pPrev = NULL;
temp -> info = x;
}
return temp;
}
void init(DList &l){
l.pHead = l.pTail = NULL;
}
void addHead(DList &l, int x){
DNode *temp = getnode(x);
if(l.pHead == NULL){
l.pHead = l.pTail = temp;
}
else{
temp -> pNext = l.pHead; // l khong phai con tro nen cham
l.pHead -> pPrev = temp;
l.pHead = temp;
}
}
void addTail(DList &l, int x){
DNode *temp = getnode(x);
if(l.pHead == NULL){
l.pHead = l.pTail = temp;
}
else {
temp -> pPrev = l.pTail;
l.pTail -> pNext = temp;
l.pTail = temp;
}
}
void createList(DList &L){
int x;
while(1){
cin >> x;
if (x == -1) return;
addTail(L, x);
}
}
void printList(DList l){
DNode *p = l.pHead;
if (p == NULL){
cout << "List is empty";
return;
}
while (p != NULL){
cout << p->info << " ";
p = p->pNext;
}
}
DNode* Search(DList l, int x){
DNode* node = l.pHead;
while (node != NULL && node->info != x){
node = node->pNext;
}
return node;
}
void addAfter(DList &l, int a, int b){
DNode* p = Search(l, a);
if (p == NULL) cout << "\nCan't find the value "<<a;
else {
DNode* q = getnode(b);
q->pNext = p->pNext;
q->pPrev = p;
if (l.pTail == p) l.pTail = q; // CHU Y
else p->pNext->pPrev = q;
p->pNext = q;
if (l.pTail == p)
l.pTail = q;
}
}
void addBefore(DList &l, int a, int b){
DNode* p = Search(l, a);
if (p == NULL) cout << "\nCan't find the value "<<a;
else {
DNode* q = getnode(b);
q->pNext = p;
q->pPrev = p->pPrev;
if (l.pHead == p) l.pHead = q; // CHU Y
else p->pPrev->pNext = q;
p->pPrev = q;
if (l.pHead == p)
l.pHead = q;
}
}
int main()
{
DList L;
init(L);
int x,y,choice;
cout<<"MENU:";
cout<<"\n1. Create a DList";
cout<<"\n2. Print the DList";
cout<<"\n3. Insert a value at the front";
cout<<"\n4. Insert a value at the end";
cout<<"\n5. Insert a value after a given value (only for the first value found)";
cout<<"\n6. Insert a value before a given value (only for the first value found)";
cout<<"\n7. Insert a value after a given value (for all the same values)";
cout<<"\n8. Insert a value before a given value (for all the same values)";
cout<<"\n20. Exit"<<endl;
while(true)
{
cout<<"\n\t\tPLEASE SELECT YOUR CHOICE: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter your positive integers until you enter -1 to finish: ";
createList(L);
break;
case 2:
cout<<"\nYour current DList: ";
printList(L);
break;
case 3:
cout<<"\nEnter a number: ";
cin>>x;
addHead(L,x);
break;
case 4:
cout<<"\nEnter a number: ";
cin>>x;
addTail(L,x);
break;
case 5:
cout<<"\nEnter two numbers: ";
cin>>x>>y;
addAfter(L,x,y);
break;
case 6:
cout<<"\nEnter two numbers: ";
cin>>x>>y;
addBefore(L,x,y);
break;
case 20:
cout<<"\nGOOD BYE";
return 0;
}
}
return 0;
}
// BST
// Bai 1
#include <iostream>
using namespace std;
struct DNode
{
int info;
DNode *pNext, *pPrev;
};
struct DList
{
DNode *pHead, *pTail;
};
DNode *getnode(int x){
DNode *temp = new DNode;
if (temp != NULL){
temp -> pNext = temp -> pPrev = NULL;
temp -> info = x;
}
return temp;
}
void init(DList &l){
l.pHead = l.pTail = NULL;
}
void addHead(DList &l, int x){
DNode *temp = getnode(x);
if(l.pHead == NULL){
l.pHead = l.pTail = temp;
}
else{
temp -> pNext = l.pHead; // l khong phai con tro nen cham
l.pHead -> pPrev = temp;
l.pHead = temp;
}
}
void addTail(DList &l, int x){
DNode *temp = getnode(x);
if(l.pHead == NULL){
l.pHead = l.pTail = temp;
}
else {
temp -> pPrev = l.pTail;
l.pTail -> pNext = temp;
l.pTail = temp;
}
}
void createList(DList &L){
int x;
while(1){
cin >> x;
if (x == -1) return;
addTail(L, x);
}
}
void printList(DList l){
DNode *p = l.pHead;
if (p == NULL){
cout << "List is empty";
return;
}
while (p != NULL){
cout << p->info << " ";
p = p->pNext;
}
}
DNode* Search(DList l, int x){
DNode* node = l.pHead;
while (node != NULL && node->info != x){
node = node->pNext;
}
return node;
}
void addAfter(DList &l, int a, int b){
DNode* p = Search(l, a);
if (p == NULL) cout << "\nCan't find the value "<<a;
else {
DNode* q = getnode(b);
q->pNext = p->pNext;
q->pPrev = p;
if (l.pTail == p) l.pTail = q; // CHU Y
else p->pNext->pPrev = q;
p->pNext = q;
if (l.pTail == p)
l.pTail = q;
}
}
void addBefore(DList &l, int a, int b){
DNode* p = Search(l, a);
if (p == NULL) cout << "\nCan't find the value "<<a;
else {
DNode* q = getnode(b);
q->pNext = p;
q->pPrev = p->pPrev;
if (l.pHead == p) l.pHead = q; // CHU Y
else p->pPrev->pNext = q;
p->pPrev = q;
if (l.pHead == p)
l.pHead = q;
}
}
int main()
{
DList L;
init(L);
int x,y,choice;
cout<<"MENU:";
cout<<"\n1. Create a DList";
cout<<"\n2. Print the DList";
cout<<"\n3. Insert a value at the front";
cout<<"\n4. Insert a value at the end";
cout<<"\n5. Insert a value after a given value (only for the first value found)";
cout<<"\n6. Insert a value before a given value (only for the first value found)";
cout<<"\n7. Insert a value after a given value (for all the same values)";
cout<<"\n8. Insert a value before a given value (for all the same values)";
cout<<"\n20. Exit"<<endl;
while(true)
{
cout<<"\n\t\tPLEASE SELECT YOUR CHOICE: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter your positive integers until you enter -1 to finish: ";
createList(L);
break;
case 2:
cout<<"\nYour current DList: ";
printList(L);
break;
case 3:
cout<<"\nEnter a number: ";
cin>>x;
addHead(L,x);
break;
case 4:
cout<<"\nEnter a number: ";
cin>>x;
addTail(L,x);
break;
case 5:
cout<<"\nEnter two numbers: ";
cin>>x>>y;
addAfter(L,x,y);
break;
case 6:
cout<<"\nEnter two numbers: ";
cin>>x>>y;
addBefore(L,x,y);
break;
case 20:
cout<<"\nGOOD BYE";
return 0;
}
}
return 0;
}
// Bai 2
#include <iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
typedef node* Tree;
node *getnode(int x){
node *temp = new node;
if (temp != NULL){
temp -> left = temp -> right = NULL;
temp -> data = x;
}
return temp;
}
void insertTree(Tree &T, int x){
if (T != NULL){
if(x < T->data) insertTree(T->left, x);
else if(x > T->data) insertTree(T->right, x);
}
else T = getnode(x);
}
void inputTree(Tree &T){
int n, x;
cin >> n;
for (int i = 0; i < n; i++){
cin >> x;
insertTree(T, x);
}
}
void NLR(Tree T){
if(T != NULL){
cout << T->data << " ";
NLR(T->left);
NLR(T->right);
}
}
void LRN(Tree T){
if(T != NULL){
LRN(T->left);
LRN(T->right);
cout << T->data << " ";
}
}
void LNR(Tree T){
if(T != NULL){
LNR(T->left);
cout << T->data << " ";
LNR(T->right);
}
}
void listLeafs(Tree T){
if(T != NULL){
if (T->left == NULL && T->right == NULL) cout << T->data << " ";
else {
listLeafs(T->left);
listLeafs(T->right);
}
}
}
void listInternalNodes(Tree T, int flag){
if(T != NULL){
if (flag == 0) flag = 1;
else if ((T->left || T->right) && flag == 1) cout << T->data << " ";
listInternalNodes(T->left, flag);
listInternalNodes(T->right, flag);
}
}
void listNodesWithOneChild(Tree T){
if(T != NULL){
if (T->left != NULL && T->right == NULL) cout << T->data << " ";
else if (T->left == NULL && T->right != NULL) cout << T->data << " ";
listNodesWithOneChild(T->left);
listNodesWithOneChild(T->right);
}
}
void listNodesWithTwoChildren(Tree T){
if(T != NULL){
if (T->left && T->right) cout << T->data << " ";
listNodesWithTwoChildren(T->left);
listNodesWithTwoChildren(T->right);
}
}
int main()
{
Tree T = NULL;
inputTree(T);
cout<<"\nNLR: "; NLR(T);
cout<<"\nLRN: "; LRN(T);
cout<<"\nLNR: "; LNR(T);
cout<<"\nLeaf nodes: "; listLeafs(T);
cout<<"\nInternal nodes: "; listInternalNodes(T,0);
cout<<"\nNodes with one child: "; listNodesWithOneChild(T);
cout<<"\nNodes with two children: "; listNodesWithTwoChildren(T);
return 0;
}
// Bai 3
#include <iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
typedef node* Tree;
node *getnode(int x){
node *temp = new node;
if (temp != NULL){
temp -> left = temp -> right = NULL;
temp -> data = x;
}
return temp;
}
void insertTree(Tree &T, int x){
if (T != NULL){
if(x < T->data) insertTree(T->left, x);
else if(x > T->data) insertTree(T->right, x);
}
else T = getnode(x);
}
void inputTree(Tree &T){
int n, x;
cin >> n;
for (int i = 0; i < n; i++){
cin >> x;
insertTree(T, x);
}
}
int countNodes(Tree T){
if(T == NULL)
return 0;
else return 1 + countNodes(T->left) + countNodes(T->right);
}
int countLeafs(Tree T){
if(T == NULL)
return 0;
else if(T->left == NULL && T->right == NULL)
return 1;
else
return countLeafs(T->left) + countLeafs(T->right);
}
int countInternalNodes(Tree T){
if(T == NULL || (T->left == NULL && T->right == NULL))
return 0;
else if(T->left == NULL || T->right == NULL)
return countInternalNodes(T->left) + countInternalNodes(T->right);
else
return 1 + countInternalNodes(T->left) + countInternalNodes(T->right);
}
int countOneChild(Tree T){
if(T == NULL)
return 0;
else if(T->left == NULL && T->right != NULL)
return 1 + countOneChild(T->right);
else if(T->left != NULL && T->right == NULL)
return 1 + countOneChild(T->left);
else
return countOneChild(T->left) + countOneChild(T->right);
}
int countTwoChildren(Tree T){
if(T == NULL)
return 0;
else if(T->left != NULL && T->right != NULL)
return 1 + countTwoChildren(T->left) + countTwoChildren(T->right);
else
return countTwoChildren(T->left) + countTwoChildren(T->right);
}
int countLess(Tree T, int x){
if(T == NULL)
return 0;
else if(T->data < x)
return 1 + countLess(T->left, x) + countLess(T->right, x);
else
return countLess(T->left, x);
}
int countBetweenValues(Tree T, int x, int y){
if(T == NULL)
return 0;
else if(T->data > x && T->data < y)
return 1 + countBetweenValues(T->left, x, y) + countBetweenValues(T->right, x, y);
else if(T->data < x)
return countBetweenValues(T->right, x, y);
else
return countBetweenValues(T->left, x, y);
}
int main()
{
Tree T = NULL;
inputTree(T);
cout<<"Number of nodes: " << countNodes(T)<<endl;
cout<<"Number of leaf nodes: " << countLeafs(T)<<endl;
cout<<"Number of internal nodes: "<< countInternalNodes(T)<<endl;
cout<<"Number of nodes with one child: "<< countOneChild(T)<<endl;
cout<<"Number of nodes with two children: "<< countTwoChildren(T)<<endl;
int x;cout<<"Enter x: ";cin>>x;
cout<<"\nNumber of nodes less than "<<x<<": "<< countLess(T,x)<<endl;
int y; cout<<"Enter x,y: ";cin>>x>>y;
cout<<"\nNumber of nodes greater than "<<x<<" and less than "<<y<<": "<< countBetweenValues(T,x,y)<<endl;
return 0;
}Editor is loading...