Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Cây tìm kiếm nhị phân - Xóa 1 node bất kỳ trên cây TKNP

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cây tìm kiếm nhị phân - Xóa 1 node bất kỳ trên cây TKNP

Bài gửi  admin on Mon Apr 05, 2010 6:31 pm

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();
}

cuchuoi8995
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 11/05/2010

cái này hình như sai rồi anh ơi!

Bài gửi  cuchuoi8995 on Wed May 12, 2010 12:05 am

Code:
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);
  }
}
if((*T)->Left == NULL && (*T)->Right == NULL)
(*T) = NULL;
chỗ này sai nè!nếu như (*T)->Left == NULL && (*T)->Right == NULL thì gán (*T) = NULL; là không ổn rồi.nếu như gán như vậy thì nút trước của nút này vẫn cứ trỏ đến nó và nếu duyệt thì vẫn xuất hiện nút này.muốn mất nó thì nên truyền thêm một biến là nút trên của nút này(tạm gọi là *Tpre) rồi gán Tpre->pleft =NULL và Tpre->right =NULL là ôke!nếu em nói sai thì mong bác mail cho em nha.thanks bác!

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Re: Cây tìm kiếm nhị phân - Xóa 1 node bất kỳ trên cây TKNP

Bài gửi  admin on Wed May 12, 2010 8:55 am

cuchuoi8995 đã viết:
chỗ này sai nè!nếu như (*T)->Left == NULL && (*T)->Right == NULL thì gán (*T) = NULL; là không ổn rồi.nếu như gán như vậy thì nút trước của nút này vẫn cứ trỏ đến nó và nếu duyệt thì vẫn xuất hiện nút này.muốn mất nó thì nên truyền thêm một biến là nút trên của nút này(tạm gọi là *Tpre) rồi gán Tpre->pleft =NULL và Tpre->right =NULL là ôke!nếu em nói sai thì mong bác mail cho em nha.thanks bác!

Không sai vì trong trường hợp này ta xét nó là nút lá.

Sponsored content

Re: Cây tìm kiếm nhị phân - Xóa 1 node bất kỳ trên cây TKNP

Bài gửi  Sponsored content Today at 3:10 am


    Hôm nay: Thu Dec 08, 2016 3:10 am