//二叉樹的建立，與霍夫曼壓縮算法的實現
//BY-俞宏遠，2015.4.10
#include?
#include?
#include?
using?namespace?std;

const?int?MAX=128;
ifstream?input（“inputfile1.txt“）;
ofstream?output（“outputfile1.txt“）;
struct?BiHuff//markflag?構成雙重標記位
{
	char?data;
	char?code[100];
	int?weight;
	bool?flag;//1表示為葉，0不是
	int?lchildrchildparent;?
	bool?mark;//標記是否是在建立霍夫曼樹時需要遍歷的項
};

struct?BiNode//二叉樹節點結構
{
	char?data;
	BiNode?*lchild;
	BiNode?*rchild;
};

class?BiTree
{
public?:
	BiTree（?）;?????????????//構造函數，初始化一棵二叉樹，其前序序列由鍵盤輸入
	~BiTree（?void）;?????????//析構函數，釋放二叉鏈表中各結點的存儲空間
	BiNode*?Getroot（）;??//獲得指向根結點的指針
	void?PreOrder（BiNode?*root）;?????//前序遍歷二叉樹
	void?InOrder（BiNode??*root）;??????//中序遍歷二叉樹
	void?PostOrder（BiNode??*root）;????//后序遍歷二叉樹
	void?CalcuTree（?BiNode?*root）;???????//計算二叉樹中葉節點個數，樹的高度，度為2節點個數
	//	bool?IsFullTree（?BiNode?*root）;??????//判斷二叉樹是否為滿樹
private?:
	BiNode?*root;?????????//指向根結點的頭指針
	BiNode?*Creat（?）;?????//有參構造函數調用
	void?Release（BiNode?*T）;???//析構函數調用
};


int?MinWeight（BiHuff*?int?）;//找到最小項
int?CountTree（BiHuff*?）;//數被mark標記的樹還剩多少
int?FindLeaf（BiHuff*?）;//找葉子
void?CreateHTree（?BiHuff?*?int?）;//創建哈夫曼樹
void?Encoding?（?BiHuff?*）;//編碼
void?TransHuffman（BiHuff?*）;//將文檔轉換為霍夫曼碼
void?Decoding?（BiHuff?*）;//解碼

void?TranBinary（）;//把文檔轉換為2進制形式儲存，采用按位與運算

void?NormalBiTree（）;?//功能模塊1建立普通二叉樹并遍歷得到有關信息
void?HuffmanTree（）;//功能模塊22.建立霍夫曼二叉樹并對文件進行編碼.


void?main（）{
	TranBinary（）;
	int?choose=0;
	while?（choose!=3）
	{
		cout<<“功能選擇：?“<		cout<<“??1.建立普通二叉樹并遍歷得到有關信息.?“<		cout<<“??2.建立霍夫曼二叉樹并對文件進行編碼.?“<		cout<<“??3.退出！?“<		cin>>choose;
		if（choose==1）{
			NormalBiTree（）;
		}
		else?if（choose==2）{
			HuffmanTree（）;
		}
		else?if（choose==3）;
		else{
			cout<<“輸入有誤！“<			break;
		}
	}
	input.close（）;
	output.close（）;
}


void?TranBinary（）//把文檔轉換為2進制形式儲存，采用按位與運算
{
	ifstream?fileIn（“inputfile1.txt“）;
	ofstream?fileOut（“inputfile3.txt“）;
	char?inputs;
	while?（fileIn.get（inputs））?{

		for?（int?i?=?7;?i?>=?0;?--i）
			fileOut?<<（（inputs>>（i））&1）;
		//		fileOut<<“?“;
	}
	fileIn.close（）;
	fileOut.close（）;
}

BiTree::BiTree（）{
	this->root=Creat（）;??//保存根節點
}

BiNode*?BiTree::Creat（?）
{
	BiNode*?T=NULL;
	char?ch;
	cin>>ch;
	if?（ch==‘*‘）?root?=?NULL;???//空格表示該節點下一個指針為空
	else
	{?
		T?=?new?BiNode;???????//生成一個結點
		T->data=ch;
		T->lchild?=?Creat（?）;????//遞歸建立左子樹
		T->rchild?=?Creat（?）;????//遞歸建立右子樹
	}?
	return?T;
}

BiTree::~BiTree（void）
{
	Release（root）;
}

void?BiTree::Release（BiNode*?root）//遞歸釋放樹空間
{
	if?（root?!=?NULL）{??????????????????
		Release（root->lchild）;???//釋放左子樹
		Release（root->rchild）;???//釋放右子樹
		delete?root;
	}??
}

BiNode*?BiTree::Getroot（?）
{
	return?root;
}

void?BiTree::PreOrder（BiNode?*root）
{
	if（root==NULL）??return;
	else{??
		cout<data<<“?“;
		PreOrder（root->lchild）;
		PreOrder（root->rchild）;
	}
}

void?BiTree::InOrder?（BiNode?*root）
{
	if?（root==NULL）??retu

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-04-20?18:01??BiTree-Huffman\
?????目錄???????????0??2015-04-11?19:17??BiTree-Huffman\BiTree-Huffman\
?????文件?????7864320??2015-04-11?18:31??BiTree-Huffman\BiTree-Huffman.sdf
?????文件?????????909??2015-04-07?18:23??BiTree-Huffman\BiTree-Huffman.sln
?????文件???????19968??2015-04-11?18:31??BiTree-Huffman\BiTree-Huffman.v11.suo
?????文件????????4012??2015-04-07?18:38??BiTree-Huffman\BiTree-Huffman\BiTree-Huffman.vcxproj
?????文件?????????941??2015-04-07?18:38??BiTree-Huffman\BiTree-Huffman\BiTree-Huffman.vcxproj.filters
?????目錄???????????0??2015-04-11?19:17??BiTree-Huffman\BiTree-Huffman\Debug\
?????文件??????????61??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\BiTree-Huffman.lastbuildstate
?????文件????????1455??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\BiTree-Huffman.log
?????文件?????????590??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\cl.command.1.tlog
?????文件???????12462??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\CL.read.1.tlog
?????文件?????????312??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\CL.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link-cvtres.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link-cvtres.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link-rc.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link-rc.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016-cvtres.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016-cvtres.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016-rc.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016-rc.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1016.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172-cvtres.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172-cvtres.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172-rc.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172-rc.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1172.write.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1848-cvtres.read.1.tlog
?????文件???????????2??2015-04-11?17:59??BiTree-Huffman\BiTree-Huffman\Debug\link.1848-cvtres.write.1.tlog
............此處省略69個文件信息