tree.h

这是清华大学出版社的《数据结构》的电子文档讲义

            return;												//已到下一个结点,返回
            }
        st.push(cNode);											//若退栈计数为1,重新压栈
        if(cNode.node->getLeft()!=NULL)							//若有左子树应先遍历,为此
            st.push(stackNode <Type>(cNode.node->getLeft()));	//左子树根指针压栈
        }
    }

template<class Type>class preOrder:public treeIterator<Type>{
	public:
      	preOrder(const binaryTree<Type>&BT);
      	~preOrder(){}
		void first();
      	void operator++();
    protected:
      	stackArray<const binTreeNode<Type>*>st;
    	};

template<class Type>preOrder<Type>::preOrder(const binaryTree<Type>& BT):
      treeIterator<Type>(BT){}								//调用父类构造函数构造无名对象
      //treeIterator <Type>(BT){st.push(BT.getRoot());}
template<class Type>void preOrder<Type>::first(){
    st.makeEmpty();
    if(t.getRoot())st.push(t.getRoot());
    operator++();											//完成后,current指向基树的根结点
    }
template<class Type>void preOrder<Type>::operator++(){
    if(st.isEmpty()) {            							//当栈空且current亦为空,则出错
        if(current==NULL){cerr<<"Advanced past end"<<endl;  exit(1);}
      	current=NULL;	return;								//当仅栈空,则遍历完成,置current为空后返回
      	}
	current=st.pop();										//否则,退出一个栈顶元素,即为当前结点
    if(current->getRight()!=NULL) st.push(current->getRight());		//若其右子非空,先压栈
    if(current->getLeft()!=NULL) st.push(current->getLeft());		//若其左子非空,再压栈
    }																//已到下一个结点,返回

template<class Type>class levelOrder:public treeIterator<Type>{
    public:
      	levelOrder(const binaryTree<Type>& BT);
		~levelOrder(){}
		void first();
      	void operator++();
    protected:
        queueArray<const binTreeNode<Type>*>qu;
    };

template<class Type>levelOrder<Type>::levelOrder(const binaryTree<Type>& BT)://构造函数
          treeIterator<Type>(BT){}		
//          treeIterator<Type>(BT){qu.enQueue(BT.getRoot());}		
template<class Type>void levelOrder<Type>::first(){							//初始化函数,完成后
	qu.makeEmpty();															//current指向基树的根
    if(t.getRoot())qu.enQueue(t.getRoot());
    operator++(); 
	}
template <class Type> void levelOrder <Type>::operator++(){
    if ( qu.isEmpty()){													//当栈空且current亦为空,则出错
    	if(current==NULL){cerr<<"Advanced past end"<<endl;  exit (1);}
        current=NULL;return;											//仅队空则遍历完成,置current为空后返回
        }
    current=qu.deQueue();												//否则,current指向退出队列的队头元素
    if(current-> getLeft() !=NULL)qu.enQueue(current->getLeft());		//若其左子非空,先进队
	if(current-> getRight() !=NULL)qu.enQueue(current->getRight());		//若其右子非空,再进队
	}																	//已到下一个结点,返回

//堆的相关程序=============================================================

template<class Type>class minPQ{
    public:
      	virtual void insert(const Type &)=0;							//参数元素加入优先队列
      	virtual int removeMin (Type &)=0;								//Type* 最优先元素出优先队列
	};

template<class Type>class minHeap:public minPQ<Type>{		//最小堆的类声明
	public:
  		minHeap(int maxSize);											//构造函数1:建立空堆
  		//minHeap(Type arr[ ],int n);									//构造函数
 		minHeap(array<Type>& arr);										//构造函数2
  		~minHeap(){}													//析构函数
  		const minHeap <Type> & operator=(const minHeap &R);				//堆复制赋值
  		void insert(const Type& x);										//原返回值类型为int 							//将x插人到最小堆中
  		int removeMin(Type & x);										//删除堆顶上的最小元素
  		int isEmpty()const{return currentSize==0;}						//判堆空
  		//int IsFull()const{return currentSize==maxHeapSize ;}			//判堆满
  		void makeEmpty(){currentSize=0;}								//置空堆
		array<Type> heap;												//存放最小堆元素的向量
	private:
  		//num{DefaultSize=10};
  		//Type * heap;											//存放最小堆中元素的数组
  		int currentSize ;                         				//最小堆中当前元素个数
      	int maxHeapSize ;										//最小堆最多允许元素个数
      	void filterDown(int i, int m) ;							//从i到m自顶向下进行调整成为最小堆
      	void filterUp(int i);									//从i到0自底向上进行调整成为最小堆
    };

template<class Type>minHeap<Type>::minHeap(int maxSize) 
//{maxHeapSize=DefaultSize<maxsize?m->Size ; DefaaltSize ;	//按参数给定堆最大体积
//    heap=new Type [maxHeapSize] ;							//创建堆存储空间heap[maxHeapSize]
	: heap(maxSize), maxHeapSize(maxSize), currentSize(0){}
//调用向量构造函数,当前大小为0
//template<class Type>minHeap<Type> ::minHeap(Type arr[ ],int n){
//maxHeapSize= DefaultSize<n?n:DefaaltSize ;				//按参数给定堆最大体积
//    heap=new Type [ maxHeapSize ] ;						//创建堆存储空间heap[maxHeapSize]
template<class Type>minHeap<Type>::minHeap(array<Type>& arr){
    heap(arr);
	maxHeapSize=currentSize=arr.length();					//复制堆向量,建立当前大小
    int currentPos=(currentSize-2)/2;       				//找最初调整位置:最后的分支结点编号
    while ( currentPos>=0){									//自底向上逐步扩大形成堆
    	filterDown(currentPos, currentSize-1);				//局部自上向下调整
        currentPos--;										//再向前换一个分支结点
        }
    }
template<class Type>void minHeap <Type>::filterDown(const int start, const int endOfHeap){
//私有函数:从结点start开始到EndOjHeap为止,自上向下比较,如果子女的值
//小于双亲结点的值,则相互交换,这样将一个集合局部调整为最小堆。
	int i=start, j=2*i+1;
	Type temp=heap[i];										//j是i的左子女位置,暂存结点i
	while(j<=endOfHeap){									//检查是否到最后位置
        if(j<endOfHeap && heap[j]>heap[j+1]) j++;			//让j指向两子女中的小者
        if(temp<=heap[j]) break;                    		//小则不做调整
        else {heap[i]=heap[j];								//否则小者上移,
			i=j; 											//i下降到j的位置
			j=2*j+1;}										//j下降到其左子位置
        }													//继续向下层比较
    heap[i]=temp ;											//temp中暂存的结点元素放到合适位置i
	}
template<class Type>void minHeap<Type>::filterUp(int start){
    			//私有函数:从结点start开始到结点0为止,自下向上比较,如果子女的值小
				//于双亲结点的值则相互交换,这样将集合重新调整为最小堆。
	int j=start,i=(j-1)/2;   Type temp=heap[j];
    while ( j>0){											//沿双亲结点路径向上直达根结点
        if ( heap[i]<=temp) break;							//双亲结点值小,不调整
    	else{heap[j]=heap[i];  j=i;  i=(i-1)/2;}			//双亲结点值大,调整
    	}
  	heap[j]=temp ;											//回送
}
template<class Type>void minHeap<Type>::insert (const Type &x){
  	//if ( currentSize=maxHeapSize) {cerr<<"Heap Full"<<endl; return 0;}		//堆满,返回0
  	if(currentSize==maxHeapSize) {
		maxHeapSize=currentSize+8; 									//堆满,
		heap.reSize(maxHeapSize);}									//加大堆
  	heap[currentSize]=x ;  											//插人
	filterUp(currentSize) ;											//向上调整
  	currentSize++;													//堆计数加1
    //return 1;
	}
template<class Type>int minHeap<Type>::removeMin(Type &x){
	if(! currentSize){cout<<"Heap empty"<<endl;  return 0; }  	//空堆,返回0
	x=heap[0];  													//引用参数x带回最小元素
	heap[0]=heap[currentSize-1];									//原来最后元素填补到根结点
    currentSize--;													//堆大小减1
    filterDown(0, currentSize-1 );									//自上向下调整为堆
    return 1;														//成功带回,返回1
    }

//3．扩充二叉树的类声明===================================================
template<class Type>class extBinTree;						//扩充二叉树的前视声明

template <class Type> class element {								//树结点的类定义
    friend class extBinTree;
    private:
      	Type data_key;												//结点数据,存权值或权值和
      	element <Type> * leftChild, * rightChild ;					//结点左、右子女指针
    };
template <class Type> class extBinTree{								//扩充二叉树类定义
    public:
      	extBinTree ( extBinTree <Type> & bt1, extBinTree <Type> & bt2){		//构造函数
        	root->leftChild=bt1.root;								//左子树为参数1
root->rightChild=bt2.root;											//右子树为参数2
        	root->data_key=btl.root->data_key + bt2.root->data_key;	//权值取左右权值之和
        	}
    protected:
      	int defaultSize;                            				//=20;  缺省权值集合大小
      	element <Type> * root;										//扩充二叉树的根
};

//4．构造霍夫曼树的函数====================================================
//在算法中使用了一个最小堆,利用它组织森林并从中选择根结点权值最小和次小的两棵树。
template<class Type>void hufmanTree (array<Type>frq, extBinTree<Type>& hfmtree){
    			//给出n个频度数据frq[0] ~frq[n-1],构造霍夫曼树,通过参数hfmtree返回。
	extBinTree<Type> & first,& second;
	int n=frq.length();
    array<extBinTree<Type> > node (n) ;						//n棵树组成的森林
    minHeap<extBinTree<Type> > hp;							//在算法中使用的最小堆,存放森林
    for (int i=0; i <n; i++) {								//各扩充二叉树初始化为单结点树
        node[i].root->data_key=frq[i];
        node[i].root->leftChild=node[i].root->rightChild=NULL;
        }
    hp.minHeap(node, n);									//建立存储扩充二叉树森林的最小堆
    for (int i=0; i <n-1; i++) {							//做n一1趟,逐步形成霍夫曼树
        hp.DeleteMin(first);hp.DeleteMin(second);			//选择根的权值最小和次小的两棵树
        hfmtree=new extBinTree<Type> (first, second);		//合并
        hp.insert(hfmtree);									//重新插人到最小堆中
        }
	}
/*原教材中的程序
template<class Type>void hufmanTree (Type * p,int n, extBinTree<Type>& newtree){
    			//给出n个频度数据fr[0] ~fr[n-1],构造霍夫曼树,通过参数newtree返回。
extBinTree<Type> & first,& second;
    extBinTree <Type> node [ DafualtSize ] ;                   //n棵树组成的森林
    minHeap <extBinTree <Type>> hp;				//在算法中使用的最小堆,存放森林
if(n>DefavltSize){
        cerr<<"Size n"<<n<<"exceeds the boundary of array"<<endl; 	return;
        }
    for (int i=0; i <n; i++) {						//各扩充二叉树初始化为单结点树
        node[i].root->data.key=t[i];
        node[i].root->leftChild=node[i].root->rightChild=NULL;
        }
    hp.minHeap(node, n);						//建立存储扩充二叉树森林的最小堆
    for (int i=0; i <n-1; i++) {						//做n一1趟,逐步形成霍夫曼树
        hp.DeleteMin(first);hp.DeleteMin(second);//选择根的权值最小和次小的两棵树
        newtree=new extBinTree<Type> (first, second);	//合并
        hp.insert(newtree);							//重新插人到最小堆中
        }
}
*/