logo资料库

C++实现AVL树.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.03M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    #include #include using namespace std; bool unbalanced=false; template struct node { S data; int bf; node *lchild ; node *rchild; }; template class BST { public: node* Search(S k,node *F); void AVLInsert(node *&T,S R); void PreOrder(node *p); void Inorder(node*p); void Postorder(node*p); void LevelOrder(node*p); private: void LeftRotation(node * &T); void RightRotation(node* &T); }; template node*BST::Search (S k,node* F) { if(F==NULL) return NULL; else if (k==F->data) return F; else if(kdata) return(Search(k,F->lchild)); else return(Search(k,F->rchild)); } template void BST::AVLInsert(node*&T,S R) { if(!T) {
    unbalanced=true; T=new node; T->data=R; T->lchild=T->rchild=NULL; T->bf=0; } else if(Rdata) { AVLInsert(T->lchild,R); if(unbalanced) { switch (T->bf) { case -1:T->bf=0; unbalanced=false; break; case 0:T->bf=1; break; case 1:LeftRotation(T); } } } else if(R>T->data) { AVLInsert(T->rchild,R); if(unbalanced) { switch(T->bf) { case 1:T->bf=0; unbalanced=false; break; case 0:T->bf=-1; break; case -1:RightRotation(T); } } else unbalanced=false; } } template
    void BST::LeftRotation(node* &T) { node* lc; node* gc; lc=T->lchild; if(lc->lchild) { T->lchild=lc->rchild; lc->rchild=T; T->bf=0; T=lc; } else { gc=lc->rchild; lc->rchild=gc->lchild; gc->lchild=lc; T->lchild=gc->rchild; gc->rchild=T; switch(gc->bf) { case 1:T->bf=-1; lc->bf=0;break; case 0: T->bf=lc->bf=0; break; case -1:T->bf=0; lc->bf=1; } T=gc; } T->bf=0; unbalanced=false; } template void BST::RightRotation(node* &T) { node* gc; node* lc; lc=T->rchild; if(lc->rchild) { T->rchild=lc->lchild; lc->lchild=T;
    T->bf=0; T=lc; } else { gc=lc->lchild; lc->lchild=gc->rchild; gc->rchild=lc; T->rchild=gc->lchild; gc->lchild=T; switch(gc->bf) { case 1:T->bf=-1; lc->bf=0;break; case 0: T->bf=lc->bf=0; break; case -1:T->bf=0; lc->bf=1; } T=gc; } T->bf=0; unbalanced=false; } template void BST::PreOrder(node*p) { //先序遍历 if(p) { } } cout<data<<" "; PreOrder(p->lchild); PreOrder(p->rchild); template void BST::Inorder(node*p) { if(p) { Inorder(p->lchild); cout<data<<" "; Inorder(p->rchild);
    } } template void BST::Postorder(node*p) { if(p) { } Postorder(p->lchild); Postorder(p->rchild); cout<data<<" "; } template void BST::LevelOrder(node *tree) { queue*> q; node *newtree = tree; if(newtree!=NULL) q.push(newtree); while(!q.empty()) { newtree = q.front(); q.pop(); cout << newtree->data << " "; if(newtree->lchild!=NULL) q.push(newtree->lchild); if(newtree->rchild!=NULL) q.push(newtree->rchild); } } int main() { BST A; int p, q; cout << "input number(<0 stop):" << endl; cin >> p; node *a = NULL; node *b; while(p>=0) { A.AVLInsert(a, p);
    cin >> p; } cout <<"get the tree:"<< endl; A.PreOrder(a); cout << endl; A.Inorder(a); cout<> q; b = A.Search(q, a); if (b) cout << "b address:" << b << endl; else cout << "search error" << endl; system("pause"); return 0; } /* input number(<0 stop): 1 2 3 4 5 6 7 8 9 -1 get the tree: 4 2 1 3 6 5 8 7 9 1 2 3 4 5 6 7 8 9 1 3 2 5 7 9 8 6 4 4 2 6 1 3 5 8 7 9 input search number 3 b address:005B94E0 //先序遍历 //中序遍历 //后序遍历 //层序遍历 树的结构： 4 2 1 3 6 5 8 7 9
    请按任意键继续. . . */
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料