滴水逆向联盟

标题: VC++2012编程演练数据结构《9》平衡二叉搜索树 [打印本页]

---

作者: 大灰狼    时间: 2014-9-15 08:29
标题: VC++2012编程演练数据结构《9》平衡二叉搜索树
平衡二叉搜索树

　　任何结点的左子树和右子树高度最多相差1的二叉搜索树。
　　（1）AVL树的插入算法
　　a. 插入结点之后仍然是AVL树，则不调整；
　　b. 插入结点之后不再满足AVL树条件，则进行调整，根据导致不平衡的原因，分为：
　　a) LL型――单旋转调整
　　b) LR型――双旋转调整
　　c) RL型――双旋转调整
　　d) RR型――单旋转调整
　　下图是顺序插入单词{cup，cop，copy，hit，hi，his，hia}后得到的AVL树，单词之间按照字典顺序比较：
　　（2）AVL树的删除算法
　　a. 删除过程如BST结点的删除算法

　　b. 删除后调整――从被删除的结点找到祖父结点，然后开始单旋转或多旋转操作，一次旋转结束并不 意味着树已经平衡，因为这可能会导致它的祖先结点发生新的不平衡。所以这样的调整操作要一直进行下去，直到树平衡为止。

类的实现如下

[cpp] view plaincopy

• //平衡二叉搜索树类定义与实现  
• template<class T> class BSTree;  
• //平衡二叉搜索树的结点类型定义  
• template<class T> struct TNode  
• {private:  
• TNode<T>  *left;//左子树指针  
• TNode<T> *right;//右子树指针  
• public:  
•     int balance;//平衡因子  
•     T data;//数据域  
•     friend class BSTree<T>;  
•     //构造函数  
•     TNode():left(NULL),right(NULL),balance(0){ }  
•     TNode(T item,TNode<T> *left1,TNode<T> *right1)  
•         :balance(0),data(item),left(left1),right(right1){ }  
• };  
• template<class T> class BSTree  
• {private:  
• int size;  
• public:  
•     //构造函数  
•     BSTree(TNode<T> *&root):size(0){root=NULL;}  
•     //被ClearBST()所调用的函数  
•     void DeleteTree(TNode<T> *&root);  
•     //LL型调整操作  
•     void LL(TNode<T> **a,TNode<T> **b);  
•     //RR型调整操作  
•     void RR(TNode<T> **a,TNode<T> **b);  
•     //LR型调整操作  
•     void LR(TNode<T> **a,TNode<T> **b);  
•     //RL型调整操作  
•     void RL(TNode<T> **a,TNode<T> **b);  
•     //释放空间  
•     void FreeBST(TNode<T> *&root);  
•     //求平衡二叉搜索树中所有结点数  
•     int BSTSize();  
•     //判断平衡二叉搜索树是否为空  
•     int BSTEmpty(TNode<T> *&root);  
•     //取根指针  
•     TNode<T> *GetRoot(TNode<T> *&root);  
•     //从平衡二叉搜索树中查找元素  
•     TNode<T> *BSTLocate(TNode<T> *&root,T item);  
•     //向平衡二叉搜索树中插入元素  
•     void BSTInsert(TNode<T> *&root,T item);  
•     //中序遍历平衡二叉搜索树中的所有结点  
•     void Inorder(TNode<T> *&root);  
•     //求平衡二叉搜索树的深度  
•     int BSTreeDepth(TNode<T> *&root);  
•     //求平衡二叉搜索树中所有结点数  
•     int BSTreeCount(TNode<T> *&root);  
•     //求平衡二叉搜索树中所有叶子结点数  
•     int BSTreeLeafCount(TNode<T> *&root);  
•     //清除平衡二叉搜索树，使之变为一棵空树  
•     void ClearBST(TNode<T> *&root);  
•     //初始化平衡二叉搜索树  
•     void SetTNode(TNode<T> *&root,T item);  
•     //获取设置的平衡二叉搜索树的一个结点  
•     TNode<T> *GetTNode(T item,TNode<T> *left,TNode<T> *right);  
• };  
• //平衡二叉搜索树的类实现  
• template<class T>  
• void BSTree<T>::DeleteTree(TNode<T> *&root)  
• {if(root==NULL) return;  
• if(root->left!=NULL)  
• DeleteTree(root->left);  
• if(root->right!=NULL)  
• DeleteTree(root->right);  
• free(root);  
• }  
• template<class T>  
• void BSTree<T>::LL(TNode<T> **a,TNode<T> **b)  
• {(*a)->balance=0;  
• (*a)->left=(*b)->right;  
• (*b)->balance=0;  
• (*b)->right=(*a);  
• }  
• template<class T>  
• void BSTree<T>::RR(TNode<T> **a,TNode<T> **b)  
• {(*a)->balance=0;  
• (*a)->right=(*b)->left;  
• (*b)->balance=0;  
• (*b)->left=(*a);  
• }  
• template<class T>  
• void BSTree<T>::LR(TNode<T> **a,TNode<T> **b)  
• {TNode<T> *c;  
• c=(*b)->right;//c是插入结点  
• (*a)->left=c->right;  
• (*b)->right=c->left;  
• c->left=(*b);  
• c->right=(*a);  
• switch(c->balance)  
• {case 0:(*a)->balance=0;  
• (*b)->balance=0;  
• break;  
• case 1:(*a)->balance=-1;//插入的结点在c的左子树  
•     (*b)->balance=0;  
•     break;  
• case -1:(*a)->balance=0;//插入的结点在c的右子树  
•     (*b)->balance=1;  
•     break;}  
• c->balance=0;  
• (*b)=c;//使b指向调整后的子树的根  
• }  
• template<class T>  
• void BSTree<T>::RL(TNode<T> **a,TNode<T> **b)  
• {TNode<T> *c;  
• c=(*b)->left; //c是插入结点  
• (*a)->right=c->left;  
• (*b)->left=c->right;  
• c->right=(*b);  
• c->left=(*a);  
• switch(c->balance)  
• {case 0:(*a)->balance=0;  
• (*b)->balance=0;  
• break;  
• case 1:(*a)->balance=0;//插入的结点在c的左子树  
•     (*b)->balance=-1;  
•     break;  
• case -1:(*a)->balance=1;//插入的结点在c的右子树  
•     (*b)->balance=0;  
•     break;}  
• c->balance=0;  
• (*b)=c;//使b指向调整后的子树的根  
• }  
• template<class T>  
• void BSTree<T>::FreeBST(TNode<T> *&root)  
• {DeleteTree(root);}  
• template<class T>  
• int BSTree<T>::BSTSize()  
• {return(size);}  
• template<class T>  
• int BSTree<T>::BSTEmpty(TNode<T> *&root)  
• {if(root==NULL) return(1);  
• else return(0);}  
• template<class T>  
• TNode<T> *BSTree<T>::GetRoot(TNode<T> *&root)  
• {return(root);}  
• template<class T>  
• TNode<T> *BSTree<T>::BSTLocate(TNode<T> *&root,T item)  
• {TNode<T> *t;  
• t=root;  
• while(t!=NULL)  
• {if(item==t->data) break;  
• else  
• if(item<t->data) t=t->left;  
• else t=t->right;}  
• return(t);  
• }  
• template<class T>  
• void BSTree<T>::BSTInsert(TNode<T> *&root,T item)  
• {TNode<T> *t,*p,*newN,*a,*b,*f;  
• newN=new TNode<T>;  
• newN->data=item;  
• if(root==NULL)  
• {root=newN;  
• size++;  
• return;}  
• t=root;p=NULL;  
• a=t;f=p;  
• while(t!=NULL)  
• {if(t->balance!=0)  
• {a=t;f=p;}  
• p=t;  
• if(item<t->data) t=t->left;  
• else t=t->right;}  
• if(item<p->data) p->left=newN;  
• else p->right=newN;  
• size++;  
• if(item<a->data)  
• {b=t=a->left;}  
• else {b=t=a->right;}  
• while(t!=NULL&&t->data!=item)  
• {if(item<t->data)  
• {t->balance=1;  
• t=t->left;}  
• else {t->balance=-1;t=t->right;}}  
• if(a->balance==0)  
• {if(item<a->data) a->balance=1;  
• else a->balance=-1;  
• return;}  
• else  
• if(item<a->data&&a->balance==-1||  
•    item>a->data&&a->balance==1)  
• {a->balance=0;return;}  
• else  
• {if(a->balance==1)  
• if(b->balance==1)  
• LL(&a,&b);  
• else LR(&a,&b);  
• else  
• if(b->balance==-1) RR(&a,&b);  
• else RL(&a,&b);}  
• if(f==NULL) root=b;  
• else  
• {if(f->left==a) f->left=b;  
• else f->right=b;}  
• }  
• template<class T>  
• void BSTree<T>::Inorder(TNode<T> *&root)  
• {if(root!=NULL) {  
•     Inorder(root->left);  
•     cout<<setw(2)<<root->data;  
•     Inorder(root->right);}  
• }  
• template<class T>  
• int BSTree<T>::BSTreeDepth(TNode<T> *&root)  
• {if(root==NULL) return 0;  
• else  
• {  //计算左子树的深度  
•     int dep1=BSTreeDepth(root->left);  
•     //计算右子树的深度  
•     int dep2=BSTreeDepth(root->right);  
•     //返回树的深度  
•     if(dep1>dep2) return dep1+1;  
•     else return dep2+1;}  
• }  
• template<class T>  
• int BSTree<T>::BSTreeCount(TNode<T> *&root)  
• {if(root==NULL) return 0;  
• else   
• return BSTreeCount(root->left)+BSTreeCount(root->right)+1;  
• }  
• template<class T>  
• int BSTree<T>::BSTreeLeafCount(TNode<T> *&root)  
• {if(root==NULL) return 0;  
• else  
• if(root->left==NULL && root->right==NULL) return 1;  
• else  
• return BSTreeLeafCount(root->left)+BSTreeLeafCount(root->right);  
• }  
• template<class T>  
• void BSTree<T>::ClearBST(TNode<T> *&root)  
• {DeleteTree(root);  
• root=NULL;  
• size=0;  
• }  
• template<class T>  
• void BSTree<T>::SetTNode(TNode<T> *&root,T item)  
• {root->data=item;  
• root->balance=0;  
• root->left=NULL;  
• root->right=NULL;  
• }  
• template<class T>  
• TNode<T>* BSTree<T>::GetTNode(T item,TNode<T> *left,TNode<T> *right)  
• {TNode<T> *ptr;  
• ptr=new TNode<T>;  
• ptr->data=item;  
• ptr->balance=0;  
• ptr->left=left;  
• ptr->right=right;  
• return(ptr);  
• }  
  

调用如下

[cpp] view plaincopy

• #include<conio.h>  
• #include<stdlib.h>  
• #include "AVLTREE.h"  
• using namespace std;  
• TNode<char> *q;  
• void main()  
• {cout<<"运行结果:\n";  
• int i;  
• char test[50]="abxyMNcdefgqwertyuizxcvbnm";  
• BSTree<char> t(q);  
• //cout<<"input data:\n";  
• //gets(test);  
• for(i=0;test!='\0';i++)  
• t.BSTInsert(q,test);  
• cout<<"平衡二叉搜索树的结点数="<<t.BSTSize()<<endl;  
• cout<<"平衡二叉搜索树的结点数="<<t.BSTreeCount(q)<<endl;  
• cout<<"平衡二叉搜索树的深度="<<t.BSTreeDepth(q)<<endl;  
• cout<<"平衡二叉搜索树的叶子结点数="<<t.BSTreeLeafCount(q)<<endl;  
• cout<<"中序遍历平衡二叉搜索树:\n";  
• t.Inorder(q);  
• getch();  
• t.FreeBST(q);  
• }  
  

效果如下

---

欢迎光临 滴水逆向联盟 (http://www.dtdebug.com/)

Powered by Discuz! X3.2