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

Đề tài: Nhập cây nhị phân tìm kiếm trên C++??

  1. #1
    Ngày gia nhập
    03 2009
    Bài viết
    1

    Mặc định Nhập cây nhị phân tìm kiếm trên C++??

    mình mới học C++, mình đang làm bài cây nhị phân nhưng phần nhập chưa được, mình đang loay hoay về con trỏ nhưng chưa được, mong các bạn giúp đỡ

    Code:
    #include<conio.h>
    #include<iostream.h>
    #include<stdio.h>
    #include<iomanip.h>
    
    class tree
    {
    private:
    	int key;
    	tree *trai;
    	tree *phai;
    public:
    	void nhap(tree *T);
    	void xet(tree *T,int x);
    	const tree&operator=(const tree &T);
    
    };
    
    const tree &tree::operator=(const tree &T)
    {
    key=T.key;
    trai=T.trai;
    phai=T.phai;
    
    return *this;
    }
    
    void tree::nhap(tree *T)
    {
    int n,x,i;
    
    cout<<"\n Nhap so luong phan tu:";cin>>n;
    
    for(i=0;i<n;i++)
    	{
    	cout<<"\n nhap so thu "<<i+1<<" : ";cin>>x;
    	xet(T,x);
    	}
    }
    
    	void tree::xet(tree *T,int x)
    	{
    
    	if(T==NULL)
    		{
    		T=new tree;
    		T->key=x;
    		T->trai=T->phai=NULL;
    		}
    	else
    		if(T->key==x)
    			{cout<<T->key;getch();return;}
    		else
    			if(T->key>x)
    				xet(T->trai,x);
    			else
    				xet(T->phai,x);
    	}
    void main()
    {
    clrscr();
    tree a;
    tree *T=NULL;
    a.nhap(T);
    
    cout<<"\n END";
    getch();
    }

  2. #2
    Ngày gia nhập
    05 2009
    Nơi ở
    ha noi
    Bài viết
    4

    Hoa cả mẳt .ko ai dúp hắn à ......

  3. #3
    Ngày gia nhập
    09 2009
    Bài viết
    24

    Red face cây tìm kiếm nhị phân

    Bạn có thể dùng chương trình này. Mình đã test thử rồi. (Minh viết bằng C) Có gì liên lạc qua mail minh: pnlongpro@gmail.com
    Code:
    /*Xay dung cay tim kiem nhi phan chua cac so nguyen
     -Dem so nut la
     -Dem so nut cua cay
     -Tinh chieu cao cua cay
     -Tim nut co khoa x
     -Them mot phan tu vao cay sao cho cay van la cay TKNP
     -In theo thu tu truoc sau giua
     -Xoa 1 node tren cay
    */
     
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    //---------------------------------------
        //Khai bao cau truc cho node
    //---------------------------------------
    struct Node
    {
        int info;
        Node *Left;//Node trai
        Node *Right;//Node phai
    }node;
    typedef Node *NodePtr;
     
    //----------------------------------------------
        //Cai dat cho cay tim kiem nhi phan
    //----------------------------------------------
    //Khoi tao cay nhi phan
    void init(NodePtr &pTree)
    {
        pTree=NULL;
    }
    //-----------------------------------------------
    //Cay rong
    int isEmpty(NodePtr pTree)
    {
        if(pTree==NULL)
         return 1;
        return 0;
    }
    //-------------------------------------------------
    //Cap phat 1 vung nho cho node
    NodePtr NewNode()
    {
        //--------------------------------------------------
    //Tao node moi co du lieu la x
    NodePtr CreateNode(int x)
    {
        NodePtr node;
        node=NewNode();
        node->info=x;
        node->Left=node->Right=NULL;
        return node;
    }
    //----------------------------------------------------
    //Ham giai phong cho node
    void FreeNode(NodePtr p)
    {
        free(p);
    }(x);
            pTree=p;
        }
        else
         if(x!=pTree->info)
            {
                    if(x<pTree->info)
                        Add(x,pTree->Left);
                    else
                        Add(x,pTree->Right);
            }
            else
                {
                    printf("So nay ban da nhap roi!!");
                    getch();
                    return;
                }
    }
    //----------------------------------------------------
    //Ham xoa mot node
    int delNode(NodePtr &pTree, int x)
    {
        if ( , x);
        NodePtr p, f, rp;
        p = pTree;
        if ( pTree->Left == NULL)
            pTree = pTree->Right;
        else if (pTree->Right == NULL)
            pTree = pTree->Left;
        else {
            f = p;
            rp = p->Right;
            while ( rp->Left != NULL)
            {
                f = rp;
                rp = rp->Left;
            }
            p->info = rp->info;
            if ( f == p)
                f->Right = rp->Right; //truong hop dac biet
            else
                f->Left = rp->Right;
            p = rp;
        }
    //Huy cay nhi phan
    void huyCay(NodePtr &pTree)
    {
        NodePtr p;
        if(pTree!=NULL)
        {
            huyCay(pTree->Left);
            huyCay(pTree->Right);
            FreeNode(p);
        }    {
            gotoxy(xm,d);
            printf("%4d",pTree->info);
            duyetNLR(pTree->Right,xm+x/2,x/2,d+2);
            duyetNLR(pTree->Left,xm-x/2,x/2,d+2);
        }
    }
    //-----------------------------------------------------
    //Tim kiem node co khoa x
    NodePtr search(int x,NodePtr pTree)
    {
        NodePtr p;
        if(isEmpty(pTree)) return NULL ;
        if(pTree->info==x)
            return pTree;
        if((p=search(x,pTree->Left))!=NULL)
            return p;
        return search(x,pTree->Right);
    }
    //-----------------------------------------------------
    //So la cua cay
    int soNutLa(NodePtr pTree)
    {
        if(isEmpty(pTree)) return NULL;
        if((pTree->Left==NULL)&&(pTree->Right==NULL))
            return 1;
        return soNutLa(pTree->Left) + soNutLa(pTree->Right);
    }
    //-----------------------------------------------------
    //Ham Max ho tro cho viec tim chieu cao cua cay
    int Max(int a,int b)
    {
        if(a>=b)
            return (a);
        else(pTree->Left),chieuCao(pTree->Right)));
    }
    //-------------------------------------------------------
    //Dem so nut cua cay
    int demNode(NodePtr pTree)
    {
        if(isEmpty(pTree))
            return 0;
         else
            return (1+demNode(pTree->Left)+demNode(pTree->Right));
    }
    //--------------------------------------------------------
    //Duyet cay theo thu tu giua
    void InOrder(NodePtr pTree)
    {
        if(!isEmpty(pTree))
        {
            InOrder(pTree->Left);
            printf("%3d",pTree->info);
            InOrder(pTree->Right);
        }
    }
    //----------------------------------------------------
    //Duyet theo thu sau
    void PostOrder(NodePtr pTree)
    {
        if(!isEmpty(pTree))
        {
            //-----------------------------------------------------
    //Chuong trinh chinh
    void main()
    {
        clrscr();
        int select;
        NodePtr pTree;
        init(pTree);
        do{
            clrscr();
            printf("======================================================\n");
            printf("+\tTRUONG CDCN HUE \n");
            printf("+\tKhoa CNTT \n");
            printf("+\tLOP K03THA1 \n");
            printf("+\Phan Ngoc Long \n");
            printf("=======================================================\n");
            printf("\t\t\nCHUONG TRINH MINH HOA CAY TIM KIEM NHI PHAN\n");
            printf("\t-------MENU---------\n");
            printf("\t1.Tao cay nhi phan\n");
            printf("\t2.Chen 1 node vao cay\n");
            printf("\t3.Tim kiem\n");
                    scanf("%d",&select);
            switch(select)
            {
                case 1:
                    int n;
                    int num;
                    printf("Nhap so luong phan tu:");
                    scanf("%d",&n);
                    for(int i=0;i<n;i++)
                    {
    -                    printf("Nhap phan tu %d:",i);
                        scanf("%d",&num);
                        Add(num,pTree);
                    }
                    break;
                case 2:
                     int x;
                     printf("Nhap phan tu can chen:");
                     scanf("%d",&x);
                     Add(x,pTree);
                     break;
                case 3:
                    int key;
                    pTree)!=NULL)
                    {
                        printf("Da ton tai");
                        getch();
                        break;
                    }
                    else
                    {
                        printf("Not Found!!!");
                        getch();
                        break;
                    }
                case 4:
                    clrscr();
                    if(isEmpty(pTree))
                    {
                        printf("\n\n\n\n\n\n\n");
                        printf("\t\t\tCay rong..!!!");
                    }
                    else
                    {
                        duyetNLR(pTree,40,10,2);
                        printf("\n\n\n\n\n");
                        printf("\n\nChieu cao cua cay:%d",chieuCao(pTree));
                        printf("\nSo nut la cua cay la:%d",soNutLa(pTree));
                        printf("\nCay co %d node",demNode(pTree));
                        printf("\nDuyet theo thu tu giua la:");
                                   case 5:
                    int key1;
                    printf("Nhap phan tu can xoa:");
                    scanf("%d",&key1);
                    if(delNode(pTree,key1)!=NULL)
                    {
                        printf("Delete success...");
                        getch();
                        break;
                    }
                    else
                    {
                       printf("Khong tim thay node can xoa");
                        getch();
                        break;
                    }
                case 6:
                    printf("Ban co muon huy toan bo cay Y/N:");
                    char tl=getch();
                    if(tl=='Y'||tl=='y')
                    {
                        huyCay(pTree);
                    }
                    break;
                getch();
    }
    Attached Files Attached Files
    Đã được chỉnh sửa lần cuối bởi pnlongpro : 01-08-2013 lúc 03:57 PM. Lý do: chua dinh kem file

  4. #4
    Ngày gia nhập
    09 2009
    Bài viết
    24

    khi sử dụng con trỏ ban phải khai báo đã

  5. #5
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Bạn có thể tham khảo chương trình sau.
    HTML Code:
    #include <iomanip.h> #include <conio.h> struct PNode {int Info; PNode *L,*R;}; // Cấu trúc của mỗi nút trên cây class Tree { PNode *P; public: void TreeCreate(); void TreeList(); void TreeDone(); }; // Bổ sung vào cây để khi duyệt ta nhận được dãy tăng dần PNode * App(PNode *Q,int x) { if (Q==NULL) { Q=new PNode; Q->Info=x; Q->L=NULL; Q->R=NULL; } else { if(Q->Info>x) Q->L=App(Q->L,x); else Q->R=App(Q->R,x); } return Q; } // Giải phóng phần bộ nhớ mà cây chiếm giứ PNode * Done(PNode *Q) { if ( Q!=NULL) { Q->L=Done(Q->L); Q->R=Done(Q->R); delete Q; Q=NULL; return Q; } } // Liệt kê các giá trị được lưu theo giải thuật Duyệt trái void List(PNode *Q) trước {if ( Q!=NULL) { List(Q->L); cout <<setw(8)<<Q->Info; List(Q->R); } } // Nhập các số nguyên từ bàn phím, kết thúc khi nhập giá trị 0 void Tree::TreeCreate() { int x; P=NULL; do { cout << "x= "; cin >>x; if (x!=0) P=App(P,x); } while (x); } void Tree::TreeList() { List(P);} void Tree::TreeDone() { P = Done(P);} int main() { Tree a; a.TreeCreate(); cout <<endl<<" The content of Tree is:"<<endl; a.TreeList(); a.TreeDone(); getch(); return 0; }

  6. #6
    Ngày gia nhập
    07 2010
    Bài viết
    8

    Mặc định Nhập cây nhị phân tìm kiếm trên C++??

    Đây là bài mình sưu tầm được về cây nhị phân tìm kiếm,bao gồm khởi tạo và chèn + xóa phần tử.Nhưng mình muốn biểu diễn 1 số biểu thức toán lên cây thì không biết làm thế nào(ví dụ a+(b-c)) vì cái code nảy chỉ cho phép hiển thi số trên cây.Ai biết chỉ mình với
    1)File main.cpp:
    #include <cstdlib>
    #include <iostream>
    #include "BST.h"
    using namespace std;

    void display(TreeItemType& anItem);

    int main(){

    BinarySearchTree tree;
    tree.searchTreeInsert(5);
    tree.searchTreeInsert(10);
    tree.searchTreeInsert(1);
    tree.searchTreeInsert(2);
    tree.searchTreeInsert(15);
    tree.searchTreeInsert(13);
    cout << "Day ban dau" << endl;
    tree.inorderTraverse(display);
    cout << endl;
    cout << "Xoa 1 phan tu" << endl;
    tree.searchTreeDelete(5);
    tree.inorderTraverse(display);
    cout << endl;
    system("pause");
    return 0;
    }

    void display(TreeItemType& anItem){
    cout << anItem << " ";
    }

    2) File BST.h

    #include <cstdlib>
    #include "TreeNode.h"

    typedef void (*FunctionType)(TreeItemType& anItem);

    class BinarySearchTree {
    public:
    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree& Tree);
    ~BinarySearchTree();

    bool isEmpty() const;
    void searchTreeInsert(const TreeItemType& newItem);
    void searchTreeDelete(KeyType searchKey);
    void searchTreeRetrieve(KeyType searchKey, TreeItemType& treeItem) const;
    void preorderTraverse(FunctionType visit);
    void inorderTraverse(FunctionType visit);
    void postorderTraverse(FunctionType visit);
    BinarySearchTree& operator=(const BinarySearchTree& rhs);
    private:
    void insertItem(TreeNode *& treePtr, const TreeItemType& newItem);
    void deleteItem(TreeNode *& treePtr, KeyType searchKey);
    void deleteNodeItem(TreeNode *& nodePtr);
    void processLeftmost(TreeNode *& nodePtr, TreeItemType& treeItem);
    void retrieveItem(TreeNode *treePtr, KeyType searchKey,
    TreeItemType& treeItem) const;
    void copyTree(TreeNode *treePtr, TreeNode *& newTreePtr) const;
    void destroyTree(TreeNode *& treePtr);
    void preorder(TreeNode *treePtr, FunctionType visit);
    void inorder(TreeNode *treePtr, FunctionType visit);
    void postorder(TreeNode *treePtr, FunctionType visit);

    TreeNode *rootPtr() const;
    void setRootPtr(TreeNode *newRoot);
    void getChildPtrs(TreeNode *nodePtr,
    TreeNode *& leftChildPtr,
    TreeNode *& rightChildPtr) const;
    void setChildPtrs(TreeNode *nodePtr,
    TreeNode *& leftChildPtr,
    TreeNode *& rightChildPtr);

    TreeNode *root;
    };

    3)file BST.cpp:
    #include <cstdlib>
    #include "BST.h"
    using namespace std;

    BinarySearchTree::BinarySearchTree():root(NULL) {}

    BinarySearchTree::BinarySearchTree(const BinarySearchTree& tree)
    {
    copyTree(tree.root,root);
    }

    BinarySearchTree::~BinarySearchTree()
    {
    destroyTree(root);
    }

    bool BinarySearchTree::isEmpty() const
    {
    return (root==NULL);
    }

    void BinarySearchTree::searchTreeInsert(const TreeItemType& newItem)
    {
    insertItem(root,newItem);
    }

    void BinarySearchTree::searchTreeDelete(KeyType searchKey)
    {
    deleteItem(root,searchKey);
    }

    void BinarySearchTree::searchTreeRetrieve(KeyType searchKey,
    TreeItemType& treeItem) const
    {
    retrieveItem(root,searchKey,treeItem);
    }

    void BinarySearchTree::preorderTraverse(FunctionType visit)
    {
    preorder(root,visit);
    }

    void BinarySearchTree::inorderTraverse(FunctionType visit)
    {
    inorder(root,visit);
    }

    void BinarySearchTree::postorderTraverse(FunctionType visit)
    {
    postorder(root,visit);
    }

    void BinarySearchTree::insertItem(TreeNode *& treePtr,
    const TreeItemType& newItem)
    {
    if(treePtr==NULL)
    treePtr=new TreeNode(newItem, NULL, NULL);
    else
    if(newItem < treePtr->item)
    insertItem(treePtr->leftChildPtr,newItem);
    else
    insertItem(treePtr->rightChildPtr,newItem);
    }

    void BinarySearchTree::deleteItem(TreeNode *& treePtr, KeyType searchKey)
    {
    if(treePtr!=NULL)
    {
    if(searchKey ==treePtr->item)
    deleteNodeItem(treePtr);
    else
    if(searchKey < treePtr->item)
    deleteItem(treePtr->leftChildPtr,searchKey);
    else
    deleteItem(treePtr->rightChildPtr,searchKey);
    }
    }

    void BinarySearchTree::deleteNodeItem(TreeNode *& nodePtr)
    {
    TreeNode *delPtr;
    TreeItemType repItem;

    //leaf
    if(nodePtr->leftChildPtr==NULL &&
    nodePtr->rightChildPtr==NULL)
    {
    delete nodePtr;
    nodePtr=NULL;
    }
    //no left child
    else if(nodePtr->leftChildPtr==NULL)
    {
    delPtr = nodePtr;
    nodePtr=nodePtr->rightChildPtr;
    delPtr->rightChildPtr=NULL;
    delete delPtr;
    }
    //no right
    else if(nodePtr->rightChildPtr==NULL)
    {
    delPtr = nodePtr;
    nodePtr=nodePtr->leftChildPtr;
    delPtr->leftChildPtr=NULL;
    delete delPtr;
    }
    //has two child
    else
    {
    processLeftmost(nodePtr->rightChildPtr,repItem);
    nodePtr->item = repItem;
    }
    }

    void BinarySearchTree::processLeftmost(TreeNode *& nodePtr,
    TreeItemType& treeItem)
    {
    if(nodePtr->leftChildPtr==NULL)
    {
    treeItem=nodePtr->item;
    TreeNode *delPtr=nodePtr;
    nodePtr=nodePtr->rightChildPtr;
    delPtr->rightChildPtr=NULL;
    delete delPtr;
    }
    else
    processLeftmost(nodePtr->leftChildPtr,treeItem);
    }

    void BinarySearchTree::retrieveItem(TreeNode *treePtr,
    KeyType searchKey,
    TreeItemType& treeItem) const
    {
    if(treePtr!=NULL)
    if(searchKey==treePtr->item)
    treeItem=treePtr->item;
    else if(searchKey < treePtr->item)
    retrieveItem(treePtr->leftChildPtr,searchKey,treeItem);
    else
    retrieveItem(treePtr->rightChildPtr,searchKey,treeItem);
    }





    void BinarySearchTree::copyTree(TreeNode *treePtr,
    TreeNode *& newTreePtr) const {
    if(treePtr != NULL)
    {
    newTreePtr = new TreeNode(treePtr->item,NULL,NULL);
    copyTree(treePtr->leftChildPtr,newTreePtr->leftChildPtr);
    copyTree(treePtr->rightChildPtr,newTreePtr->rightChildPtr);
    }
    }

    void BinarySearchTree::destroyTree(TreeNode *& treePtr){
    if(treePtr != NULL)
    {
    destroyTree(treePtr->leftChildPtr);
    destroyTree(treePtr->rightChildPtr);
    delete treePtr;
    treePtr=NULL;
    }
    }

    TreeNode *BinarySearchTree::rootPtr() const {
    return root;
    }

    void BinarySearchTree::setRootPtr(TreeNode *newRoot) {
    root = newRoot;
    }
    void BinarySearchTree::getChildPtrs(TreeNode *nodePtr,
    TreeNode *& leftPtr,
    TreeNode *& rightPtr) const {
    leftPtr = nodePtr->leftChildPtr;
    rightPtr = nodePtr->rightChildPtr;
    }

    void BinarySearchTree::preorder(TreeNode *treePtr,
    FunctionType visit) {
    if(treePtr != NULL)
    {
    visit(treePtr->item);
    preorder(treePtr->leftChildPtr,visit);
    preorder(treePtr->rightChildPtr,visit);
    }
    }

    void BinarySearchTree::inorder(TreeNode *treePtr,
    FunctionType visit) {
    if(treePtr != NULL)
    {
    inorder(treePtr->leftChildPtr,visit);
    visit(treePtr->item);
    inorder(treePtr->rightChildPtr,visit);
    }
    }

    void BinarySearchTree::postorder(TreeNode *treePtr,
    FunctionType visit) {
    if(treePtr != NULL)
    {
    postorder(treePtr->leftChildPtr,visit);
    postorder(treePtr->rightChildPtr,visit);
    visit(treePtr->item);
    }
    }

    Nhớ kĩ đây là Code cho DeV C++ hoặc visual C++,ghép 3 file trên vào 1 project là chạy được

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

  1. Lập trình trên nền tảng mobile nào kiếm được nhiều tiền nhất
    Gửi bởi FPTAptech trong diễn đàn Kinh nghiệm CNTT
    Trả lời: 0
    Bài viết cuối: 07-08-2013, 04:34 PM
  2. Kiếm tiền trên mạng uy tín nhất Việt Nam
    Gửi bởi bebittuot trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 28
    Bài viết cuối: 29-08-2012, 04:01 PM
  3. Nhấn enter để tự động tìm kiếm trên web
    Gửi bởi duytuyen26 trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 6
    Bài viết cuối: 09-11-2011, 12:01 PM
  4. tìm phần tử có khóa nhỏ nhất trên 1 cây nhị phân tìm kiếm
    Gửi bởi phanvuthuan 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: 12-01-2011, 12:25 AM
  5. Tìm kiếm trên C++ | Tìm kiếm sinh viên trên C++ | Cách xây dựng hàm tìm kiếm?
    Gửi bởi yentinh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 24-05-2009, 05:11 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