Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: xin hỏi về xóa cây nhị phân??

  1. #1
    Ngày gia nhập
    05 2007
    Bài viết
    6

    Mặc định xin hỏi về xóa cây nhị phân??

    mình xóa cây nhị phân xong rồi quay lại cho nó duyệt lại thì nó treo máy , có cách nào để nó báo là cây không tồn tại thay vì treo không ? đoạn code như sau:
    Code:
    /*cai dat cay nhi phan theo kieu lien ket  dong */
    #include <alloc.h>
    #include <conio.h>
    #include <stdio.h>
    #include <stdlib.h>
    #define true 1
    #define false 0
     struct node
    	{
        int info;
        node *left;
        node *right;
       };
     typedef struct node *tro;
    //---------khoi tao cay---------
    void init(tro *ptree)
    	{
       *ptree=NULL;
       }
    //-----------------tao mot nut (cap phat mot nut dong)--
    tro getnode()
    	{tro p;
       p=(tro)malloc(sizeof(struct node));
       return (p);
       }
    //-----------------------free node -------------------
    void freenode(tro p)
    	{
       free(p);
       }
    //------------------------kiem tra rong--------------
    int empty(tro p)
    	{if(p==NULL)
          return true;
       else
       	return false;
       }
    //-----------------------cap phat mot nut la(tra ve con tro tro den dia chi )-
    tro	taonut(int x)
    {tro p;
       p=getnode();
       p->left=NULL;
       p->right=NULL;
       p->info=x;
       return(p);
       }
    
    //----------------duyet cay nhi phan (thuat toan de qui LNR)---------------
    void duyetlnr(tro proot)
    	{if(proot!=NULL)
       {duyetlnr(proot->left);
       printf("\n %d",proot->info);
       duyetlnr(proot->right);
       }
    
       }
    //--------------------duyet de qui theo NLR-----------------------------
    void duyetnlr( tro proot)
    	{if(proot!=NULL)
       	{printf("\n %d ",proot->info);
           duyetnlr(proot->left);
           duyetnlr(proot->right);
           }
       }
    //-------------------------------duyet de qui theo lrn----------------
    void duyetlrn(tro proot)
    	{if(proot!=NULL)
         {
          duyetlrn(proot->left);
          duyetlrn(proot->right);
          printf("\n%d",proot->info);
         }
       }
    //------------------------------search info theo thuat de qui--------
    tro search(tro proot,int x)
      {tro p;
       if(proot==NULL)
       	return(NULL);
      	if(proot->info==x)
       	return (proot);
       else
       	if(proot!=NULL)
      		{  p=search(proot->left,x);
          	if(p==NULL)						//tim khong thay nhanh trai chuyen qua nhanh phai
          	p=search(proot->right,x);
             return (p);
          }
        }
    //--------------------------xoa cay  ---------------------------
    void cleartree(tro proot)
    	{if(proot!=NULL)
          {
       	cleartree(proot->left);
          cleartree(proot->right);
          freenode(proot);
          }
        }
    //-------------------------menu-------------------------------
    int menu()
    	{
       int chon;
       printf("\n [1] xuat theo left node right");
       printf("\n [2] xuat theo node left right");
       printf("\n [3] xuat theo left right node ");
       printf("\n [4] xoa cay ");
       printf("\n [5] tim mot nut voi gia tri info ");
       printf("\n nhap vap mot do ");
       scanf("%d",&chon);
       return(chon);
       }
    //----------------------nhap cac nut co san -------------------
    tro tree(int x,tro trai,tro phai)
    {  tro p;
          p=taonut(x);
          p->left=trai;
          p->right=phai;
          return(p);
       }
    //--------------------------------main()----------------------
       main()
       {
       int chon,c,x;
       tro ptree,p;
       init(&ptree);
      ptree=tree(9,tree(3,tree(2,NULL,NULL),tree(5,tree(4,NULL,NULL),tree(8,NULL,NULL))),
      tree(16,tree(14,NULL,NULL),tree(18,NULL,NULL)));
      do
    {   clrscr();
    	chon=menu();
      switch(chon)
       {
      	case 1 :
       	{if(ptree==NULL)
          printf("\n cay rong");
          else
          duyetlnr(ptree);
          break;
          }
       case 2:
       	{
          if(ptree==NULL)
          	printf("\n cay rong");
          else
           duyetnlr(ptree);
           break;
          }
       case 3:
       	{
           if(ptree==NULL)
          printf("\n cay rong");
          else
           duyetlrn(ptree);
           break;
          }
       case 4:
       {
           cleartree(ptree);
           break;
          }
       case 5:
       	{
           printf("\nnhap vao gia tri cua nut muon tim");
           scanf("%d",&x);
           p=search(ptree,x);
           if(empty(p))
           printf("\n khong tim thay");
           else
           printf("\n tim thay nut p co info : %d",p->info);
           break;
           }
    
      }
    printf("\n bam 0 de thoat, phim bat ki tiep tuc");
    scanf("%d",&c);
    }while(c!=0);
    }

  2. #2
    Ngày gia nhập
    12 2006
    Bài viết
    8

    ....Mình cũng đang thắc mắc về vấn đề này..hi vọng các bạn giải đáp dùm ..trong code của bạn forever7040 mình nghĩ thay vì dùm hàm free giải phóng thì gán cho
    Code:
    proot=NULL;
    là được..
    Nhưng thắc mắc của mình lại khác...các bạn thử xem qua code này xem..(trước khi hỏi ..mình nghĩ rất nhiều rồi + xem đi xem lại sách rồi..nhưng vẫn bó tay hi vọng các bạn giúp )
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<iostream.h>
    
    typedef struct tag_TNODE{
    	int key;
    	struct tag_TNODE* pLeft;
    	struct tag_TNODE* pRight;
    }TNODE;
    typedef TNODE* TREE;
    //code a function to make a tree
    void MakeTree(TREE &T)
    {
    	T=NULL;
    	T->pLeft=T->pRight=NULL;
    }
    //function insert a Tnode to Tree
    int insertTnode(TREE &T,int x){
    	if(T){
    		if(T->key==x)
    			return 0; //x is exist in TREE
    		if(T->key>x)//x's value is left of tree
    			return insertTnode(T->pLeft,x);
    		else
    			return insertTnode(T->pRight,x);
    	}
    	T=new TNODE;
    	if(T==NULL) {
    		cout<<"Memory not enough";
    		return -1;
    	}
    	T->key=x;
    	T->pLeft=T->pRight=NULL;
    	return 1;//insert succeed
    }
    //function print all Node to screen
    void LNR(TREE T){
    	if(T){
    		LNR(T->pLeft);
    		cout<<T->key<<" ";
    		LNR(T->pRight);
    	}
    }
    void Destroy(TREE &T){
    	if(T){
    		Destroy(T->pLeft);
    		Destroy(T->pRight);
    		T=NULL;/*nếu mình thay bằng delete T; thì nó in ra giá trị các node như ban đầu trong khi thực chất là đã xóa rồi  trong khi theo mình nghĩ thì nó in ra giá trị rác..chứ
    còn nếu..cho delete T vào giữa 		Destroy(T->pLeft);
                                                                    delete T; 
    		                                      Destroy(T->pRight);
    thì nó lại in ra giá trị rác+ thoát ra luôn ..vì sao vậy*_* */
                               
    	}
    }
    void main(){
    	int x,flag;
    	TREE T;
    	MakeTree(T);
    	do{
    		cout<<"\n1.Insert a Tnode";
    		cout<<"\n2.Print all Tnode on TREE";
    		cout<<"\n3.Destroy all key";
    		cout<<"\n4.Exit";
    		cin>>flag;
    		switch(flag){
    			case 1:
    				cout<<"\nInPut x= ";
    				cin>>x;
    				insertTnode(T,x);
    				break;
    			case 2:
    				LNR(T);
    				break;
    			case 3:
    				Destroy(T);
    				break;
    			case 4:
    				return;
    		}
    	}while(4);
    	getch();
    	delete T;
    }
    Còn vấn đề thứ 2 mình xin hỏi là ...
    trong cái hàm tìm kiếm của mình
    Code:
    TNODE *tim(TREE T,int x)
    {
    	if(T)
    	{
    		if(T->key==x) return T;
    		if(T->key>x)
    			 return tim(T->pLeft,	x); //neu bo return thi sao?
    		else
    			 return tim(T->pRight,x);//neu bo return thi sao?
    	}
    		return NULL;
    }
    nếu mình bỏ return ..thì nó..chỉ tìm kiếm đựoc node gốc mà thôi với debug mình có hiều cách chạy của nó...nhưng về bản chất thì...mình thực sự..ko hiểu sự khác nhau giữa bỏ lệnh return và có lệnh return
    ..HI vọng các bạn giả thích dùm mình...Đệ quy rắc rối quá
    Đã được chỉnh sửa lần cuối bởi anggon : 28-07-2007 lúc 07:33 PM. Lý do: cập nhập

  3. #3
    Ngày gia nhập
    04 2007
    Bài viết
    4

    Code:
    TNODE *tim(TREE T,int x)
    {
    	if(T)
    	{
    		if(T->key==x) return T;
    		if(T->key>x)
    			 return tim(T->pLeft,	x); //neu bo return thi sao?
    		else
    			 return tim(T->pRight,x);//neu bo return thi sao?
    	}
    		return NULL;
    }
    Gửi bạn anggon: Nếu Node cần tìm nằm ở node gốc thì hàm sẽ trả về qua câu lệnh màu xanh. Nhưng khi node cần tìm nằm một bên nhánh nào đó thì giá trị trả ra cuối cùng của hàm luôn luôn là NULL (thực hiện thông qua câu lệnh màu đỏ).
    Đã được chỉnh sửa lần cuối bởi kaka211 : 28-07-2007 lúc 09:16 PM.

  4. #4
    Ngày gia nhập
    12 2006
    Bài viết
    8

    Trích dẫn Nguyên bản được gửi bởi kaka211 Xem bài viết
    Code:
    TNODE *tim(TREE T,int x)
    {
    	if(T)
    	{
    		if(T->key==x) return T;
    		if(T->key>x)
    			 return tim(T->pLeft,	x); //neu bo return thi sao?
    		else
    			 return tim(T->pRight,x);//neu bo return thi sao?
    	}
    		return NULL;
    }
    Gửi bạn anggon: Nếu Node cần tìm nằm ở node gốc thì hàm sẽ trả về qua câu lệnh màu xanh. Nhưng khi node cần tìm nằm một bên nhánh nào đó thì giá trị trả ra cuối cùng của hàm luôn luôn là NULL (thực hiện thông qua câu lệnh màu đỏ).
    ...Theo mình thì (theo kết quả debug thì..đúng hơn) Khi có return mình muốn tìm một phần tử x nào đó thì bản thân 2 lời gọi lại hàm( ko có return nha) sẽ theo 2 nhánh cho đến khi nào gặp x giả sử là
    Code:
    a ->b->c->d(=x)
    .Khi đã gặp nó lại bắt đầu thoát ra từ hàm trong cùng và trong quá trình nó thoát ra thì giá trị mà x phải so sánh bây giờ là c->b->a nên nó chỉ tìm đựoc a mà thôi....
    còn nếu như có return thì khi nó chạy đến trong cùng(tức là gặp d=x rồi) hám sẽ thoát ra tức là nó không đi lùi như hồi nãy nữa
    Bạn..xem đúng không mình mập mờ về ..cái này lắm
    Hic lệnh
    return tim(T->pRight,x)
    hàm vẫn chạy đến khi gặp x
    còn lệnh
    tim(T->pRight,x)
    NÓ cũng chạy đến gặp x..mà sao kq khác nhau
    (@_@)! có ai giả thích cụ thể dùm mình không----------
    Đã được chỉnh sửa lần cuối bởi anggon : 29-07-2007 lúc 11:35 AM.

  5. #5
    Ngày gia nhập
    04 2007
    Bài viết
    4

    Đúng là cả hai cái đều chạy tới Node x. Nhưng trường hợp có "return" thì trả về Node X. Còn trường hợp không có return thì trả về NULL.
    Bạn nên đơn giản vấn đề mà bạn đang nghĩ thông qua việc tìm hiểu mục đích của 4 câu lệnh return.

    Theo mình thì khi làm đệ qui thì có mấy vấn đề sau cần lưu ý:
    -Điều kiện dừng
    -Tài nguyên cần dùng cho đệ qui
    -Hàm đệ qui làm gì ? Tham số như thế nào ? Trả ra giá trị gì ?

    Vdụ vào bài tìm kiếm Node trong cây nhị phân (tìm theo NLR)
    -Điều kiện dừng: dừng đệ qui khi gặp Node cần tìm hoặc gặp Node NULL.
    -Tài nguyên: Chiều cao của cây như thế nào thì nên dùng đệ qui ?
    -Hàm đệ qui: TNODE *tim(TREE T,int x)
    +++++++Tham số:
    >>>>>>>>>>>>T: Cây nhị phân có Node cần tìm (T: là Node gốc)
    >>>>>>>>>>>>x: Giá trị của Node cần tìm
    >>>>>>>>>>>>Hàm trả về :
    ++++++++++++++++ Nếu tìm thấy, trả về Node cần tìm
    ++++++++++++++++ Nếu không tìm thấy, trả về NULL

    Sau khi phân tích xong, ta giả sử đã tồn tại hàm đệ qui trên và code:
    Code:
      
    [Mã giả]
    TNODE *tim(TREE T,int x)
    {
         If (T)
         {
              if (T->key==x)   Return T;
                             
              //Nếu Node cần tìm nằm bên nhánh trái của Node T
              if (T->key > x)
              {
                   TNODE * Temp;
                   //Gọi hàm tìm với cây nhị phân có Node gốc là T->pLeft. Hàm này trả về Node tìm thấy hoặc NULL nếu không tìm thấy
                   Temp=tim(T->pLeft,x);
                   Return Temp; //Vì chắc chắc lúc này Node cần tìm không thể nằm bên nhánh phải của T được!
                                    
              }
    
              //Nếu Node cần tìm nằm bên nhánh phải của Node T
              if (T->key < x)
              {
                   TNODE * Temp;
                   //Gọi hàm tìm với cây nhị phân có Node gốc là T->pRight. Hàm này trả về Node tìm thấy hoặc NULL nếu không tìm thấy
                   Temp=tim(T->pRight,x);
                   Return Temp; //Vì chắc chắc lúc này Node cần tìm không thể nằm bên nhánh trái của T được!
                                    
              }
         }
         Return NULL; //Do T==NULL;               
    }
    Đã được chỉnh sửa lần cuối bởi kaka211 : 29-07-2007 lúc 08:05 PM.

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định xin hỏi về xóa cây nhị phân??

    Uhm! Đúng như kaka đã phân tích.

    Nếu bài viết nào cũng được phân tích rõ ràng như thế thì diễn đàn sẽ rất chất lượng và dễ hiểu.
    Hoan nghên kaka

  7. #7
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    37

    Đay là bài xao cua mình xin góp ý cùng các bạn
    Code:
    #include"stdio.h"
    #include"stdlib.h"
    #include"conio.h"
    
    struct node{int data;node* lchild;node* rchild;};
    typedef node* BST;
    void themnode(int x,BST T)
    {
         if(T->data==x)
         {
               printf("%d Da co trong cay\n",x);
               return;
         }
         else if(T->data>x)
                   if(T->lchild!=NULL) themnode(x,T->lchild);
                   else
                   {
                         node* p=(node*)malloc(sizeof(node));
                         p->data=x;
                         p->lchild=p->rchild=NULL;
                         T->lchild=p;
                   }
               else
                   if(T->rchild!=NULL) themnode(x,T->rchild);
                   else 
                   {
                         node* p=(node*)malloc(sizeof(node));
                         p->data=x;
                         p->lchild=p->rchild=NULL;
                         T->rchild=p;
                   }
    }
    BST taocay()//Ham tao cay
    {
         BST T;
         int x;
         char ch;
         T=(node*)malloc(sizeof(node));
         printf("Nhap vao node goc :");
         scanf("%d",&x);
         T->data=x;
         T->rchild=T->lchild=NULL;
         do
         {
              printf("muon dung an ESC");
              ch=getch();
              if(ch!=27)
              {
                    printf("\nNhap vao 1 so :");
                    scanf("%d",&x);
                    themnode(x,T);
              }
         }while(ch!=27);
         return T;
    }
    BST leftmost(BST T)//ham tra ve node cuc trai cua cay con phai
    {
         if(T==NULL)
         {
                printf("cay rong :");
                return NULL;
         }
         else if(T->rchild==NULL)  return T;
         else 
         {
                node* p=T->rchild;
                while(p->lchild) p=p->lchild;
                return p;
         }
    }
    BST rightmost(BST T)//han tra ve node cuc phai cua cay con trai
    {
         if(T==NULL)
         {
                printf("cay rong :");
                return NULL;
         }
         else if(T->lchild==NULL)  return T;
         else 
         {
                node* p=T->lchild;
                while(p->rchild) p=p->rchild;
                return p;
         }
    }
    void duyetcay(BST T)//ham in cay theo thu tu trai node phai
    {
         if(T!=NULL)
         {
               duyetcay(T->lchild);
               printf("%d ;",T->data);
               duyetcay(T->rchild);
         }
         else return;
    }
    int ktngto(int x)//ham kiem tra nguyen to
    {
         for(int i=2;i<x;i++)
              if(x%i==0) return 0;
         return (x>1);
    }
    void ngtomax(BST T,BST T1)//ham tao 1 cay gom cac so nguyen to trong cay T
    {
         if(T!=NULL)
         {
                ngtomax(T->lchild,T1);
                if(ktngto(T->data)) themnode(T->data,T1);
                ngtomax(T->rchild,T1);
         }
         else return ;
    }
    int max(BST T)//ham tra ve so lon nhat
    {
         node* p=T;
         while(p->rchild)
              p=p->rchild;
         return p->data;
    }
    int min(BST T)//ham tra ve so nho nhat
    {
         node* p=T;
         while(p->lchild)
              p=p->lchild;
         return p->data;
    }
    BST pre(BST x,BST T)//ham tra ve cha cua node x
    {
         if(x==T->data) return NULL;
         BST p=T;
         while(p->lchild!=x&&p->rchild!=x)
         {
              if(x->data>p->data) p=p->rchild;
              else p=p->lchild;
         }
         return p;
    }
    BST timkiem(int x,BST T)//ham tim kiem xem x co trong cay ko
    {
         if(T==NULL)
                return NULL;
         else
         {
              if(x==T->data) return T;
              else if(x<T->data) return timkiem(x,T->lchild);
              else return timkiem(x,T->rchild);
         }
    }
    void  xoanode1(BST x,BST& T)//xoa node ko co con
    {
         if(x==T) T=NULL ;
         else 
         {
              if(x->data<pre(x,T)->data)
                   pre(x,T)->lchild=NULL;
              else pre(x,T)->rchild=NULL;
              free(x);
         }
    }
    void xoanode2(BST x,BST& T)//xoa node chi co 1 con
    {
         if(x==T)
               if(T->lchild) T=T->lchild;
               else T=T->rchild;
         else
               if(x->data<pre(x,T)->data)
               {
                     if(x->lchild)
                          pre(x,T)->lchild=x->lchild;
                     else
                          pre(x,T)->lchild=x->rchild;
                          free(x);
               }
               else
               {
                     if(x->lchild)
                          pre(x,T)->rchild=x->lchild;
                     else
                          pre(x,T)->rchild=x->rchild;
                          free(x);
               }
    }
    void xoanode3(BST x,BST& T)//xoa node co 2 con
    {
         if(x==T)
         {
               BST q=leftmost(T);
               if(pre(q,T)==T)
               {
                     T->data=q->data;
                     T->rchild=q->rchild;
               }
               else
               {
                    int n=q->data;
                    if(q->lchild==NULL&&q->rchild==NULL)
                    {
                         xoanode1(q,T);
                         T->data=n;
                    }
                    else if((q->lchild&&q->rchild==NULL)||(q->rchild&&q->lchild==NULL))
                         {
                              xoanode2(q,T);
                              T->data=n;
                         }     
               }
         }
         else
         {
               if(x->data<T->data) xoanode3(x,T->lchild);
               else xoanode3(x,T->rchild);
         }
    }
    void xoanode(int x,BST& T)//ham xoa x ra khoi cay
    {
         BST q=timkiem(x,T);
              if(q->lchild==NULL&&q->rchild==NULL)
                   xoanode1(q,T);
              else if(q->lchild&&q->rchild)
                        xoanode3(q,T);
                   else
                        xoanode2(q,T);
    }
    
    int main()
    {
         int x;
         BST T,T1;
         T1=(node*)malloc(sizeof(node));
         T1->data=0;
         T1->lchild=T1->rchild=NULL;
         T=taocay();
         printf("\nDuyet theo thu tu TRP:");
         duyetcay(T);
         puts("");
         printf("phan tu lon nhat la :%d\n",max(T));
         printf("phan tu nho nhat la :%d\n",min(T));
         printf("Nhap vao 1 so nguyen :");
         do
         {
              scanf("%d",&x);
              if(timkiem(x,T))
              {
                    printf("%d da co trong cay\n",x);
                    printf("yeu cau nhap lai :");
              }
         }while(timkiem(x,T)); 
         themnode(x,T);
         printf("Cay sau khi them %d :",x);
         duyetcay(T);
         puts("");
         ngtomax(T,T1);
         if(max(T1)>0)
               printf("so nguyen to lon nhat la :%d\n",max(T1));
         else puts("trong cay ko co so ngto");
         printf("nhap vao 1 so nguyen :");
         do
         {
               scanf("%d",&x);
               if(timkiem(x,T)==NULL) 
               {
                     printf("ko co %d trong cay\n",x);
                     printf("yeu cau nhap lai :");
               }
         }while(timkiem(x,T)==NULL);
         xoanode(x,T);
         printf("Cay sau khi xoa %d :",x);
         duyetcay(T);
         getch();
         return 0;
    }
    Đã được chỉnh sửa lần cuối bởi vannhan : 06-11-2008 lúc 10:35 PM.

Các đề tài tương tự

  1. Không thể xóa file trong IsolatedStorageFile, cách nào để xóa?
    Gửi bởi mrdungx trong diễn đàn Lập trình Windows Mobile bằng C#
    Trả lời: 0
    Bài viết cuối: 04-04-2013, 11:25 PM
  2. Kỹ thuật C++0x Xóa không được 1 phần tử bất kì và xóa tại vị trí bất kì trong DSLK
    Gửi bởi datinh_o0o7 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 19-03-2011, 10:24 PM
  3. Bài tập C++ xóa sinh viên trong dssv , ai test dùm em , xóa sv thứ 3 mà nó toàn xóa sv thứ 4
    Gửi bởi prt_awm trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 08-11-2010, 02:24 PM
  4. code xóa một tệp, lỗi không xóa được file nào?
    Gửi bởi rong3sao trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 12-04-2009, 06:41 PM
  5. Tại sao chọn xóa n lại xóa tại n + 1 - Linked List trong lập trình C
    Gửi bởi dieucay555 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 03-03-2008, 11:43 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn