Untitled

#include <iostream>  
#include <queue>
using namespace std;

struct Node {
	int data;
	Node* left;
	Node* right;
};
typedef Node* node; 

node createNode(int data) {
	node newNode = new Node;
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

// Insert node
void insertNodes(node& t, int data) {
	if (t == NULL) {
		t = createNode(data);
	}
	else {
		if (t->data < data) {
			insertNodes(t->right, data);
		}
		else if (t->data > data) {
			insertNodes(t->left, data);
		}
		else {
			return;
		}
	}
}

// Calculate the high of tree
int heightTree(node t) {
	if (t == NULL) {
		return -1;
	}
	else {
		return 1 + max(heightTree(t->left), heightTree(t->right));
	}
}

void Themang(node& tree, node y) {
	if (y->left != NULL) {
		return Themang(tree, y->left);
	}
	else {
		tree->data = y->data;
		tree = y;
		y = y->right;
	}
}
void DeleteBSTreeNode(node& t, int value) {
	if (t != NULL) {
		if (t->data > value) {
			DeleteBSTreeNode(t->left, value);
		}
		else if (t->data < value) {
			DeleteBSTreeNode(t->right, value);
		}
		else {
			node cur_node = t;
			// Xoa mot nut chi co con ben trai hoac con ben phai hoac khong co con nao
			if (t->left == NULL) {
				t = t->right;
			}
			else if (t->right == NULL) {
				t = t->left;
			}
			else { // Xoa mot nut co ca hai con
				Themang(t, t->right);
			}
			delete cur_node;
			return;
		}

	}
	else {
		return;
	}
}

void xuatCayTheoMuc(node t)
{
	queue<node> nodes, nodes2;
	nodes.push(t);
	while (1) {
		while (!nodes.empty()) {
			node x = nodes.front();
			// In ra cac node trong mot muc
			cout << x->data << "  ";
			// Insert cac node cua muc tiep theo vao mang tam, neu co
			if (x->left) {
				nodes2.push(x->left);
			}
			if (x->right) {
				nodes2.push(x->right);
			}
			nodes.pop();
		}
		cout << endl;
		// Kiem tra xem muc tiep theo co node nao khong. Neu khong thi ket thuc
		if (nodes2.size() == 0) break;
		// Insert cac node o muc tiep theo tu mang tam vao mang chinh
		while (!nodes2.empty()) {
			nodes.push(nodes2.front());
			nodes2.pop();
		}
	}
}
void RemoveTree(node& t) {
	//neu van ton tai node goc
	if (t) {
		//de quy sang nhanh trai
		RemoveTree(t->left);
		//de quy sang nhanh phai
		RemoveTree(t->right);
		//xoa node goc
		delete t;
	}
}

 
bool checkAVL(node t) {
	bool check;
	if (t == NULL) check= true; 
	else if (abs(heightTree(t->left) - heightTree(t->right)) > 1) {
		return false;
	} 
	else if(t!= NULL){
		check = checkAVL(t->left) && checkAVL(t->right);
	}
	return check;
}

int main() {
	node t = NULL;
	cout << "Nhap so luong phan tu: ";
	int n; cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		cout << "Nhap gia tri phan tu thu " << i + 1 << " : ";
		cin >> arr[i];
		insertNodes(t, arr[i]);
	}
	cout << "=============== Danh sach cay sau khi nhap la: " << endl;
	xuatCayTheoMuc(t);
	cout << "Do cao cua cay: " << heightTree(t->left) << endl;
	cout << "Do cao cua cay: " << heightTree(t->right) << endl;
	if (checkAVL(t)) {
		cout << "Day la cay AVL" << endl;
	}
	else {
		cout << "Day khong phai la cay AVL" << endl;
	}
}