Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 19 kết quả

Đề tài: Cây nhị phân tìm kiếm trong lập trình C. Giúp sửa hàm xóa

  1. #1
    Ngày gia nhập
    02 2008
    Bài viết
    18

    Mặc định Cây nhị phân tìm kiếm trong lập trình C. Giúp sửa hàm xóa

    Hiện mình đang làm một cây nhị phân tìm kiếm nhưng bị lỗi hàm xóa một nút trong cây nhị phân (tìm mãi mà không hiểu mình sai chỗ nào).
    Các bạn giúp mình sửa bài này nhá
    PHP Code:
    #include <iostream.h>
    #include <conio.h>
    #include <stdlib.h>
    /* Binary search Tree */
    ///////////////////////////////////////////////////////////////////// Start Node
    class Node
    {
        private:
            
    int key;
           
    Node*left;
           
    Node*right;
       public:
           
    Node()
          {
               
    key 0;
             
    left NULL;
             
    right NULL;
          };
           
    Node(const int &key_)
           {
               
    key key_;
               
    left NULL;
              
    right NULL;
           };
          
    Node getRight();
          
    Node getLeft();
          
    void getKey(int &thekey);
        
    void setRight (Node *);
        
    void setLeft (Node *);
       
    friend class Tree;
    };

    void Node::getKey(int thekey)
    {
        
    thekey key;
    };

    Node Node::getRight ()
    {
        return 
    right;
    };

    Node Node::getLeft ()
    {
         return 
    left;
    };

    void Node::setRight (Node iNode)
    {
        
    right iNode;
    };

    void Node::setLeft (Node iNode)
    {
        
    left iNode;
    };

    //////////////////////////////////////////////////////////////////   Finish Node


    //////////////////////////////////////////////////////////////////   Start Tree
    class Tree
    {
        private:
           
    Node *root;
       protected:
           
    bool Insert(Node *& rootint key);
          
    bool Remove(Node *& rootint k);
       public:
           
    Tree()
          {
              
    root NULL;
          };
          
    Tree(const Tree &oldtree)    // ham tao ban sao copy  tao ra 1 cay moi co du lieu giong "oldtree"
           
    {

           };
          
    void DeleteTree();                           // Huy mot cay nhi phan
          
    void Insert(int key_);                       // Ham chen mot phan tu vao cay

             
    bool Remove(int key_);                       // Ham xoa mot phan tu trong tree
          
    bool Find_RemoveKey(Node *pTreeintcurrentint key_);

          
    void Find_key(Node *prootint key_) ;       // Ham tim kiem mot key co ton tai khong
          
    void Find(int key_) ;
          
    bool IsEmpty() ;                                // Ham kiem ra cay nhi phan co rong khong
          
    void Pretrav(Node *proot);                   // Duyet cay nhi phan theo thu tu truoc (NLR)
          
    void Intrav(Node *proot);                    // Duyet cay nhi phan theo thu tu giua (LNR)
          
    void Posttrav(Node *proot);                  // Duyet cay nhi phan theo thu tu sau (LRN)
          
    void Print();                                // Hien thi 3 phep duyet cay

    };
    void Tree::DeleteTree()
    {
        
    root NULL;
       
    delete root;
    };

    void Tree::Find(int key_)
    {
        
    Find_key(root,key_);
    };

    void Tree::Print()
    {
        if(
    IsEmpty())
              
    cout<<"\n\t\t\tCay rong ";
        else
        {
               
    cout<<"\nDuyet theo kieu Posttrav: ";   Posttrav(root); cout<<endl;
                
    cout<<"Duyet theo kieu Intrav:   ";     Intrav(root);cout<<endl;
                
    cout<<"Duyet theo kieu Pretrav:  ";     Pretrav(root); cout<<endl;
        }
    };

    bool Tree::IsEmpty()// Ham kiem ra cay nhi phan co rong khong
    {
        return (
    root == NULL true false);
    };

    void Tree::Pretrav(Node *proot// Duyet cay nhi phan theo thu tu truoc (NLR)
    {
         if(
    proot != NULL)
       {
            
    cout<<proot->key<<"  ";
          
    Pretrav(proot->left);
          
    Pretrav(proot->right);
       };
    };

    void Tree::Intrav(Node *proot)  // Duyet cay nhi phan theo thu tu giua (LNR)
    {
        if(
    proot != NULL)
       {
            
    Intrav(proot->left);
          
    cout<<proot->key<<"  ";
          
    Intrav(proot->right);
       };
    };

    void Tree::Posttrav(Node *proot)   // Duyet cay  nhi phan theo thu tu sau (LRN)
    {
       if(
    proot != NULL)
       {
             
    Posttrav(proot->left);
          
    Posttrav(proot->right);
          
    cout<<proot->key<<"  ";
       };
    };

    void Tree::Find_key(Node *prootint key_)   // Tim kiem mot key
    {
        if(
    proot == NULL)
           
    cout<<"\nKhong tim thay "<<key_;
       else
       {
           if(
    proot->key key_)
              
    Find_key(proot->left,key_);
          else
          {
              if(
    key_ proot->key)
                 
    Find_key(proot->right,key_);
             if(
    key_ == proot->key)
                 
    cout<<"\nTim thay "<<key_;
          }
       }

    };

    void Tree::Insert(int key_)     // Chen mot gia tri vao cay nhi phan
    {
           
    Node *= new Node(key_);
          
    Node *root;
          if(!
    root)
             {
              
    root p;
             return ;
          }
          while(
    q)
          {
              if(
    q->key  == key_)
             {
                 
    cout<<"khong chen duoc:";
                  return ;
             }
             else
             {
                 if(
    q->key key_)
                {
                    if(!
    q->left)// neu cay con trai ma rong  thi chen` luon vao do
                    
    {
                        
    q->left p;
                      return ;
                    }
                   else
                       
    q->left;// di tiep sang cay con trai
                
    }
                if(
    q->key key_)
                {
                    if(!
    q->right)// neu cay con fai ma rong  thi chen` luon vao do
                   
    {
                       
    q->right p;
                      return ;
                   }
                   else
                       
    q->right;// di tiep sang cay con fai
                
    }
              }
          }
    };


    //////////////////////////////////////////////////////////////////    Finish Node



    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                                                    // gia tri key_ nut can tim
    bool Tree::Find_RemoveKey(Node *pTreeint&currentint key_// Tim cha cua nut can xoa
    {                        // Tao mot con tro pTree de luu vi tri cua nut can xoa
                             // Tao mot bien current de luu vi tri nut can xoa la trai hay phai
                             //       neu la trai thi bang 1 neu la phai thi bang 0

        
    Node *proot root;   // tao mot con proot gan no bang root de lay vi tri dau tien trong cay
       
    if( root == NULL // neu cay rong thi ko tim duoc va thoat khoi ham
           
    return false;
       if( 
    root->key == key_ // neu goc cua cay bang voi gia tri can chen thi luu gia tri cua proot = root
       
    {
            
    pTree root;
          return 
    true;
       };
       while( 
    proot->left != NULL || proot->right != NULL )
       {    
    // chung nao ma nhanh trai va nhanh phai cua cay ma con khac NULL thi van tim tiep
           
    if( proot->right != NULL && proot->right->key == key_ )
          {   
    // Neu nhanh phai ko rong va gia tri nhanh phai bang voi gia tri cam thi thi
              
    current 0;   // gan current = 0  de xac dinh vi tri cua no o ben phai
              
    pTree proot;   // gan con pTree = root de luu vi tri cua nut can xoa
             
    return true;
          }
          if(
    proot->left && proot->left->key == key_)
          {    
    // Neu nhanh phai ko rong va gia tri nhanh trai bang voi gia tri cam thi thi
              
    current 1;    // gan current = 1  de xac dinh vi tri cua no o ben trai
              
    pTree proot// gan con pTree = root de luu vi tri cua nut can xoa
             
    return true;
          }
          if(
    proot->key key_)   // Neu gia tri
          
    {
              if(!
    proot->right// Neu nhanh phai rong thi
                  
    return false;   // Khong tim thay va thoat khoi ham
              
    proot proot->right// tiep tuc cho proot tim den nut right ke tiep
          
    }
          if(
    proot->key key_)
          {
              if(!
    proot->left)  // Neu nhanh phai rong thi
                  
    return false// // Khong tim thay va thoat khoi ham
              
    proot proot->left// tiep tuc cho proot tim den nut left ke tiep
          
    }
       };
       return 
    false;
    }  ;


    bool Tree::Remove(int key_)  // Ham xoa
    {
        
    Node *node;
       
    Node *temp;
       
    int huong = -1;

       if(
    Find_RemoveKey(node,huong,key_))
       {
           if(
    huong == 0// truong hop node o ben trai
              
    temp node->right;
          if(
    huong == 1)  // truong hop node o ben phai
              
    temp node->left;
          if(
    huong == -1)   // truong hop node o goc
              
    temp root;
                   if(
    temp->right == NULL && temp->left == NULL)   // nut can xoa ko co cay con
          
    {
               if(
    huong == 0)  // node can xoa ben trai node cha
                 
    node->right == NULL;
             if(
    huong == 1)
                 
    node->left == NULL;
             if(
    huong ==-1)
             {
                  
    root NULL;
                return 
    true;
             }
             
    temp->right NULL;
             
    temp->left NULL;
             return 
    true;
          }

          if(
    temp->left != NULL && temp->right == NULL//truong hop co cay ben phai nhung khong co cay con ben trai
          
    {


             if(
    huong == 1)
                 
    node->left temp->left;
             if(
    huong == 0)
                 
    node->right=temp->left;
             if(
    huong == -1)
             {
                 
    root=root->left;
                return 
    true;
             }
             
    temp->left=NULL;
             return 
    true;
          }

          if(
    temp->left == NULL && temp->right != NULL//truong hop co cay ben trai nhung khong co cay con ben phai
          
    {
             if(
    huong == 1)
                 
    node->left temp->right;
             if(
    huong == 0)
                 
    node->right=temp->right;

             if(
    huong == -1)
             {

                 
    root root->right;
                
    node->right NULL;
                 
    delete node;
                return 
    true;
             }

             
    temp->right=NULL;
             
    delete temp;
             return 
    true;
          }

          if(
    temp->left && temp->right)   // truong hop ca hai nhanh deu co cay con
          
    {
                    
    Node*temp1 node->right;  // ta di sang nhanh con ben fai va tim gia tri min cua no'
              
    Node*temp2 temp;
             while(
    temp1->left)
              {
                 
    temp2=temp1;
                
    temp1=temp1->left;
              }
              
    temp->key temp1->key;
              if(
    temp2 == temp// neu ta fat hien gia tri min la gia tri ngay sau gia tri can xoa
              
    temp2->right temp1->right;
              else
              
    temp2->left temp1->right;
              
    delete temp1;
              return 
    true;
          }
       }
       else
       {
           
    cout<<"ko xuat hien "<<endl;
          return 
    false;
       }


    };
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



    //////////////////////////////////////////////////////////////////    Finish Node


    //////////////////////////////////////////////////////////////////     Start menu
    void Menu(Tree &bst)
    {
        
    int choose,value;
       
    char choose1;
       
    cout<<"\t\t\t BINARY SEARCH TREE\n\n";
       
    cout<<"\t\t1.Hien thi cay nhi phan\n\n";
       
    cout<<"\t\t2.Chen mot phan tu vao cay nhi phan.\n\n";
       
    cout<<"\t\t3.Xoa mot phan tu vao cay nhi phan.\n\n";
       
    cout<<"\t\t4.Xoa ca cay nhi phan.\n\n";
       
    cout<<"\t\t5.Tim kiem mot phan tu vao cay nhi phan.\n\n";
       
    cout<<"\t\t6.Sao chep cay hien tai thanh cay moi.\n\n";
       
    cout<<"\t\t7.Thoat khoi chuong trinh.\n\n\n";
       
    cout<<"\t\t Moi chon mot chuc nang: ";
       
    cin>>choose;
       switch(
    choose)
       {
          case 
    1:
          {
              
    system("cls");
               
    bst.Print();
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
          case 
    2:
          {
              
    system("cls");
             
    int n;
             
    cout<<"Ban muon nhap bao nhieu phan tu: ";
             
    cin>>n;
             for(
    int i 0;n;i++)
             {
                   
    cout<<"\n Nhap vao gia tri muon chen: ";
                 
    cin>>value;
                 
    bst.Insert(value);
             }
             
    cout<<"\n\n Cay nhi phan sau khi da chen ";
             
    bst.Print();
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
          case 
    3:
          {
          
    system("cls");
             do
             {
                 
    cout<<"\n Cay nhi phan hien tai: ";
                 
    bst.Print();
                   
    cout<<"\n Nhap vao gia tri muon xoa: ";
                 
    cin>>value;
                 
    bst.Remove(value);
                
    cout<<"\nBan co muon xoa tiep hem (y/n): " ;
                
    cin>>choose1;
             }while(
    choose1 == 'y');
             
    cout<<"\n\n Cay nhi phan sau khi da xoa ";
             
    bst.Print();
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
          case 
    4:
          {
              
    system("cls");
             
    bst.DeleteTree();
             
    cout<<"\n\t\t\tCay nhi phan da duoc xoa: ";
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
          case 
    5:
          {
              
    system("cls");
             
    cout<<"\n Cay nhi phan hien tai: ";
             
    bst.Print();
               
    cout<<"\n Nhap vao gia tri muon tim: ";
             
    cin>>value;
             
    bst.Find(value);
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
          case 
    6:
          {
               
    system("cls");
             
    cout<<"\n Sory! chuc nang nay chua mo";
             
    getch();
             
    system("cls");
             
    Menu(bst);
          }
           case 
    7:
          {
               exit(
    0);
          }
       };
    };
    /////////////////////////////////////////////////////////////// Start main
    void main()
    {
            
    textmode(C4350); // Noi rong man hinh console
         
    Tree bst;
          
    Menu(bst);
            
    getch();

    Kick link Download code
    Đã được chỉnh sửa lần cuối bởi Counter-Strike : 23-02-2008 lúc 03:22 PM.

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Ối cậu viết dông dài mà khó hiểu nữa. Tớ đọc thấy đuối.
    Khi tớ down về thấy dòng *(đã sửa).cpp có nghĩa là cậu fix được rồi à.

  3. #3
    Ngày gia nhập
    02 2008
    Bài viết
    18

    Chưa đâu đã sửa được đâu. Mà tớ viết đúng là dài thật nhưng cậu để ý một hàm xóa giúp tớ thôi, chèn với in với tìm kiếm đúng hết rồi, nhưng riêng hàm xóa tớ chẳng hiểu làm sao mà sai.

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    He cậu nêu lại cái ý tưởng của cậu đi ? Đọc oải quá. Mà tớ lại chưa cài cái VC nên ko debug được.
    Để mai tớ cài rồi test thử xem sao .

  5. #5
    Ngày gia nhập
    06 2007
    Nơi ở
    UIT
    Bài viết
    44

    Chào bạn ! Đọc cái phần xóa node của bạn đau cả mắt sao bạn không dùng đệ quy nhỉ ? Mình lục trong tài liệu mình đã học có phần này bạn đọc tham khảo xem nhé !
    Code:
    void thaythecach1(Tree& p,Tree&t )
    {
    	if(t->left!=NULL)
    	thaythecach1(p,t->left);
    	else
    	{
    		p->key=t->key;
    		p=t;
    		t=t->right;
    	}
    }
    void deletetnodex(Tree& t,int x)
    {
    	if(t!=NULL)
    	{
    		if(t->key<x)
    		deletetnodex(t->right,x);
    		else
    		{
    			if(t->key>x)
    			deletetnodex(t->left,x);
    			else
    			{
    				TNode* p;
    				p=t;
    				if(t->left==NULL)
    				t=t->right;
    				else
    				{
    					if(t->right==NULL)
    					t=t->left;
    					else
    					thaythecach1(p,t->right);
    				}
    				delete p;
    			}
    		}
    	}
    	else
    	printf("\nKhong tim thay phan can xoa");
    }

  6. #6
    Ngày gia nhập
    02 2008
    Bài viết
    18

    Mặc định Cây nhị phân tìm kiếm trong lập trình C. Giúp sửa hàm xóa

    Trích dẫn Nguyên bản được gửi bởi kidkid Xem bài viết
    He cậu nêu lại cái ý tưởng của cậu đi ? Đọc oải quá. Mà tớ lại chưa cài cái VC nên ko debug được.
    Để mai tớ cài rồi test thử xem sao .
    OK ý tưởng của iem là thế này.
    Đầu tiên ta viết một hàm tìm kiếm node cha của nút cần xóa (hàm này mình comment rất đầy đủ chắc bạn đọc cũng hiểu được)
    Sau đó trong hàm xóa node mình gọi đến hàm tìm node cha
    Sẽ có 4 trường hợp sảy ra.

    - Trường hợp nút cần xóa không có cây con
    + Ta chia ra những trường hợp: node cần xóa bên trái node cha
    Thì ta sẽ cho node cha trỏ đến nút con bên phải bằng NULL (tức là xóa nút cần xóa luôn)
    Trường hợp node cần xóa bên phải node cha thì cũng tương tự.
    Trường hợp node cần xóa ở gốc thì quá đơn giản rồi phải không. Cho root (nút gốc = NULL là xong)

    - Trường hợp nút cần xóa có cây con bên phải nhưng ko có cây con bên trái
    Xét trường hợp nút cần xóa ở bên trái nút cha thì cho node cha nút cần xóa trỏ đến nút con bên trái nút cần xóa là xong.
    Trường hợp nút cần xóa bên trái nút cha thì cũng tương tự.
    Cũng cần phải xét cả trường hợp node cần xóa là nút gốc.

    - Trường hợp nút cần xóa có cây con bên trái nhưng ko có cây con bên phải.
    + Tương tự trường hợp trên.

    - Trường hợp nút cần xóa có cả cây con phải là cây con bên trái thì hơi rắc rối một tẹo.
    +Ta sẽ phải xác định xem liệu có một cây con phải của cây con trái không
    nếu có thì ta lại lần xuống cây con phải cây con phải của cây con trái của nút ấy cho đến khi không còn nút phải nào nữa, tức là đã đụng tới con phải thấp nhất (cái vòng while của em đấy) vậy ta tìm được giá trị nhỏ nhất.Thì ta thay giá trị của nút cần loại bỏ bằng giá trị nút nhỏ nhất vừa tìm được. Và sau đó ta xóa giá trị min vừa tìm được. (Nôm na là ta tìm node có giá trị nhỏ nhất của cây bên phải sau đó gán giá trị của node cần xóa bằng giá trị của min tìm được và xóa nút có giá trị min tìm được đó đi là OK)

    (mịa em dốt văn hy vọng các bác hiểu)

    Đấy thuật toán ý tưởng của em là như vậy (nói thật cây nhị phân là phần khó cũng như là phần khá cao cấp trong CTDL). Còn cũng nói thật luôn là em vốn ngu bẩm sinh nên về đệ quy tới giờ em vẫn không thể hiểu được thấu đáo nó chạy từng bước từng bước như thế nào nên em cũng chẳng dám dùng, nói thẳng ra là đếch biết dùng thế nào. Hô hô.
    Bác vtien_uit nói qua cho em ý tưởng và thuật toán của đoạn code bác cho em cái. Mịa em vốn đã ngu nên đọc đếch hiểu code bác làm kiểu gì luôn.
    Đã được chỉnh sửa lần cuối bởi Counter-Strike : 24-02-2008 lúc 12:21 AM.

  7. #7
    Ngày gia nhập
    06 2007
    Nơi ở
    UIT
    Bài viết
    44

    Chào bạn sau đây là ý tưởng của đoạn trên bạn nhé ! Mình thấy bạn nói về phần xóa lên mình chỉ làm phần xóa một nút có giá trị X trên cây nhị phân tìm kiếm ;

    Việc thực hiện được khi truyền vào một cây và một giá trị cần xóa ! Bắt đầu từ node gốc nếu cây rỗng thì kết thúc tìm kếm , Còn không so sánh giá trị của node gốc có nhỏ hơn giá trị cần xóa không
    + .Nếu giá trị tại node gốc nhỏ hơn thì thực tiếp việc xóa trên cây con bên phải của nút gốc vì node chứ giá trị X nếu có trên cây phải có vị trí bên phỉa cây nhi phân tìm kiếm cái này là do tính chất của cây nhị phân tìm kiếm.. Việc tìm kiếm lại bắt đầu với nút con bên phải node gốc trước đó làm node gốc của giai đoạn tìm kiếm đệ quy
    + Nếu giá trị tại node ở nút gốc lớn hơn giá trị xần xóa thì tương tự thực hiện đệ quy với cây con bên trái của node gốc
    Nếu không là một trong hai trường hợp trên thì giá trị tại node chính là giá trị cần xóa . Việc xóa phải bảo đàm sau khi xóa cây vẫn là cây nhị phân tìm kiếm lên các bước thực hiện như sau :
    Tạo một node phụ để lưu trữ node gốc sắp xóa : Kiểm tra tại node gốc nếu không có nhánh bên trái thì sau khi xóa có một node bên phải của cây con phải là node gốc của cây mới và ngược lại không có nhánh bên phải thì sau khi xóa có một node bên cây con trái là node gốc của cây mới . Nếu không rơi vào hai trường hợp trên thì chỉ việc xóa node gốc ;là xong bài toán .
    Bây giờ là việc tìm node thay thế trong một trong hai trường hợp trên và hàm thaythecach1 là cách giải quyết trong trường hợp này . Bây giờ ta bàn đến việc tìm phần tử thay thế sao thỏa mãn cây con sau khi thay hỏa mãn cây nhị phân tìm kiếm .(trong sách của mình nó nói là tìm phần tử thế mạng ) .
    Có 2 cách tìm phần tử thế mạng đó là tìm phần tử lớn nhất bên cây trái của node cần thay thế và phần tử nhỏ nhất bên cây phải của node
    Việc tìm phần tử thế mạng trong hàm được truyền vào tham chiếu 2 cây tức là hai nhánh nếu có của node con bên phải (hay trái tùy thuộc vào trường hợp trên) của node gốc. Kiểm tra nếu bên trái không node không null thì thực hiện việc dệ quy tiếp còn không tức là node trái bằng null thì node bên phải là node làm node thay thế tại vị trí ta cần xóa ! Việc này đảm bảo cho cây sau khi xóa là cây nhị phân tìm kiếm .

    Việc thực hiện bằng ơh]ơng pháp dệ quy như trên không bỏ sót trường hợp nào của bài toán .



    Lý thuyết nhiều quá phải không ? đọc cố gắng hiểu nếu vẫn thấy khó hiểu quá thì bạn mail cho mình, mình đưa bạn cái slice của trường mình bạn xem có đúng không ! Thân !

  8. #8
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Cái ý tưởng của cậu phải nói 1 câu như thế này " Phát minh lại cái bánh xe ". Tớ nghĩ là cậu nên đọc lại để lấy cái hướng mà người khác đã viết và được đánh giá là tối ưu ( hiện nay ).
    /* Chú ý lại chỗ cậu xóa cái node root nhé. Sai rồi kìa */

    Với cái ý của cậu tớ tóm gọn lại thế này :
    Để xóa 1 node ta xét 3 trường hợp sau :
    - Node cần xóa là node lá
    - Node cần xóa có 1 node con
    - Node cần xóa có 2 node con

    a/ Node cần xóa là node lá
    - Như cậu nói cho cha của nó trỏ đến NULL.
    - Cái khác là cậu phải hủy node này đi. Nếu ko nó sẽ làm lãng phí bộ nhớ.

    b/ Node cần xóa có 1 node con
    - Cậu đừng có chia lung tung . Vào đây rồi mới tính, đừng phân ra dễ làm lộn xộn lắm. Lúc này bắt đầu có các trường hợp như cậu trình bày.

    Code:
     If( current.rightchild == null ) // khuyết cây con phải
        if(current == root )
             root = current.leftchild;
        else if ( isLeftChild ) // parrent.leftChild == current
             parrent.leftChild = current.leftchild
        else
             parrent.rightChild = current.leftchild
     else if ( current.leftchild == null // khuyết cây con trái
      // tương tự
     else // Ko khuyết cây nào .
     ......
    c/ TH Có cả 2 nhánh

    - ý tưởng như cậu nói vậy, chẳng có gì khó khăn cả.
    Code:
     else
     {
         minRightTree = findMin(current->right); // tìm node nhỏ nhất cây con bên phải.  
         current->key = minRightTree->key;
         remove(minRightTree->key); // cái này gọi là đệ qui nè. Để xóa cái node cuối đi.
      }
    Thế nhé.

  9. #9
    Ngày gia nhập
    02 2008
    Bài viết
    18

    OK thank 2 bác Kid với bác vtien_uit cực nhiều luôn.
    iem đang cố gắng hiểu đây _ __!.

  10. #10
    Ngày gia nhập
    02 2008
    Bài viết
    18

    Code:
    void thaythecach1(Tree& p,Tree&t )
    {
    	if(t->left!=NULL)
    	thaythecach1(p,t->left);
    	else
    	{
    		p->key=t->key;
    		p=t;
    		t=t->right;
    	}
    }
    void deletetnodex(Tree& t,int x)
    {
    	if(t!=NULL)
    	{
    		if(t->key<x)
    		deletetnodex(t->right,x);
    		else
    		{
    			if(t->key>x)
    			deletetnodex(t->left,x);
    			else
    			{
    				TNode* p;
    				p=t;
    				if(t->left==NULL)
    				t=t->right;
    				else
    				{
    					if(t->right==NULL)
    					t=t->left;
    					else
    					thaythecach1(p,t->right);
    				}
    				delete p;
    			}
    		}
    	}
    	else
    	printf("\nKhong tim thay phan can xoa");
    }
    Thực sự em không hiểu Tree ở đây cả một cây nhị phân hay là chỉ là nột Node trong cây nhị phân, và TNode* p ở đây nghĩa là gì.
    Ý tưởng của bác thì em chỉ mờ mờ hiểu vì chưa hiểu các biến kể trên.
    Nếu có thể bác up cả code bài cây này cho em tham khảo.

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

  1. Bài tập C Xóa 1 nút trong cây nhị phân tìm kiếm
    Gửi bởi akiller12 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: 30-09-2013, 07:21 PM
  2. Giúp mình về xóa phần tử lá trong cây nhị phân tìm kiếm
    Gửi bởi bangdienc9 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 18-05-2012, 02:09 PM
  3. [Help]Lỗi kì lạ - Xóa một phần tử trong cây nhị phân tìm kiếm.
    Gửi bởi A a trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 16-05-2012, 09:51 AM
  4. Lập trình C++ xóa một phần tử trong cây nhị phân tìm kiếm
    Gửi bởi nhatnha trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 16-12-2010, 01:40 AM
  5. [LT][Tìm kiếm]Xóa node trong cây nhị phân tìm kiếm
    Gửi bởi schtroumpfs trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 05-06-2007, 05:47 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