typedef int E;
struct TreeNode {
E element;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct TreeNode *Node;
Node createNode(E element) {
Node node = malloc(sizeof(struct TreeNode));
if (node == NULL) return NULL;
node->left = node->right = NULL;
node->element = element;
return node;
}
void preOrder(Node root) {
if (root == NULL) return;
preOrder(root->left);
printf("%d ", root->element);
preOrder(root->right);
}
void insert(Node root, E element) {
while (root) {
if (root->element == element) return;
if (root->element > element) {
if (root->left)
root = root->left;
else {
Node node = createNode(element);
root->left = node;
return;
}
} else {
if (root->right)
root = root->right;
else {
Node node = createNode(element);
root->right = node;
return;
}
}
}
}
Node insert2(Node root, E element) {
if (root == NULL) return createNode(element);
if (root->element > element) {
if (root->left) insert2(root->left, element);
else
root->left = insert2(root->left, element);
} else if (root->element < element) {
if (root->right)
insert2(root->right, element);
else
root->right = insert2(root->right, element);
}
}
int find(Node root, E target) {
if (root == NULL) return -1;
if (root->element == target) return root->element;
if (root->element > target)
find(root->left, target);
else find(root->right, target);
}
Node findMax(Node root) {
if (root->right == NULL) return root;
findMax(root->right);
}
int delete(Node root, E element) {
if (root == NULL) return -1;
Node tmp;
if (root->element == element) {
if (root->right && root->left) {
tmp = findMax(root->left);
root->element = tmp->element;
if (tmp->left) {
tmp->element = tmp->left->element;
tmp->left = tmp->left->left;
free(tmp->left);
} else free(tmp);
} else if (root->right || root->left) {
if (root->right) tmp = root->right;
else tmp = root->left;
root->element = tmp->element;
root->right = tmp->right;
root->left = tmp->left;
}
} else {
free(root);
}
if (root->element > element)
delete(root->left, element);
else
delete(root->right, element);
}
int main() {
Node root = insert2(NULL, 18);
insert2(root, 10);
insert2(root, 20);
insert2(root, 7);
insert2(root, 5);
insert2(root, 22);
insert2(root, 9);
printf("%d ", find(root, 17));
printf("%d", find(root, 9));