# Tree

unknown
plain_text
a year ago
3.4 kB
4
Indexable
Never
```#include <iostream>
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);
cout << t->data << " ";
printTreeLRN(t->right);
}
}

// Insert node
node insertNode(node t, int data) {
if (t == NULL) {
node newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
else {
if (t->data < data) {
t->right = insertNode(t->right, data);
}
else if (t->data > data) {
t->left = insertNode(t->left, data);
}
else {
return t;
}
}
}

// 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;
if (t->left == NULL) {
t = t->right;
}
else if (t->right == NULL) {
t = t->left;
}
else {
Themang(t, t->right);
}
delete cur_node;
}

}
else {
return;
}
}
int main() {
int arr[] = { 5,1,8,12,7,3,4,9,5, 10 };
node t = NULL;
int slg = sizeof(arr) / sizeof(arr[0]);
cout << slg << endl;
for (int i = 0; i < slg; i++) {
t = insertNode(t, arr[i]);
}
cout << "Our tree: " << endl;
printTreeLNR(t);
cout << endl;
cout << "The height of tree: " << heightTree(t) << endl;
cout << "Tong gia tri lon hon 5: " << sumofGreaterX(t, 11) << endl;
node nodeX = findXwithoutRecur(t, 2);
if (nodeX != NULL) {
cout << "Tim thay node " << nodeX->data << " trong tree" << endl;
}
else {
cout << "Khong tim thay node " << endl;
}
nodeX = findXbyRecur(t, 12);
if (nodeX != NULL) {
cout << "Tim thay node " << nodeX->data << " trong tree" << endl;
}
else {
cout << "Khong tim thay node " << endl;
}
DeleteBSTreeNode(t, 12);
printTreeLNR(t);
}```