iter.h

利用霍夫曼树进行文件压缩和解压

#pragma once

# include <iostream>
#include"huffmantree.h"
#include"stack.h"


using namespace std;


template <class Type> class Stack;

template <class Type> class ExtBinTree;

//扩展二叉树游标类节点
template <class Type> class StkNode {		
public:
    const ExtBinNode <Type> *Node;                       //结点指针
    int PopTim;                                           //退栈次数
    StkNode ( const ExtBinNode <Type>  *N = 
        NULL ) : Node (N), PopTim (0) { }                 //构造函数
};


//扩展二叉树游标类
template <class Type> class TreeIterator {
public:
    TreeIterator ( const ExtBinTree <Type> & BT ) :
                     T (BT), current (BT.root) { }	
    virtual ~TreeIterator ( ) { }
    virtual void First ( ) = 0;
    virtual void operator ++ ( ) = 0;
    const Type & operator ( ) ( ) const;
	void SettoRoot(){current = T.root;}
	Type  getD ( ) ;
	string getC(){ return current->GetCode();}
	bool Isleaf();        //判断是否是叶子
	bool Isin();          //判断是否在树中
	bool TurnLeft(){      //走到左子女处
		if(current==NULL||current->leftChild ==NULL)return false;
		current = current->leftChild; return true;
	}
    bool TurnRight(){     //走到右子女处
		if(current==NULL||current->rightChild ==NULL)return false;
		current = current->rightChild; return true;
	}
                
protected:
    const ExtBinTree <Type> & T;       //扩展二叉树引用
    const ExtBinNode <Type> * current; //游标
private:
    TreeIterator ( const TreeIterator & ) { }
    const TreeIterator & operator = ( const TreeIterator & );
};		

template <class Type>
bool TreeIterator <Type>::Isleaf(){                           //判断是否是叶子
	return( current != NULL && !current->GetLeft()&& !current->GetRight() );
}

template <class Type>
bool TreeIterator <Type>::Isin(){                             //判断是否在树中
	return (current != NULL);
}


template <class Type> const Type &TreeIterator
<Type> :: operator ( ) ( ) const {
    if ( current == NULL )
       { cout << "非法访问" << endl;  exit (1); }
    return current->GetData ( );
}

template <class Type>  Type TreeIterator
<Type> :: getD ( )  {
    if ( current == NULL )
       { cout << "非法访问" << endl;  exit (1); }
    return current->GetData ( );
}


//扩展二叉树后序游标类
template <class Type> class PostOrder : 
    public TreeIterator <Type> {
public:
    PostOrder ( const ExtBinTree <Type> & BT );
    ~PostOrder ( ) { }    
	void First ( );            //定位到后序次序下第一个结点
    void operator ++ ( );	   //定位到后序次序下的下一个结点 
                       
protected:
    Stack < StkNode<Type> > st;      //工作栈
};


template <class Type>PostOrder <Type>::
PostOrder (  const ExtBinTree <Type> & BT ) :
    TreeIterator <Type> (BT) {
        st.Push ( StkNode <Type> ( BT.GetRoot ( ) ) );
}

template <class Type> 
void PostOrder <Type>::First ( ) {
    st.MakeEmpty ( );
    if ( T.GetRoot ( ) != NULL ) 
      st.Push ( StkNode <Type> ( T.GetRoot ( ) ) );
      operator ++ ( );
}

template <class Type> 
void PostOrder <Type>::operator ++ ( ) {
     if ( st.IsEmpty ( ) ) {
        if ( current == NULL ) {
           cout << "已经遍历结束" << endl;  exit (1); 
        } 
		current = NULL;  return;     //遍历完成
     }
     StkNode <Type> Cnode;
     for (  ;  ;  ) {       //循环,找后序下的下一个结点
        Cnode = st.Pop ( );                 
        if ( ++Cnode.PopTim == 3 )  //从右子树退出 
           { current = Cnode.Node;  return; } 
        st.Push ( Cnode );                   //否则加一进栈
        if ( Cnode.PopTim == 1 ) {    //=1, 左子女进栈
           if ( Cnode.Node->GetLeft ( ) != NULL )
   	     st.Push ( StkNode <Type> (  Cnode.Node->GetLeft ( ) ) );
        }
        else {                  //=2,右子女进栈
          if ( Cnode.Node->GetRight ( ) != NULL )
 	    st.Push ( StkNode <Type> (  Cnode.Node->GetRight ( ) ) );
       }
    }
}