nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
28 kB
7
Indexable
Never
// 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;
}

nord vpnnord vpn
Ad