/*
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
typedef Node* node;
// print tree
void printTreeNLR(node t) {
if (t != NULL) {
cout << t->data << ' ';
printTreeNLR(t->left);
printTreeNLR(t->right);
}
}
void printTreeLNR(node t) {
if (t != NULL) {
printTreeLNR(t->left);
cout << t->data << " ";
printTreeLNR(t->right);
}
}
void printTreeLRN(node t) {
if (t != NULL) {
printTreeLRN(t->left);
printTreeLRN(t->right);
cout << t->data << " ";
}
}
node createNode(int data) {
node newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert node
void insertNode(node& t, int data) {
if (t == NULL) {
t = createNode(data);
}
else {
if (t->data < data) {
insertNode(t->right, data);
}
else if (t->data > data) {
insertNode(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));
}
}
// Calculate the sum of numbers are greater than x
int sumofGreaterX(node t, int x) {
int data = 0;
if (t == NULL) {
return 0;
}
if (t->data > x) {
data += t->data;
}
data += sumofGreaterX(t->left, x);
data += sumofGreaterX(t->right, x);
return data;
}
// Find x without using Recursive
node findXwithoutRecur(node tree, int value) {
while (true) {
if (tree == NULL) {
return NULL;
}
if (tree->data == value) {
return tree;
}
if (tree->data > value) {
tree = tree->left;
}
else {
tree = tree->right;
}
}
}
// Find x by using Recursive
node findXbyRecur(node tree, int value) {
if (tree == NULL) {
return NULL;
}
if (tree->data == value) {
return tree;
}
if (tree->data > value) {
return findXbyRecur(tree->left, value);
}
else {
return findXbyRecur(tree->right, value);
}
}
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 insertAtNode(node t, int nodes, int value) {
if (t != NULL) {
if (t->data < nodes) {
insertAtNode(t->right, nodes, value);
}
else if (t->data > nodes) {
insertAtNode(t->left, nodes, value);
}
else {
node cur = t;
node add = createNode(value);
if (cur->data < nodes && cur->right->data > nodes) {
add->right = cur->right;
cur->right = add;
}
else if (cur->data > nodes && cur->left->data < nodes) {
add->left = cur->left;
cur->left = add;
}
else {
insertNode(t, value);
}
}
}
}
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();
}
}
}
int sonutla(node t) {
int n = 0;
if(t==NULL) {
return 0;
}
if (t->left == NULL && t->right == NULL) {
return 1;
}
n += sonutla(t->left);
n+=sonutla(t->right);
return n;
}
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;
}
}
void menu(node& t) {
while (1) {
cout << "=========== Your option =============" << endl;
cout << "1. " << endl;
cout << "2. " << endl;
cout << "3. " << endl;
cout << "4. " << endl;
cout << "5. " << endl;
cout << "9. Thoat" << endl;
cout << "=============== End =================" << endl;
cout << "Lua chon cua ban la: ";
int choose;
do {
cin >> choose;
if (choose < 1 || choose>9) {
cout << "Nhap lai: ";
}
} while ((choose < 1 || choose>9));
switch (choose)
{
case 1: {
break;
}
case 2: {
break;
}
case 3: {
break;
}
case 9: {
system("cls");
return;
}
}
}
}
int main() {
node t = NULL;
menu(t);
}
*/