Добрый день. Добрые форумчане помогите переписать бинарное дерево.
Есть программа для рабоыт с деревом:
| Код |
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct searchtree
{
int element;
struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef int ElementType;
node insert(ElementType, node);
node delet(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);
void main()
{
int ch;
ElementType a;
node temp;
makeempty();
while(1)
{
printf("\n1. Insert\n2. Delete\n3. Find min\n4. Find max\n5. Find\n6. Display\n7. Exit\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter an element : ");
scanf("%d", &a);
root = insert(a, root);
break;
case 2:
printf("\nEnter the element to delete : ");
scanf("%d",&a);
root = delet(a, root);
break;
case 3:
printf("\nEnter the element to search : ");
scanf("%d",&a);
temp = find(a, root);
if (temp != NULL)
printf("Element found");
else
printf("Element not found");
break;
case 4:
temp = findmin(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMinimum element : %d", temp->element);
break;
case 5:
temp = findmax(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMaximum element : %d", temp->element);
break;
case 6:
if(root==NULL)
printf("\nEmpty tree");
else
display(root, 1);
break;
case 7:
exit(0);
default:
printf("Invalid Choice");
}
}
}
node insert(ElementType x,node t)
{
if(t==NULL)
{
t = (node)malloc(sizeof(node));
t->element = x;
t->left = t->right = NULL;
}
else
{
if(x < t->element)
t->left = insert(x, t->left);
else if(x > t->element)
t->right = insert(x, t->right);
}
return t;
}
node delet(ElementType x,node t)
{
node temp;
if(t == NULL)
printf("\nElement not found");
else
{
if(x < t->element)
t->left = delet(x, t->left);
else if(x > t->element)
t->right = delet(x, t->right);
else
{
if(t->left && t->right)
{
temp = findmin(t->right);
t->element = temp->element;
t->right = delet(t->element,t->right);
}
else if(t->left == NULL)
t=t->right;
else
t=t->left;
}
}
return t;
}
void makeempty()
{
root = NULL;
}
node findmin(node temp)
{
if(temp == NULL || temp->left == NULL)
return temp;
return findmin(temp->left);
}
node findmax(node temp)
{
if(temp==NULL || temp->right==NULL)
return temp;
return findmin(temp->right);
}
node find(ElementType x, node t)
{
if(t==NULL) return NULL;
if(x<t->element) return find(x,t->left);
if(x>t->element) return find(x,t->right);
return t;
}
void display(node t,int level)
{
int i;
if(t)
{
display(t->right, level+1);
printf(“\n”);
for(i=0;i<level;i++)
printf(" ");
printf("%d", t->element);
display(t->left, level+1);
}
}
|
Отлично работает с цифрами. Но мне необходимо такое же дерево, но для работы со словами.
Как можно переписать эту программу для этих потребностей?
вот что в данный момент есть, но не работает :(
| Код |
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct searchtree
{
char *element;
struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef char *ElementType;
node insert(ElementType, node);
node delet(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);
void main()
{
int ch;
ElementType a;
node temp;
makeempty();
while(1)
{
printf("\n1. Insert\n2. Delete\n3. Find\n4. Find min\n5. Find max\n6. Display\n7. Exit\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter an element : ");
scanf("%s", a);
root = insert(a, root);
break;
case 2:
printf("\nEnter the element to delete : ");
scanf("%s",a);
root = delet(a, root);
break;
case 3:
printf("\nEnter the element to search : ");
scanf("%s",a);
temp = find(a, root);
if (temp != NULL)
printf("Element found");
else
printf("Element not found");
break;
case 4:
temp = findmin(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMinimum element : %s", temp->element);
break;
case 5:
temp = findmax(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMaximum element : %s", temp->element);
break;
case 6:
if(root==NULL)
printf("\nEmpty tree");
else
display(root, 1);
break;
case 7:
exit(0);
default:
printf("Invalid Choice");
}
}
}
node insert(ElementType x,node t)
{
if(t==NULL)
{
t = (node)malloc(sizeof(node));
t->element = x;
t->left = t->right = NULL;
}
else
{
if(strcmp(x,t->element)<0)
t->left = insert(x, t->left);
else if(strcmp(x,t->element)>0)
t->right = insert(x, t->right);
}
return t;
}
node delet(ElementType x,node t)
{
node temp;
if(t == NULL)
printf("\nElement not found");
else
{
if(strcmp(x,t->element)<0)
t->left = delet(x, t->left);
else if(strcmp(x,t->element)>0)
t->right = delet(x, t->right);
else
{
if(t->left && t->right)
{
temp = findmin(t->right);
t->element = temp->element;
t->right = delet(t->element,t->right);
}
else if(t->left == NULL)
t=t->right;
else
t=t->left;
}
}
return t;
}
void makeempty()
{
root = NULL;
}
node findmin(node temp)
{
if(temp == NULL || temp->left == NULL)
return temp;
return findmin(temp->left);
}
node findmax(node temp)
{
if(temp==NULL || temp->right==NULL)
return temp;
return findmin(temp->right);
}
node find(ElementType x, node t)
{
if(t==NULL) return NULL;
if(strcmp(x,t->element)<0) return find(x,t->left);
if(strcmp(x,t->element)>0) return find(x,t->right);
return t;
}
void display(node t,int level)
{
int i;
if(t)
{
display(t->right, level+1);
printf("\n");
for(i=0;i<level;i++)
printf(" ");
printf("%s", t->element);
display(t->left, level+1);
}
}
|
|
)