XÓA 1 NÚT BẤT KỲ TRÊN CÂY TÌM KIẾM NHỊ PHÂN
Giả sử ta muốn xoá một nút có khoá x, trước hết ta phải tìm kiếm nút chứa khoá x trên cây.
Việc xoá một nút như vậy, tất nhiên, ta phải bảo đảm cấu trúc cây TKNP không bị phá vỡ.
Thuật toán:
-Nếu không tìm thấy nút chứa khoá x thì giải thuật kết thúc.
-Nếu tìm gặp nút N có chứa khoá x, ta có ba trường hợp sau:
· Nếu N là lá ta thay nó bởi NULL.
· N chỉ có một nút con ta thay nó bởi nút con của nó.
· N có hai nút con ta thay nó bởi nút lớn nhất trên cây con trái của nó (nút cực phải của cây con trái) hoặc là nút bé nhất trên cây con phải của nó (nút cực trái của cây con phải). Trong giải thuật sau, ta thay x bởi khoá của nút cực trái của cây con bên phải rồi ta xoá nút cực trái này. Việc xoá nút cực trái của cây con bên phải sẽ rơi vào một trong hai trường hợp trên.
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int TData;
//Cau truc cua Node
typedef struct TNode{
TData Data;
TNode*Left;
TNode*Right;
};
//Cau truc cay
typedef TNode* TTree;
//Khoi tao cay rong
void MakeNullTree(TTree *T)
{
(*T) = NULL;
}
//Duyet tien to NLR
void PreOrder(TTree T)
{
if(T!=NULL)
{
printf("%4d ",T->Data);
PreOrder(T->Left);
PreOrder(T->Right);
}
}
//Duyet trung to LNR
void InOrder(TTree T)
{
if(T !=NULL)
{
InOrder(T->Left);
printf("%4d ",T->Data);
InOrder(T->Right);
}
}
//Duyet hau to LRN
void PosOrder(TTree T)
{
if(T!=NULL)
{
PosOrder(T->Left);
PosOrder(T->Right);
printf("%4d ",T->Data);
}
}
//Thu tuc them 1 khoa vao cay tim kiem nhi phan
void InsertNode(TTree *Root,TData x)
{
if (*Root == NULL){ /* them nut moi chua khoa x */
(*Root)=(TNode*)malloc(sizeof(TNode));
(*Root)->Data = x;
(*Root)->Left = NULL;
(*Root)->Right = NULL;
}
else
if (x < (*Root)->Data)
InsertNode(&(*Root)->Left,x);
else
if (x>(*Root)->Data)
InsertNode(&(*Root)->Right,x);
}
//Nhap cac Node vao cay
void Tree(TTree*k) {
int x;
printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
printf("Nhap so 0 thi ket thuc:");
do {
scanf("%d",&x);
if (x != 0)
InsertNode(&*k,x);
} while(x != 0);
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0 viet khong de quy
int Search(TTree Root,TData x){
TTree temp = Root;
while(temp != NULL)
{
if(x == temp->Data)
return 1;
else
if (x > temp->Data)
temp = temp ->Right;
else
temp = temp -> Left;
}
return 0;
}
//xac dinh so node trong cay
int Number_Node(TTree T)
{
if(T==NULL)
return 0;
else
return 1 + Number_Node(T->Left) + Number_Node(T->Right);
}
//Ham tra ve node con cuc trai dong thoi xoa node nay
TData DeleteGreatLeft(TTree * T)
{
if((*T)->Left ==NULL)
{
TData temp = (*T)->Data;
(*T) = (*T)->Right;
return temp;
}
else
return DeleteGreatLeft(&(*T)->Left);
}
//Thu tuc xoa 1 node bat ky
void DeleteNode(TData x, TTree* T)
{
if(x > (*T)->Data)
DeleteNode(x,&(*T)->Right);
else
if(x <(*T)->Data)
DeleteNode(x,&(*T)->Left);
else
{
if((*T)->Left == NULL && (*T)->Right == NULL)
(*T) = NULL;
else
if((*T)->Left == NULL)
(*T) = (*T)->Right;
else
if((*T)->Right == NULL)
(*T) = (*T)->Left;
else
(*T)->Data = DeleteGreatLeft(&(*T)->Right);
}
}
//Chuong trinh chinh
void main() {
TTree T; //Khoi tao cay ban day
int n;
MakeNullTree(&T);
clrscr();
Tree(&T);
printf("\nGia tri cua cay khi duyet NLR.\n");
PreOrder(T);
printf("\nGia tri cua cay khi duyet LNR.\n");
InOrder(T);
printf("\nGia tri cua cay khi duyet LRN.\n");
PosOrder(T);
printf("\nSo node trong cay %d.", Number_Node(T));
printf("\nNhap phan tu can xoa ");
scanf("%d",&n);
if ( Search(T,n) == 0 )
printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
else
{
DeleteNode(n,&T);
printf("\nSo node con lai trong cay %d.", Number_Node(T));
printf("\nGia tri cua cay khi duyet NLR.\n");
PreOrder(T);
printf("\nGia tri cua cay khi duyet LNR.\n");
InOrder(T);
printf("\nGia tri cua cay khi duyet LRN.\n");
PosOrder(T);
}
getch();
}