实验报告3-网络132徐峰-2013122832(2)

《数据结构》实验报告 - 5 -

} }

void PostOrder(BiTree root)//后序遍历二叉树 {

if(root!=NULL) {

PostOrder(root->LChild);//后序遍历左子树 PostOrder(root->RChild);//后序遍历右子树 Visit(root->data);//访问根结点 } }

void main() {

BiTree T;

CreateBiTree(&T);

printf(\先序遍历序列为:\ PreOrder(T);

printf(\中序遍历序列为:\ InOrder(T);

printf(\后序遍历序列为:\ PostOrder(T); getch(); } 2)

#include #include #include

typedef char DataType; typedef struct Node { DataType data;

struct Node *LChild; struct Node *RChild; }BiTNode, *BiTree;

void CreateBiTree(BiTree *bt) {

char ch;

ch=getchar();

if(ch=='.') *bt=NULL; else {

*bt=(BiTree)malloc(sizeof(BiTNode));//生成一个新结点 (*bt)->data=ch;

CreateBiTree(&(*bt)->LChild);//生成左子树 CreateBiTree(&(*bt)->RChild);//生成右子树

《数据结构》实验报告 - 6 -

} }

void Visit(char ch) {

printf(\}

void PreOrder(BiTree root)

/*先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针*/ {

if(root!=NULL) {

Visit(root->data);

PreOrder(root->LChild); PreOrder(root->RChild); } }

void InOrder(BiTree root) {

if(root!=NULL) {

InOrder(root->LChild); Visit(root->data); InOrder(root->RChild); } }

void PostOrder(BiTree root) {

if(root!=NULL) {

PostOrder(root->LChild); PostOrder(root->RChild); Visit(root->data); } }

void PrintTree(BiTree Boot,int nLayer) {

if(Boot==NULL) return;

PrintTree(Boot->RChild,nLayer+1); for(int i=0;i

printf(\

PrintTree(Boot->LChild,nLayer+1); }

void main()

《数据结构》实验报告 - 7 -

{

BiTree T;

CreateBiTree(&T);

printf(\先序遍历序列为：\PreOrder(T);

printf(\中序遍历序列为：\InOrder(T);

printf(\后序遍历序列为：\PostOrder(T); printf(\PrintTree(T,0); getch(); } 3)

#include using namespace std;

typedef struct Node{//创建节点 char ch;//字符 int weight;//权值

int flag;//判断左右孩子 0为左孩子 1为右孩子 struct Node* next;//叶子节点链表 struct Node* next1;//造树用表 struct Node* LChild; struct Node* RChild; struct Node* Parent; }*List;

int i,a[100];//数组用来暂存一个哈弗曼编码 其中数字为可支持的最大哈弗曼编码的位数

void CinStr(List &H){//输入字符串 H=(List)malloc(sizeof(Node)); H->next=H;//构造循环链表 List r,s; char ch; int flag=1; r=H;

while(flag){ cin>>ch;

if(ch!='*'){

s=(List)malloc(sizeof(Node)); s->ch=ch; s->weight=1; r->next=s; r=s;

《数据结构》实验报告 - 8 -

} else{

flag=0; r->next=H; } } }

void Arrange_1(List &H){//整理链表 统计字符权值 List L1,L2,L3;

for(L1=L3=H->next;L1->next!=H;L1=L1->next,L3=L1){ for(L2=L1->next;L2!=H;){ if(L1->ch==L2->ch){ L1->weight++;

L3->next=L2->next; free(L2); L2=L3->next; }

else { L3=L2;

L2=L2->next; } } } }

void Arrange_2(List &H){//整理链表 按权值的升序排序 List L1,L2,temp;

temp=(List)malloc(sizeof(Node));

for(L1=H->next;L1->next!=H;L1=L1->next){ for(L2=L1->next;L2!=H;L2=L2->next){ if(L1->weight>L2->weight){ temp->ch=L1->ch;

temp->weight=L1->weight; L1->ch=L2->ch;

L1->weight=L2->weight; L2->ch=temp->ch;

L2->weight=temp->weight; }

else if(L1->weight==L2->weight){//权值相等 比较ascII码 if(int(L1->ch)>int(L2->ch)){ temp->ch=L1->ch;

temp->weight=L1->weight; L1->ch=L2->ch;

L1->weight=L2->weight; L2->ch=temp->ch;

《数据结构》实验报告 - 9 -

L2->weight=temp->weight; } } } }

free(temp); }

void Arrange_3(List &H){//复制叶子链为next1 造树用 List L;

for(L=H;L->next!=H;L=L->next) L->next1=L->next; L->next1=H; }

void Arrange_4(List &H){//整理表 按权值升序排列 List L1,L2,temp; L1=H->next1;

if(L1->next1!=H&&L1->weight>L1->next1->weight){ temp=H->next1;

L2=H->next1=H->next1->next1;

for(L1=L2->next1;L1!=H&&temp->weight>L1->weight;L2=L1,L1=L1->next1); L2->next1=temp; if(L1!=H)

temp->next1=L1; else

temp->next1=H; } }

void DispCode(List &H){//显示各字符的权值 for(List L=H->next;L!=H;L=L->next) cout<ch<<':'<weight<

void InitLeaf(List &H){//初始化叶子节点 使其孩子都为null List L;

for(L=H->next;L!=H;L=L->next) L->LChild=NULL, L->RChild=NULL; }

void CrtHT(List &H){//创建哈夫曼树 if(H->next1->next1!=H){ List L,L1,L2;