Home » » Tim Xoa 1 Nut Tren CNPTK

Tim Xoa 1 Nut Tren CNPTK

Written By 1 on Chủ Nhật, 13 tháng 5, 2012 | 23:27


// TmXoaNutCNP.cpp : Defines the entry point for the console application.
//C++ 2010

#include "stdafx.h"
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>

typedef struct node
{
int a;
struct node *left,*right;
}cay;

void duyetgiua(cay *root)
{
if(root!=NULL)
{
duyetgiua(root->left);
printf("%3d",root->a);
duyetgiua(root->right);
}
}
void duyetsau(cay *root)
{
if(root!=NULL)
{
duyetsau(root->left);
duyetsau(root->right);
printf("%3d",root->a);
}
}
void main()
{

cay *root,*temp,*temp1,*temp2;
int k,n,x;
root=NULL;

 //Them 1 nut//

printf("\n Tien hanh nhap du lieu cho cay:");
do
{
printf("\n Nhap X (Nhap -1 de ket thuc):");
scanf("%d",&x);
if(x==-1)
break;
temp=root;
k=0;
while(temp!=NULL)
{
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
else
{
k=1;
break;
}
}
if(k==1)
{
printf("\n Trung khoa va nhap lai!!!\n");
continue;
}
if(root==NULL)
{
root=new cay;
temp=root;
}
else
{
temp1=root;
k=1;
while(temp1!=NULL)
{
temp=temp1;
if(x<temp1->a)
temp1=temp1->left;
else if(x>temp1->a)
temp1=temp1->right;
}
if(x<temp->a)
{
temp->left=new cay;
temp=temp->left;
}
else
{
temp->right=new cay;
temp=temp->right;
}

}
temp->a=x;
temp->left=temp->right=NULL;
}
while(1);
printf("\n Duyet giua:\n");
duyetgiua(root);
printf("\n Duyet sau:\n");
duyetsau(root);

 //Tim kiem 1 nut//

printf("\n Nhap gia tri can tim kiem:");
scanf("%d",&x);
temp=root;
while(temp!=NULL)
{
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
else
break;
}
if(temp==NULL)
printf("\n Tim khong ra!!!");
else
printf("\n Tim thay!!!");
printf("\nTac vu tim kiem da xong.");
 
 //Xoa 1 nut trong cay//

printf("\n Nhap gia tri can xoa:");
scanf("%d",&x);
temp=root;
while(temp!=NULL)
{
if(temp->a==x)
break;
temp1=temp;
if(x<temp->a)
temp=temp->left;
else if(x>temp->a)
temp=temp->right;
}
printf("\n Nut can xoa la: %d, nut cha la %d\n",temp->a,temp1->a);
if(temp==NULL)
printf("\n Tim khong thay!!!");
else
if(temp->left==NULL&&temp->right==NULL)
if(temp->a<temp1->a)
temp1->left=NULL;
else
temp1->right=NULL;
else if(temp->left==NULL)
{
temp1->right=temp->right;
delete(temp);
}
else if(temp->right==NULL)
{
temp1->left=temp->left;
delete(temp);
}
else if(temp->right!=NULL&&temp->left!=NULL)
{
temp1=temp->left;
if(temp1->right==NULL)
{
temp->a=temp1->a;
temp->left=temp1->left;
delete(temp1);
}
else
{
while(temp1->right!=NULL)
{
temp2=temp1;
temp1=temp1->right;
}
temp->a=temp1->a;
temp2->right=NULL;
delete(temp1);
}
}
duyetsau(root);

getch();
}

0 nhận xét:

Đăng nhận xét