描述4.txt

13、堆 MinHeap.h test.cpp 14、哈夫曼树 BinTreeNode.h BinaryTree.h MinHeap.h Huffman.h Test.

template<typename Type> void LinkQueue<Type>::MakeEmpty(){
	QueueNode<Type> *pdel;
	while(m_pfront){
		pdel=m_pfront;
		m_pfront=m_pfront->m_pnext;
		delete pdel;
	}
}

template<typename Type> void LinkQueue<Type>::Append(const Type item){
	if(m_pfront==NULL){
		m_pfront=m_prear=new QueueNode<Type>(item);
	}
	else{
		m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
	}
}

template<typename Type> Type LinkQueue<Type>::Delete(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	QueueNode<Type> *pdel=m_pfront;
	Type temp=m_pfront->m_data;
	m_pfront=m_pfront->m_pnext;
	delete pdel;
	return temp;
}

template<typename Type> Type LinkQueue<Type>::GetFront(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pfront->m_data;
}

template<typename Type> void LinkQueue<Type>::Print(){
	QueueNode<Type> *pmove=m_pfront;
	cout<<"front";
	while(pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->rear"<<endl<<endl<<endl;
}

TreeNode.h

template<typename Type> class Tree;

template<typename Type> class TreeNode{
public:
	friend class Tree<Type>;

private:
	Type m_data;
	TreeNode<Type> *m_pfirst,*m_pnext;
	TreeNode():m_pfirst(NULL), m_pnext(NULL){}
	TreeNode(Type item, TreeNode<Type> *first = NULL, TreeNode<Type> *next = NULL)
		:m_data(item), m_pfirst(first), m_pnext(next){}
};

Tree.h

#include "TreeNode.h"
#include "LinkQueue.h"

template<typename Type> class Tree{
public:
    Tree():m_proot(NULL), m_pcurrent(NULL){}
public:
    TreeNode<Type> *GetCurrent(){	//Get the current node
        return m_pcurrent;
    }
    void SetCurrent(TreeNode<Type> *current){	//set the current node
        m_pcurrent = current;
    }
    bool Insert(Type item);		//insert an new node to current node
    void Remove(Type item);		//delete the node whose data is equal to item
    void Remove(TreeNode<Type> *current);	//delete the node
    bool Find(Type item);		//find the node whose data is equal to item
    void PrintChild(TreeNode<Type> *current);	//print the child tree
    TreeNode<Type> *Parent(TreeNode<Type> *current);	//get the parent

    void Print();				//print the tree
    void PreOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root first
    void PostOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root last
    void LevelOrder(TreeNode<Type> *root);	//ordering the tree by level
    void PreOrder();
    void PostOrder();
    void LevelOrder();

private:
   TreeNode<Type> *m_proot,*m_pcurrent;	
    bool Find(TreeNode<Type> *root, Type item);
    void Remove(TreeNode<Type> *root, Type item);
    TreeNode<Type> *Parent(TreeNode<Type> *root, TreeNode<Type> *current);
    void Print(TreeNode<Type> *start, int n=0);
};

template<typename Type> bool Tree<Type>::Insert(Type item){
    TreeNode<Type> *newnode = new TreeNode<Type>(item);
    if (NULL == newnode){
        cout << "Application Error!" <<endl;
        exit(1);
    }
    if (NULL == m_proot){
        m_proot = newnode;
        m_pcurrent = m_proot;
        return 1;
    }
    if (NULL == m_pcurrent){
        cerr << "insert error!" <<endl;
        return 0;
    }

    if(NULL == m_pcurrent->m_pfirst){
        m_pcurrent->m_pfirst = newnode;
        m_pcurrent = newnode;
        return 1;
    }
    TreeNode<Type> *pmove = m_pcurrent->m_pfirst;
    while(pmove->m_pnext){
        pmove = pmove->m_pnext;
    }
    pmove->m_pnext = newnode;
    m_pcurrent = newnode;
    return 1;

}

template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *current){
    if(NULL == current){
        return;
    }
    TreeNode<Type> *temp = Parent(current);
    if(NULL == temp){
        TreeNode<Type> *pmove = current->m_pfirst;
        if(NULL != pmove->m_pfirst){
            pmove=pmove->m_pfirst;
            while(pmove->m_pnext){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pfirst->m_pnext;
            current->m_pfirst->m_pnext = NULL;
        }
        else{
            pmove->m_pfirst = pmove->m_pnext;
        }
        m_proot = current->m_pfirst;
    }
    else{
        if(temp->m_pfirst == current){
            TreeNode<Type> *pmove = current->m_pfirst;
            if (pmove){
                while (pmove->m_pnext){
                    pmove = pmove->m_pnext;
                }
                pmove->m_pnext = current->m_pnext;
            }
            else{
                current->m_pfirst = current->m_pnext;
            }

        }
        else{
            TreeNode<Type> *pmove = temp->m_pfirst;
            while(pmove->m_pnext != current){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pnext;
            while(pmove->m_pnext){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pfirst;
        }
    }
    delete current;
}

template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *root, Type item){
    if(NULL == root){
        return;
    }
    if(root->m_pfirst){
        TreeNode<Type> *pmove=root->m_pfirst;
        while(pmove){
            Remove(pmove, item);
            pmove = pmove->m_pnext;
        }
    }	
    if(root->m_data == item){
        Remove(root);
    }

}
template<typename Type> void Tree<Type>::Remove(Type item){
    return Remove(m_proot, item);
}

template<typename Type> TreeNode<Type>* Tree<Type>::Parent(
    TreeNode<Type> *root, TreeNode<Type> *current){
        if(NULL == root){
            return NULL;
        }
        TreeNode<Type> *pmove=root->m_pfirst,*temp;
        if(NULL != pmove){
            while(pmove){
                if(pmove == current){
                    return root;
                }
                pmove = pmove->m_pnext;
            }
        }
        pmove = root->m_pfirst;
        while(pmove){
            temp = Parent(pmove, current);
            if(temp){
                return temp;
            }
            pmove = pmove->m_pnext;
        }
        return NULL;
}

template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *current){
    return Parent(m_proot,current);
}

template<typename Type> void Tree<Type>::PrintChild(TreeNode<Type> *current){
    TreeNode<Type> *pmove = current->m_pfirst;
    cout<<"first";
    if(NULL != pmove){
        cout<<"--->"<<pmove->m_data;
    }
    while(pmove->m_pnext){
        cout<<"--->"<<pmove->m_data;
        pmove = pmove->m_pnext;
    }
}

template<typename Type> bool Tree<Type>::Find(TreeNode<Type> *root, Type item){
    if (root->m_data == item){
        return 1;
    }
    if (NULL == root){
        return 0;
    }
    TreeNode<Type> *pmove=root->m_pfirst;
    if (NULL == pmove){
        return 0;
    }
    while (pmove){
        if (Find(pmove, item)){
            return 1;
        }
        pmove = pmove->m_pnext;
    }
    return 0;
}

template<typename Type> bool Tree<Type>::Find(Type item){
    return Find(m_proot,item);
}

template<typename Type> void Tree<Type>::Print(TreeNode<Type> *start, int n = 0){
    if (NULL == start){
        for (int i=0; i<n; i++){
            cout << "     ";
        }
        cout << "NULL" << endl;
        return;
    }
    TreeNode<Type> *pmove = start->m_pfirst;
    Print(pmove, n+1);

    for (int i=0; i<n; i++){
        cout << "     ";
    }
    cout << start->m_data << "--->" <<endl;

    if (NULL == pmove){   
        return;
    }
    pmove = pmove->m_pnext;
    while (pmove){
        Print(pmove, n+1);
        pmove = pmove->m_pnext;
    }
}

template<typename Type> void Tree<Type>::Print(){
    Print(m_proot);
}

template<typename Type> void Tree<Type>::PreOrder(TreeNode<Type> *root){
    if (NULL == root){
        return;
    }
    cout << root->m_data;
    TreeNode<Type> *pmove = root->m_pfirst;
    while (pmove){
        PreOrder(pmove);
        pmove = pmove->m_pnext;
    }
}

template<typename Type> void Tree<Type>::PostOrder(TreeNode<Type> *root){
    if (NULL == root){
        return;
    }
    TreeNode<Type> *pmove = root->m_pfirst;
    while (pmove){
        PostOrder(pmove);
        pmove = pmove->m_pnext;
    }
    cout << root->m_data;
}

template<typename Type> void Tree<Type>::PreOrder(){
    PreOrder(m_proot);
}

template<typename Type> void Tree<Type>::PostOrder(){
    PostOrder(m_proot);
}

template<typename Type> void Tree<Type>::LevelOrder(TreeNode<Type> *root){	//using queue
    LinkQueue<TreeNode<Type> *> queue;
    TreeNode<Type> *pmove, *ptemp;
    if (root != NULL){
        queue.Append(root);
        while (!queue.IsEmpty()){
            ptemp = queue.Delete();
            cout << ptemp->m_data;
            pmove = ptemp->m_pfirst;
            while(pmove){
                queue.Append(pmove);
                pmove = pmove->m_pnext;
            }
        }
    }
}

template<typename Type> void Tree<Type>::LevelOrder(){
    LevelOrder(m_proot);
}

test.cpp

#include <iostream>

using namespace std;

#include "Tree.h"

int main(){
	Tree<int> tree;
    int init[10]={3,6,0,2,8,4,9,1,5,7};
    for (int i=0; i<10; i++){
	    tree.Insert(init[i]);
        if (1 == i % 2){
            tree.SetCurrent(tree.Parent(tree.GetCurrent()));
        }
    }
    tree.Print();
    cout << endl <<endl << endl;
    
    tree.Remove(3);
    tree.Print();
    cout << endl <<endl << endl;

    cout << tree.Find(5) << endl << tree.Find(11) <<endl;
    
    tree.PreOrder();
    cout << endl;
    tree.PostOrder();
    cout << endl;
    tree.LevelOrder();
	return 0;
}
16、B+树

BTreeNode.h

template<typename Type> class BTree;

template<typename Type> class BTreeNode{
public:
    friend BTree<Type>;
    BTreeNode(): m_nMaxSize(0), m_ptr(NULL), m_pparent(NULL){}
    BTreeNode(int size): m_nsize(0), m_nMaxSize(size), m_pparent(NULL){
        m_pkey = new Type[size+1];
        m_ptr = new BTreeNode<Type> *[size+1];
        for (int i=0; i<=size; i++){
            m_ptr[i] = NULL;
            m_pkey[i] = this->m_Infinity;
        }
    }
    void Destroy(BTreeNode<Type> *root);
    ~BTreeNode(){
		if (m_nMaxSize){
			delete[] m_pkey;
			for (int i=0; i<=m_nMaxSize; i++){
				m_ptr[i] = NULL;
			}
		}
    }
    bool IsFull(){
        return m_nsize == m_nMaxSize;
    }
    Type GetKey(int i){
        if (this){
            return this->m_pkey[i];
        }
        return -1;
    }

private:
    int m_nsize;
    int m_nMaxSize;     //the Max Size of key
    Type *m_pkey;
    BTreeNode<Type> *m_pparent;
    BTreeNode<Type> **m_ptr;
    static const Type m_Infinity = 10000;
};

template<typename Type> struct Triple{
    BTreeNode<Type> *m_pfind;
    int m_nfind;
    bool m_ntag;
};

template<typename Type> void BTreeNode<Type>::Destroy(BTreeNode<Type> *root){
    if (NULL == root){
        return;
    }
    for (int i=0; i<root->m_nsize; i++){
        Destroy(root->m_ptr[i]);
    }
    delete root;
}

BTree.h

#include "BTreeNode.h"


template<typename Type> class BTree{
public:
    BTree(int size): m_nMaxSize(size), m_proot(NULL){}
    ~BTree();
    Triple<Type> Search(const Type item);
    int Size();
    int Size(BTreeNode<Type> *root);
    bool Insert(const Type item);   //insert item
    bool Remove(const Type item);   //delete item
    void Print();                   //print the BTree
    BTreeNode<Type> *GetParent(const Type item);    

private:
    //insert the pright and item to pinsert in the nth place;
    void InsertKey(BTreeNode<Type> *pinsert, int n, const Type item, BTreeNode<Type> *pright); 

    void PreMove(BTreeNode<Type> *root, int n); //move ahead
    
    //merge the child tree
    void Merge(BTreeNode<Type> *pleft, BTreeNode<Type> *pparent, BTreeNode<Type> *pright, int n); 

    //adjust with the parent and the left child tree
    void LeftAdjust(BTreeNode<Type> *pright, BTreeNode<Type> *pparent, int min, int n);