mot_so_thao_tac_vs_tree.cpp

/**
 * Data structure and algorithm: Binary Tree
 * Some action with Binary Tree
 *
 * Author: LvDuit (lvduit08 at gmail.com)
 * Date: 16/06/2014
 */

#include <stdio.h>
#include <math.h>

#define max(a, b) (a > b ? a : b)
//#define max(a, b) ((a>b) * a + (a<=b) * b);


typedef struct _node {
	struct _node * left, * right;
	int value;
} node;

// Tạo node mới với giá trị x
node * createNode(int x) {
	node * newNode = new node;
	if (newNode == NULL) 
		return NULL;

	newNode->left = newNode->right = NULL;
	newNode->value = x;

	return newNode;
}

// Thêm nút
void addNode(node * & root, node * newNode) {
	if (root == NULL) {
		root = newNode;
		return;	
	}

	if (root->value > newNode->value)
		return addNode(root->left, newNode);
	else if (root->value < newNode->value)
		return addNode(root->right, newNode);
	else
		return;
}

// Thêm 1 giá trị vào trong cây, đầu tiên từ giá trị x tạo ra node mới, sao đó add vào cây
void addNode(node * & root, int x) {
	return addNode(root, createNode(x));
}

// In cây LNR
void printTree(node * root) {
	if (root != NULL) {
		printTree(root->left);
		printf("%-3d", root->value);
		printTree(root->right);		
	}

	return;	
}

// Đếm nút có đúng 2 con
int counterNodeHave2Child(node * root) {
	if (root == NULL) 
		return 0;
	return ((root->left != NULL && root->right != NULL) ? 1 : 0) + 
		 counterNodeHave2Child(root->left) + counterNodeHave2Child(root->right);
}

// Đếm nút có đúng 1 con
int counterNodeHave1Child(node * root) {
	if (root == NULL) 
		return 0;
	return ((root->left != NULL && root->right == NULL) || (root->left == NULL && root->right != NULL) ? 1 : 0) + 
		 counterNodeHave1Child(root->left) + counterNodeHave1Child(root->right);
}

// Kiểm tra có phải là số hoàn thiện hay không
bool isPerfectNumber(int x) {
	int s = 0;
	for (int i = 1; i < x; i++) {
		if (x % i == 0) s++;
	}

	if (s == x) return true;

	return false;
}

// Đếm số node trong cây là node đó phải là số hoàn thiện
int counterNodePerfectNumber(node * root) {
	if (root == NULL) 
		return 0;
	return (isPerfectNumber(root->value) ? 1 : 0) + 
		 counterNodePerfectNumber(root->left) + counterNodePerfectNumber(root->right);
}

// Xuất các node ở tầng thứ k
void printNodeAtLevel(node * root, int k) {
	if (root != NULL) {
		printNodeAtLevel(root->left, k - 1);
		if (k == 0) printf("%-3d", root->value);
		printNodeAtLevel(root->right, k - 1);
	}
}

// Đếm các nút ở tầng thứ k
int counterNodeAtLevel(node * root, int k) {
	if (root == NULL) 
		return 0;

	return ((k == 0) ? 1 : 0) 
			+ counterNodeAtLevel(root->left, k - 1) // đếm bên trái
			+ counterNodeAtLevel(root->right, k - 1); // bên phải
}

// Đếm các nút thấp hơn tầng thứ k
int counterNodeAtLevelLower(node * root, int k) {
	int c = 0;
	for (int i = 0; i < k; i++) {
		c += counterNodeAtLevel(root, i);
	}

	return c;
}

// Tìm chiều cao của cây
int getTreeHeight(node * root) {
	if (root == NULL) return 0;

	return 1 + max(getTreeHeight(root->left), getTreeHeight(root->right));	
}

// Đếm số nút lá trong cây
int counterNodeLeaf(node * root) {
	if (root == NULL) return 0;

	return ((root->left == NULL && root->right == NULL) ? 1 : 0) 
		+ counterNodeLeaf(root->left) // đếm bên trái 
		+ counterNodeLeaf(root->right); // đếm bên phải
}

// Đếm số nút là số chẵn trong cây
int counterNodeEven(node * root) {
	if (root == NULL) 
		return 0;
	return ((root->value % 2 == 0) ? 1 : 0) + 
		 counterNodeEven(root->left) + counterNodeEven(root->right);
}

// Đếm số nút lá là số chẵn
int counterNodeLeafEven(node * root) {
	if (root == NULL) 
		return 0;
	return ((root->left == NULL && root->right == NULL && root->value % 2 == 0) ? 1 : 0) + 
		 counterNodeLeafEven(root->left) + counterNodeLeafEven(root->right);	
}

// Kiểm tra số nguyên tố
bool soNguyenTo(int n) {
    if (n <= 1) 
		return false; 
    
	for (int i=2; i<n; i++) 
        if (n%i == 0) 
            return false; 
    
	return true;
}

// Kiểm tra số chính phương
bool soChinhPhuong(int n) { 
    if (n <= 0) 
		return false; 
    
	int s = sqrt((double)n); 
    if (s*s == n) 
		return true; 
    
	return false; 
}

// Xóa 1 node trong cây
//    * Node có 1 con
//    * Node có 2 con

// Xóa toàn bộ cây
void deleteTree(node * & root) {
	if (root == NULL) return;

	deleteTree(root->left);
	deleteTree(root->right);
	delete root;
	root = NULL;
}

int main() {
	node * root = NULL;

	addNode(root, 5);
	addNode(root, 1);
	addNode(root, 9);
	addNode(root, 4);
	addNode(root, 9);
	addNode(root, 3);
	addNode(root, 8);
	addNode(root, 11);
	addNode(root, 16);

	/*
     	==> Tree:
	               5          ---------- level 0
				 /   \                  
				1     9                  level 1
			     \   /  \              
			      4  8   11              level 2
				 /        \
				3         16    -------- level 3

	*/


	printTree(root);
	
	printf("\n\n * %d nut co dung 1 nut con. ", counterNodeHave1Child(root));
	printf("\n * %d nut co dung 2 nut con. ", counterNodeHave2Child(root));
	printf("\n * %d nut la so chan. ", counterNodeEven(root));
	printf("\n * So nut la' trong cay la: %d", counterNodeLeaf(root));
	printf("\n * %d nu't la` nu't la' va` la` so^' chan~. ", counterNodeLeafEven(root));
	printf("\n * %d nu't la` so^' hoan` thie^n. ", counterNodePerfectNumber(root));
	printf("\n * Chieu cao cua cay = %d ", getTreeHeight(root));
	printf("\n * So nut o tang thu 2 = %d ", counterNodeAtLevel(root, 2));
	printf("\n * Tong so nut nam duoi tang 3 = %d ", counterNodeAtLevelLower(root, 3));
	
	printf("\n * Duyet cay theo chieu ngang: \n");
	for (int i = 0; i < getTreeHeight(root); i++) {
		printNodeAtLevel(root, i);
		printf("\n");
	}

	// Delete tree
	deleteTree(root);
	
	return 0;
}