#ifndefTREE_H_INCLUDED#defineTREE_H_INCLUDED#include<string>#include<stack>usingnamespacestd;typedefcharElemType;typedefintElemHfm;typedefstructTreeNode{ElemTypedata; intltag,rtag;//線索標(biāo)志structTreeNode*lchild;structTreeNode*rchild;}BTree,*PBTree;typedefstruct{ ElemHfmdata; floatweight; intparent; intlchild; intrchild;}HTNode;//哈夫曼樹的構(gòu)造classTree{ PBTreepre;//指向當(dāng)前子樹的前驅(qū)節(jié)點(diǎn) PBTreecreate_fam(charpre[],charin[],intn); PBTreecreate_map(charpost[],charin[],intn); voidvisitTreeNode_f(PBTreet); voidvisitTreeNode_m(PBTreet); voidvisitTreeNode_p(PBTreet); voidThread(PBTreet);//對(duì)一棵樹進(jìn)展線索化public:Tree(){};PBTreeCreateBTree(chars[],chart[],intselect);//select=0,1,2時(shí)分別是先中后序 voidvisitTreeNode(PBTreet,intselect); PBTreeCreateThread(PBTreet);//中序線索化二叉樹 voidvisitInOrder(PBTreet);//中序遍歷線索二叉樹};classHFMTree{public: voidCreateHT(HTNodeht[],intn);};#endif//TREE_H_INCLUDED#include"Tree.h"#include<iostream>PBTreeTree::create_fam(charpre[],charin[],intn){intp,k;PBTrees;p=k=0; if(n==0)returnNULL;for(p=0;p<n;++p){if(pre[0]==in[p]){ k=p;break;}}s=newBTree();s->data=pre[0];s->lchild=create_fam(pre+1,in,k);s->rchild=create_fam(pre+k+1,&in[p]+1,n-k-1);returns;}PBTreeTree::create_map(charpost[],charin[],intn){ intp,maxpos; PBTrees=NULL; maxpos=n-1; if(n<=0)returnNULL; for(p=0;p<n;++p) { if(in[p]==post[maxpos]) { break; } } s=newBTree(); s->data=post[maxpos]; s->lchild=create_map(post,in,p); s->rchild=create_map(post+p,&in[p]+1,n-p-1); returns;}PBTreeTree::CreateBTree(chars[],chart[],intselect){ switch(select) { case0: returncreate_fam(s,t,strlen(s)); case1: returncreate_map(s,t,strlen(s)); default:returnNULL; }}voidTree::visitTreeNode_f(PBTreet){ stack<PBTree>St; PBTreep; if(t) {//先序遍歷的時(shí)候先讓右孩子進(jìn)棧，在進(jìn)左孩子，那么出棧的時(shí)候會(huì)先出左孩子，符合遍歷樹的要求。 St.push(t); while(!St.empty()) { p=St.top(); St.pop();//出棧 cout<<p->data<<""; if(p->rchild)//假設(shè)有右孩子 { St.push(p->rchild); } if(p->lchild)//假設(shè)有左孩子 { St.push(p->lchild); } }; }}voidTree::visitTreeNode_m(PBTreet){ stack<PBTree>St; PBTreep; if(t) { p=t; while(!St.empty()||p) { while(p)//一直向左 { St.push(p); p=p->lchild; } if(!St.empty())// { p=St.top(); St.pop();// cout<<p->data<<"";//輸出 p=p->rchild;//key } } }}voidTree::visitTreeNode_p(PBTreet){ stack<PBTree>St; PBTreep,q; intflag; if(t) { p=t; do { while(p) { St.push(p); p=p->lchild; } q=NULL; flag=1; while(!St.empty()&&flag)//每次向右轉(zhuǎn)后在向最左轉(zhuǎn) { p=St.top(); if(p->rchild==q)//右孩子不存在或右孩子已經(jīng)被訪問。 { cout<<p->data<<""; q=p;//假設(shè)p的右子樹被訪問過，那么q指向p St.pop(); } else { p=p->rchild; flag=0; } } }while(!St.empty()); }}voidTree::visitTreeNode(PBTreet,intselect){ switch(select) { case0: visitTreeNode_f(t); break; case1: visitTreeNode_m(t); break; case2: visitTreeNode_p(t); default:break; }}voidTree::Thread(PBTreet)//中序遍歷{ if(t) { Thread(t->lchild); if(t->lchild==NULL) { t->lchild=pre;//假設(shè)左子樹空了，那么使其指向前驅(qū) t->ltag=1; } elset->ltag=0; if(pre->rchild==NULL)//因?yàn)檫@里需要前驅(qū)節(jié)點(diǎn)指向，所以增加了一個(gè)虛擬節(jié)點(diǎn) { pre->rchild=t; pre->rtag=1; } elsepre->rtag=0; pre=t; Thread(t->rchild); }}PBTreeTree::CreateThread(PBTreet){ PBTreeroot;//一個(gè)根節(jié)點(diǎn) root=newBTree();//創(chuàng)立頭節(jié)點(diǎn) root->ltag=0,root->rtag=1;//初始化頭節(jié)點(diǎn) root->rchild=t;//讓root的右子樹指向跟結(jié)點(diǎn) if(!t) { root->rchild=root;//假設(shè)所指子樹為空那么回指 } else { root->lchild=t; pre=root;//在調(diào)用Thread之前一定要初始化pre Thread(t); pre->rchild=root; pre->rtag=1; root->rchild=pre; } returnroot;}voidTree::visitInOrder(PBTreet)//這里傳入的是根節(jié)點(diǎn)，不是樹的第一個(gè)節(jié)點(diǎn){ PBTreep=t->lchild;//p指向樹的第一個(gè)節(jié)點(diǎn) if(p) { while(p!=t) { while(p->ltag==0)p=p->lchild;//找到第一個(gè)節(jié)點(diǎn) cout<<p->data<<""; while(p->rtag==1&&p->rchild!=t)//假設(shè)有子樹為空那么可以一直找到其中序遍歷的后繼 { p=p->rchild; cout<<p->data<<""; } p=p->rchild; } }}voidHFMTree::CreateHT(HTNodeht[],intn){ inti,j,k,lnode,rnode; intmin1,min2; for(i=0;i<2*n-1;++i)ht[i].parent=-1;//初始化所有節(jié)點(diǎn)的父節(jié)點(diǎn)都為-1 for(i=n;i<2*n-1;++i) { min1=min2=32767; lnode=rnode=-1; for(j=0;j<i-1;++j) if(ht[j].parent==-1) { if(min1>ht[j].weight) { min2=min1;rnode=lnode; min1=ht[j].weight;rnode=j; } elseif(min2>ht[j].weight) { min2=ht[j].weight; rnode=j; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=min1+min2; ht[i].lchild=lnode; ht[i].rchild=rnode; }}#include<iostream>#include"Tree.h"voidtest1(PBTrees){if(s){cout<<s->data<<"";test1(s->lchild);test1(s->rchild);}}voidtest2(PBTrees){if(s){test2(s->lchild); cout<<s->data<<"";test2(s->rchild);