_tree_full.cpp

#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;

const int N = 5;
const int MIN = 1;
const int MAX = 50;

typedef struct _tnode {
	int value;
	struct _tnode * left;
	struct _tnode * right;
} NODE;

typedef NODE * TREE;
TREE ROOT;

	inline bool addNode(TREE & T, int x);
	inline void printLNR(TREE T);
	inline int getRand();// { /* return rand() % (MAX - MIN + 1) + MIN; */ return random_shuffle(); }
	inline NODE * createNode(int x);
	inline bool deleteNode(TREE & T, int x);\
	inline void swapDeleteNode(NODE * & currentNode, NODE * & rightNode);
	inline int countNode(TREE T); // couter node 
	inline int coutNodeLeaf(TREE T);
	inline int coutNodeHaveOneChild(TREE T);
	inline bool haveOneChild(TREE T);
	inline bool isNodeLeaf(TREE T);
	inline int maxNodeLeaf(TREE T);
	inline int getHeight(TREE T);
	inline int getLevel(TREE T, int level = 0);
	inline void printNodeAtLevel(TREE T, int level);
	inline int countNodeAtLevel(TREE T, int level);
	inline void deleteTree(TREE & T);
	inline TREE copyTree(TREE T);
	inline int max(int a, int b) { return a > b ? a : b; }
	inline void printNodeWithHeightOfLeftEqualRight(TREE T);

// ------------------------
int main() {

	addNode(ROOT, 5);
	addNode(ROOT, 4);
	addNode(ROOT, 8);
	addNode(ROOT, 5);
	addNode(ROOT, 12);
	addNode(ROOT, 1);
	addNode(ROOT, 3);
	addNode(ROOT, 9);
	addNode(ROOT, 16);
	addNode(ROOT, 7);
	addNode(ROOT, 2);

	/*
	
	printLNR(ROOT);
	cout << getLevel(ROOT); // tìm mức tối đa của cây
	printNodeAtLevel(ROOT, 3); // in mức ở mức thứ 3
	cout << countNodeAtLevel(ROOT, 2); // in số mức ở cây thứ 3
	
	*/

	/*
	// Duyệt cây theo chiều ngang
	for (int i = 0; i <= getLevel(ROOT); i++) {
		printNodeAtLevel(ROOT, i);
		cout << endl;
	}
	*/

	/* // Copy cây, xong xóa cây gốc
	printLNR(ROOT); cout << endl;
	TREE _ROOT = copyTree(ROOT);
	deleteTree(ROOT);
	printLNR(_ROOT);cout << endl;
	*/

	//printNodeWithHeightOfLeftEqualRight(ROOT);

	/*
	printLNR(ROOT);cout << endl;
	deleteNode(ROOT, 5); // xóa node có giá trị 5
	printLNR(ROOT);cout << endl;
	*/

	return 0;
}

// -----------------------
inline bool addNode(TREE & T, int x) {
	if (T == NULL) {
		T = new NODE;
		if (T == NULL) return false;

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

		return true;
	}

	if (T->value > x) return addNode(T->left, x);
	else if (T->value < x) return addNode(T->right, x);
	else return false;
}

inline NODE * createNode(int x) {
	NODE * newNode = new NODE;
	newNode->value = x;
	newNode->left = newNode->right = NULL;

	return newNode;
}

inline bool deleteNode(TREE & T, int x) {
	if (T == NULL) return false;
	if (x < T->value) return deleteNode(T->left, x);
	if (x > T->value) return deleteNode(T->right, x);

	NODE * currentNode = T;
	if (T->left == 0) T = T->right;
	else if (T->right == 0) T = T->left;
	else {
		swapDeleteNode(currentNode, T->right);
	}
	delete currentNode;
}

inline void swapDeleteNode(NODE * & currentNode, NODE * & rightNode) {
	if (rightNode->left) return swapDeleteNode(currentNode, rightNode->left);
	
	currentNode->value = rightNode->value;
	currentNode = rightNode;
	rightNode = rightNode->right;
}

inline void printLNR(TREE T) {
	if (T == NULL) return;

	printLNR(T->left);
	cout << T->value << " ";
	printLNR(T->right);
}

inline int getRand() { return rand() % (MAX - MIN + 1) + MIN;}

inline int countNode(TREE T) {
	if (T == NULL) return 0;

	return countNode(T->left) + countNode(T->right) + 1;
}

inline int coutNodeLeaf(TREE T) {
	if (T == NULL) return 0;

	return countNode(T->left)
		+ countNode(T->right)
		+ (T->left == NULL && T->right == NULL ? 1 : 0);
}

inline int coutNodeHaveOneChild(TREE T) {
	if (T == NULL) return 0;

	return countNode(T->left)
		+ countNode(T->right)
		+ (haveOneChild(T) ? 1 : 0);
}

// have one child
inline bool haveOneChild(TREE T) {
	return (T->left == NULL && T->right != NULL)
		|| (T->left != NULL && T->right == NULL);
}

inline bool isNodeLeaf(TREE T) {
	if (T->left != NULL || T->right != NULL) return false;

	return true;
}

inline int maxNodeLeaf(TREE T) {
	if (T == NULL) return -1;
	return max(
		max(
			maxNodeLeaf(T->left),
			maxNodeLeaf(T->right)
		),
		(isNodeLeaf(T) ? T->value : -1)
	);
}

inline int getHeight(TREE T) {
	if (T == NULL) return 0;

	return 1 + max(getHeight(T->left), getHeight(T->right));
}

inline int getLevel(TREE T, int level) {
	if (T->left == NULL && T->right == NULL) return level;

	return max(T->left != NULL ? getLevel(T->left, level + 1) : level,
		T->right ? getLevel(T->right, level + 1) : level);
}

inline void printNodeAtLevel(TREE T, int level) {
	if (T == NULL) return;
	if (level == 0) {
		cout << T->value << " ";
		return;
	}

	printNodeAtLevel(T->left, level - 1);
	printNodeAtLevel(T->right, level - 1);
}

inline int countNodeAtLevel(TREE T, int level) {
	if (T == NULL) return 0;

	int a = 0;
	if (level == 0) a = 1;

	a += countNodeAtLevel(T->left, level - 1)
		+ countNodeAtLevel(T->right, level - 1);

	return a;
}

inline void deleteTree(TREE & T) {
	if (T != NULL) {
		deleteTree(T->left);
		deleteTree(T->right);
		delete T;
		T = NULL;
	}
}

inline TREE copyTree(TREE T) {
	if (T == NULL) return NULL;

	NODE * newNode = createNode(T->value);
	newNode->left = copyTree(T->left);
	newNode->right = copyTree(T->right);

	return newNode;
}

inline void printNodeWithHeightOfLeftEqualRight(TREE T) {
	if (T == NULL) return;

	printNodeWithHeightOfLeftEqualRight(T->left);
	if (getHeight(T->left) > 0 && getHeight(T->left) == getHeight(T->right)) {
		cout << T->value << " ";
	}
	printNodeWithHeightOfLeftEqualRight(T->right);
}