#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct treeNod
{
char data;
struct treeNod *left;
struct treeNod *right;
} Node, treeNode;
treeNode* makeRootNode(char data, treeNode *leftNode, treeNode *rightNode)
{
treeNode *root = (treeNode*)malloc(sizeof(treeNode));
root->data = data;
root->left = leftNode;
root->right = rightNode;
return root;
}
/* 전위 , 중위, 후위 트리
void preorder(treeNode *root) //D-L-R
{
if(root)
{
printf("%c", root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(treeNode *root) // L-D-R
{
if(root)
{
inorder(root->left);
printf("%c", root->data);
inorder(root->right);
}
}
void postorder(treeNode *root) // L-R-D
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("%c", root->data);
}
}
*/
treeNode *searchBTS(treeNode *root, char a)
{
treeNode *p=root;
if(p==NULL)
{
return NULL;
}
// printf("%c ->",p->data);
if(a==p->data)
{
return p;
}
else if(a < p->data)
{
return searchBTS(p->left,a);
}
else
{
return searchBTS(p->right,a);
}
}
treeNode* insertNode(treeNode *p, char b)
{
treeNode *newNode = (treeNode*)malloc(sizeof(Node));
if(p==NULL)
{
newNode->data = b;
newNode->left= NULL;
newNode->right= NULL;
return newNode;
}
else if(b<p->data)
p->left = insertNode(p->left, b);
else if(b>p->data)
p->right = insertNode(p->right, b);
else
printf("already existed");
return p;
}
treeNode* MaxNode(treeNode *p)
{
while(p->right != NULL)
{
p=p->right;
}
return p;
}
treeNode* deleteNode(treeNode *root,char data)
{
treeNode *parent, *p, *q;
parent = p =root;
while((p!=NULL) && (p->data != data))
{
parent = p;
if(data < p->data)
p= p->left;
else
p= p->right;
}
if(p==NULL)
{
printf("tree is empty. \n");
return ;
}
//delete p is 단말노드이면
if(p->left==NULL && p->right==NULL)
{
if(parent->left == p)
parent->left = NULL;
else
parent->right = NULL;
free(p);
}
//자식1
else if(p->left==NULL || p->right==NULL)
{
if(p->left != NULL)
{
if(parent->left == p)
parent->left = p->left;
else
parent->right = p->left;
}
else
{
if(parent->left == p)
parent->left = p->right;
else
parent->right = p->right;
}
}
//자식2
// (p->left !=NULL) && (p->right != NULL)
else
{
q=MaxNode(p->left);
//printf("%c\n",q->data);
p->data = q->data;
deleteNode(p->left, p->data);
}
}
/*
void insertBST(treeNode* p, char b)
{
treeNode* q;
while(p!=NULL)
{
printf("%c ->",p->data);
q=p;
if(b < p->data)
{
p=p->left;
}
else if(b > p->data)
{
p=p->right;
}
}
treeNode *NewNode = (treeNode*)malloc(sizeof(treeNode));
NewNode->data = b;
NewNode->left = NULL;
NewNode->right = NULL;
//if(p==NULL)
//{
// p=NewNode;
//}
//else
if(b<q->data)
{
q->left=NewNode;
}
else
{
q->right=NewNode;
}
}
*/
void inorderprint(treeNode *root) // L-D-R
{
if(root)
{
inorderprint(root->left);
printf(" %c -", root->data);
inorderprint(root->right);
}
}
int main()
{
treeNode *n7=makeRootNode('G',NULL,NULL);
treeNode *n6=makeRootNode('E',NULL,NULL);
treeNode *n5=makeRootNode('C',NULL,NULL);
treeNode *n4=makeRootNode('A',NULL,NULL);
treeNode *n3=makeRootNode('F',n6,n7);
treeNode *n2=makeRootNode('B',n4,n5);
treeNode *n1=makeRootNode('D',n2,n3);
// printf("search A : ");
searchBTS(n1,'A');
// printf("\n");
printf(" tree : ");
inorderprint(n1);
printf("\n");
//insertNode(n1, '@');
//printf("\nafter : ");
//inorderprint(n1);
//printf("\n");
deleteNode(n1, 'B');
inorderprint(n1);
printf("\n");
/*
printf("\n preorder: \n");
preorder(n1);
printf("\n inorder: \n");
inorder(n1);
printf("\n postorder: \n");
postorder(n1);
*/
getchar();
}