This is my first post here
Thanks for the solution though

This is my first post here
Thanks for the solution though

naeem

Witam.
Podłącze się, nie będę rozpoczynał nowego tematu.
Może ktoś sprawdzić czego ten kod nie przechodzi?
[bbone=cpp,3126]

include

include

typedef struct drzewo BST;
struct drzewo
{
int key;
BST *left;
BST *right;
BST *p;
};

BST *tree=NULL;

void inorder(BST *root)
{
if(!root)
return;
if(root->left)
inorder(root->left);
printf("%d ",root->key);
if(root->right)
inorder(root->right);
}

void preorder(BST *root)
{
if(root != NULL)
{
printf("%d ",root->key);
preorder(root->left);
preorder(root->right);
}
}

void postorder(BST *root)
{
if(root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ",root->key);
}
}

BST *search(BST *root,int val)
{
if((root == NULL) || (val == root->key))
return root;
if(val < root->key)
return search(root->left,val);
else
return search(root->right,val);
return root;
}

BST *min(BST *root)
{
while(root->left != NULL)
root=root->left;
return root;
}

BST *max(BST *root)
{
while(root->right != NULL)
root=root->right;
return root;
}

BST *nast(BST *root)
{
BST *y=root;
if(root == NULL)
return y;
if(root->right != NULL)
return min(root->right);
y=root->p;
while(y != NULL && root == y->right)
{
root=y;
y=y->p;
}
return y;
}

BST *pop(BST *root)
{
BST *y=root;
if(root == NULL)
return y;
if(root->left != NULL)
return max(root->left);
y=root->p;
while(y != NULL && root == y->left)
{
root=y;
y=y->p;
}
return y;
}

BST *del(BST *root,int val)
{
BST *x=root;
BST *y=(BST *)malloc(sizeof(BST));
BST *del=search(root,val);

if(del == NULL)
	return y;

if(del->left == NULL || del->right == NULL)
	y=del;
else
	y=nast(del);

if(y->left != NULL)
	x=y->left;
else
	x=y->right;

if(x != NULL)
	x->p=y->p;

if(y->p == NULL)
	root=x;
else
	if(y == y->p->left)
		y->p->left=x;
	else
		y->p->right=x;

if(y != del)
	del->key=y->key;
return y;

}

BST *add(BST *root,int val)
{
BST *x=root;
BST *nowe=(BST *)malloc(sizeof(BST));
nowe->key=val;
nowe->p=nowe->left=nowe->right=NULL;
BST *y=NULL;
while(x != NULL)
{
y=x;
if(val < x->key)
x=x->left;
else
x=x->right;
}
nowe->p=y;
if(y == NULL)
root=nowe;
else
{
if(nowe->key < y->key)
y->left=nowe;
else
y->right=nowe;
}
return root;
}

void delete(BST *root)
{
}

int main(void)
{
BST *p;
int i,j,z,x,a;
char c;
scanf("%d",&i);
z=1;
while(i--)
{
scanf("%d%*c",&j);
printf("test %d\n",z++);
for(x=0;x {
scanf("%c %d%*c",&c,&a);
if(c == 'I')
tree=add(tree,a);
else
if(c == 'D')
del(tree,a);
else
if(c == 'S')
{
p=search(tree,a);
if(p == NULL)
printf("-\n");
else
printf("%d\n",p->key);
}
else
if(c == 'X')
{
switch(a)
{
case 0:
p=min(tree);
printf("%d\n",p->key);
break;
case 1:
p=max(tree);
printf("%d\n",p->key);
break;
}
}
else
if(c == 'N')
{
p=nast(search(tree,a));
if(p == NULL)
printf("-\n");
else
printf("%d\n",p->key);
}
else
if(c == 'P')
{
p=pop(search(tree,a));
if(p == NULL)
printf("-\n");
else
printf("%d\n",p->key);
}
else
if(c == 'R')
{
switch(a)
{
case 0:
inorder(tree);
putchar('\n');
break;
case 1:
preorder(tree);
putchar('\n');
break;
case 2:
postorder(tree);
putchar('\n');
break;
}
}
}
tree=NULL;
}
return 0;
}
[/bbone]
Testy podane w zadaniu mi przechodzi może ktoś zerknąć?
Dzięki.

Witam,
zupełnie nie rozumiem, czy to jest tak trudno układając zadanie wystarczająco je doprecyzować, aby nie było żadnych wątpliwości? Naprawdę nie widzę sensu w zgadywaniu co autor mógł mieć na myśli, bo chyba nie o to w tym wszystkim chodzi...

Stąd kilka moich pytań:
- co trzeba wypisać dla zapytań min/max oraz zapytań wypisania drzewa pre/in/postorder, gdy drzewo jest puste?
- czy drzewo może trzymać duplikaty? czy może kolejne próby dodania mam odrzucić?
- jeżeli może trzymać, to czy powinienem je trzymać w tym samym węźle, czy też na lewo/prawo względem już istniejącego węzła o tej wartości?
- czy przy próbie usunięcia nieistniejącego elementu mam wypisać "-"? jeżeli duplikaty są dozwolone, to który z nich mam usunąć?

Z góry dzięki za pomoc

Mój test:
IN:

1
60
I 15
I 7
I 31
I 3
I 12
I 20
I 1
I 4
I 8
I 14
I 16
I 25
I 6
I 13
I 22
I 27
I 5
I 26
I 28
I 29
R 0
R 1
R 2
S 5
S 300
S 15
S 25
P 15
P 2
P 5
P 29
P 28
P 3
P 12
P 1
N 31
N 20
N 12
D 15
R 1
R 2
R 0
X 0
X 1
D 20
D 29
D 4
R 0
R 1
R 2
X 0
X 1
D 3
S 3
S 14
S 15
N 12
P 5
X 0
R 2

OUT:

test 1
1 3 4 5 6 7 8 12 13 14 15 16 20 22 25 26 27 28 29 31 
15 7 3 1 4 6 5 12 8 14 13 31 20 16 25 22 27 26 28 29 
1 5 6 4 3 8 13 14 12 7 16 22 26 29 28 27 25 20 31 15 
5
-
15
25
14
-
4
28
27
1
8
-
-
22
13
14 7 3 1 4 6 5 12 8 13 31 20 16 25 22 27 26 28 29 
1 5 6 4 3 8 13 12 7 16 22 26 29 28 27 25 20 31 14 
1 3 4 5 6 7 8 12 13 14 16 20 22 25 26 27 28 29 31 
1
31
1 3 5 6 7 8 12 13 14 16 22 25 26 27 28 31 
14 7 3 1 6 5 12 8 13 31 16 25 22 27 26 28 
1 5 6 3 8 13 12 7 22 26 28 27 25 16 31 14 
1
31
-
14
-
13
1
1
5 6 1 8 13 12 7 22 26 28 27 25 16 31 14