数据结构实验报告三(2)

实验题目 姓名

第七章、树形结构 班级

小组合作 学 号

否

一、实验目的

7.1 实现二叉树的各种基本运算的算法 7.2 实现二叉树的各种遍历算法 7.3 求二叉树从根节点到叶子节点的路径 7.4 由遍历序列构造二叉树 7.5 实现中序线索化二叉树 7.6 构造哈夫曼树 7.7 用二叉树来表示代数表达式二.实验环境 安装了 Windows7 操作系统，并且安装了 Microsoft Visual C++ 6.0。

三、实验内容与步骤

7.1 实现二叉树的各种基本运算的算法【编写一个程序 exp7-1.cpp,实现二叉树的各种基本运算的算法。 (1) 输出二叉树 b (2) 输出 H 节点的左右孩子节点值 (3) 输出二叉树 b 的深度 (4) 输出二叉树 b 的宽度 (5) 输出二叉树 b 的节点个数 (6) 输出二叉树 b 的叶子节点个数 (7) 释放二叉树 b1 输入程序如下： ○ #include "stdafx.h" //文件名:exp7-1.cpp #include <stdio.h> #include"algo7-1.cpp" typedef char ElemType; //typedef struct node //{ // // // ElemType data; struct node *lchild; struct node *rchild; //数据元素 //指向左孩子 //指向右孩子

//} BTNode; //extern void CreateBTNode(BTNode *&b,char *str); //extern BTNode *FindNode(BTNode *b,ElemType x); //extern BTNode *LchildNode(BTNode *p); //extern BTNode *RchildNode(BTNode *p); //extern int BTNodeDepth(BTNode *b); //extern void DispBTNode(BTNode *b); //extern int BTWidth(BTNode *b); //extern int Nodes(BTNode *b); //extern int LeafNodes(BTNode *b); //extern void DestroyBTNode(BTNode *&b); void main()

{

BTNode *b,*p,*lp,*rp;; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树的基本运算如下:\n"); printf(" (1)输出二叉树:");DispBTNode(b);printf("\n"); printf(" (2)H 节点:"); p=FindNode(b,'H'); if (p!=NULL) { lp=LchildNode(p); if (lp!=NULL) printf("左孩子为%c ",lp->data); else printf("无左孩子 "); rp=RchildNode(p); if (rp!=NULL) printf("右孩子为%c",rp->data); else printf("无右孩子 "); } printf("\n"); printf(" (3)二叉树 b 的深度:%d\n",BTNodeDepth(b)); printf(" (4)二叉树 b 的宽度:%d\n",BTWidth(b)); printf(" (5)二叉树 b 的节点个数:%d\n",Nodes(b)); printf(" (6)二叉树 b 的叶子节点个数:%d\n",LeafNodes(b)); printf(" (7)释放二叉树 b\n"); DestroyBTNode(b);

}

2 输入程序并运行，如图 ○

7.2 实现二叉树的各种遍历算法编写一个程序 exp7-2.cpp,实现二叉树的各种遍历算法。 1 输入程序如下： ○#include "stdafx.h" //文件名:exp7-2.cpp #include <stdio.h> #include "algo7-1.cpp" #include <malloc.h> #define MaxSize 100 typedef char ElemType; void PreOrder(BTNode *b) //先序遍历的递归算法 { if (b!=NULL) { printf("

%c ",b->data); //访问根节点 PreOrder(b->lchild); //递归访问左子树 PreOrder(b->rchild); //递归访问右子树 } } void PreOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if (b!=NULL) { top++; //根节点入栈 St[top]=b; while (top>-1) //栈不为空时循环 { p=St[top]; //退栈并访问该节点 top--; printf("%c ",p->data); if (p->rchild!=NULL) //右孩子入栈 { top++; St[top]=p->rchild; } if (p->lchild!=NULL) //左孩子入栈 { top++; St[top]=p->lchild; } } printf("\n"); } } void InOrder(BTNode *b) //中序遍历的递归算法 { if (b!=NULL) { InOrder(b->lchild); //递归访问左子树 printf("%c ",b->data); //访问根节点

InOrder(b->rchild); }

//递归访问右子树

} void InOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if (b!=NULL) { p=b; while (top>-1 || p!=NULL) { while (p!=NULL) { top++; St[top]=p; p=p->lchild; } if (top>-1) { p=St[top]; top--; printf("%c ",p->data); p=p->rchild; } } printf("\n"); } } void PostOrder(BTNode *b) //后序遍历的递归算法 { if (b!=NULL) { PostOrder(b->lchild); //递归访问左子树 PostOrder(b->rchild); //递归访问右子树 printf("%c ",b->data); //访问根节点 } } void PostOrder1(BTNode *b) { BTNode *St[MaxSize]; BTNode *p; int flag,top=-1; //栈指针置初值 if (b!=NULL) { do { while (b!=NULL) //将 t 的所有左节点入栈 { top++; St[top]=b; b=b->lchild; } p=NULL; //p 指向当前节点的前一 个已访问的节点 flag=1;

while (top!=-1 && flag) { b=St[top]; if (b->rchild==p) { printf("%c ",b->data); top--; p=b; } else { b=b->rchild; flag=0; } } } while (top!=-1); printf("\n");

//取出当前的栈顶元素 //右子树不存在或已被访问,访问之 //访问*b 节点 //p 指向则被访问的节点

//t 指向右子树

} } void TravLevel(BTNode *b) { BTNode *Qu[MaxSize]; //定义循环队列 int front,rear; //定义队首和队尾指针 front=rear=0; //置队列为空队列 if (b!=NULL) printf("%c ",b->data); rear++; //节点指针进入队列 Qu[rear]=b; while (rear!=front) //队列不为空 { front=(front+1)%MaxSize; b=Qu[front]; //队头出队列 if (b->lchild!=NULL) //输出左孩子,并入队列 { printf("%c ",b->lchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->lchild; } if (b->rchild!=NULL) //输出右孩子,并入队列 { printf("%c ",b->rchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->rchild; } } printf("\n"); } void main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树 b:");DispBTNode(b);printf("\n"); printf("层次遍历序列:"); TravLevel(b); printf("先序遍历序列:\n");

printf(" 递归算法:");PreOrder(b);printf("\n"); printf(" 非递归算法:");PreOrder1(b); printf("中序遍历序列:\n"); printf(" 递归算法:");InOrder(b);printf("\n"); printf(" 非递归算法:");InOrder1(b); printf("后序遍历序列:\n"); printf(" 递归算法:");PostOrder(b);printf("\n"); printf(" 非递归算法:");PostOrder1(b); DestroyBTNode(b); } }

2 输入程序并运行，如图 ○

图8

7.3 求二叉树从根节点到叶子节点的路径对 7.1 的二叉树，设计一个程序 exp7-3.cpp 完成如下功能： (1) 输出所有叶子节点 (2) 输出所有叶子节点到根节点的路径 (3) 输出(2)中的第一条最长路径 1 输入程序如下： ○#include "stdafx.h" //文件名:exp7-3.cpp #include <stdio.h> #include <malloc.h> #include "algo7-1.cpp" #define MaxSize 100 typedef char ElemType;

Node *&b); void AllPath(BTNode *b) { struct snode { BTNode *node; int parent; } Qu[MaxSize]; int front,rear,p; front=rear=-1; rear++; Qu[rear].node=b; Qu[rear].parent=-1; while (front<rear) { front++; b=Qu[front].node; //队头出队列 //*b 为叶子节点 //根节点指针进入队列 //根节点没有双亲节点 //队列不为空 //存放当前节点指针 //存放双亲节点在队列中的位置 //定义顺序队列 //定义队头和队尾指针 //置队列为空队列

if (b->lchild==NULL && b->rchild==NULL) { printf(" %c 到根节点逆路径:",b->data); p=front; while (Qu[p].parent!=-1) { printf("%c ",Qu[p].node->data); p=Qu[p].parent; } printf("%c\n",Qu[p].node->data); } if (b->lchild!=NULL) { rear++; Qu[rear].node=b->lchild; Qu[rear].parent=front; } //左孩子入队列

if (b->rchild!=NULL) { rear++; Qu[rear].node=b->rchild; Qu[rear].parent=front; } } }

//右孩子入队列

void AllPath1(BTNode *b,ElemType path[],int pathlen) { int i; if (b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) { printf(" %c 到根节点逆路径: %c ",b->data,b->data); for (i=pathlen-1;i>=0;i--) printf("%c ",path[i]); printf("\n"); } else { path[pathlen]=b->data; pathlen++; AllPath1(b->lchild,path,pathlen); //递归扫描左子树 AllPath1(b->rchild,path,pathlen); //递归扫描右子树 pathlen--; } } } void LongPath(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen) { int i; if (b==NULL) { //恢复环境 //将当前节点放入路径中 //路径长度增 1 //*b 为叶子节点

if (pathlen>longpathlen) //若当前路径更长,将路径保存在 longpath 中 { for (i=pathlen-1;i>=0;i--) longpath[i]=path[i]; longpathlen=pathlen; } } else { path[pathlen]=b->data; pathlen++; LongPath(b->lchild,path,pathlen,longpath,longpathlen); LongPath(b->rchild,path,pathlen,longpath,longpathlen); pathlen--; } } void DispLeaf(BTNode *b) { if (b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) printf("%c ",b->data); else { DispLeaf(b->lchild); DispLeaf(b->rchild); } } } void main() { BTNode *b; ElemType path[MaxSize],longpath[MaxSize]; int i,longpathlen=0; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树 b:");DispBTNode(b);printf("\n"); //将当前节点放入路径中 //路径长度增 1 //递归扫描左子树 //递归扫描右子树 //恢复环境

printf("b 的叶子节点:");DispLeaf(b);printf("\n"); printf("AllPath:\n");AllPath(b); printf("AllPath1:\n");AllPath1(b,path,0); LongPath(b,path,0,longpath,longpathlen); printf("第一条最长逆路径长度:%d\n",longpathlen); printf

("第一条最长逆路径:"); for (i=longpathlen-1;i>=0;i--) printf("%c ",longpath[i]); printf("\n"); DestroyBTNode(b);

} 2 输入程序并运行，如图

○

图 12

7.4 由遍历序列构造二叉树【设计一个程序 exp7-4.cpp 实现由先序遍历以及由中序遍历序列构造一颗二叉树 的 功 能 要 求 以 括 号 表 示 和 凹 入 表 示 法 输 入 该 二 叉 树 。 并 用 “ ABDEHJKLMNCFGI ” 和 “ DBJHLKMNEAFCGI ” 以 及 由 中 序 遍 历 序 列 “DBJHLKMNEAFCGI”和后序遍历序列“DJLNMKHEBFIGCA”进行验证。 1 输入程序如下： ○#include "stdafx.h" //文件名:exp7-4.cpp #include <stdio.h> #include <malloc.h>

#include"algo7-1.cpp" #define MaxSize 100 #define MaxWidth 40 typedef char ElemType; //typedef struct node //{ // ElemType data; //数据元素 // struct node *lchild; //指向左孩子 // struct node *rchild; //指向右孩子 //} BTNode; //extern void DispBTNode(BTNode *b); //extern void DestroyBTNode(BTNode *&b); BTNode *CreateBT1(char *pre,char *in,int n) { BTNode *s; char *p; int k; if (n<=0) return NULL; s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树节点*s s->data=*pre; for (p=in;p<in+n;p++) //在中序序列中找等于*ppos 的位置 k if (*p==*pre) break; k=p-in; s->lchild=CreateBT1(pre+1,in,k); s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); return s; } BTNode *CreateBT2(char *post,char *in,int n,int m) { BTNode *s; char *p,*q,*maxp; int maxpost,maxin,k; if (n<=0) return NULL; maxpost=-1; for (p=in;p<in+n;p++) //求 in 中全部字符中在 post 中最右边的那个字符 for (q=post;q<post+m;q++) //在 in 中用 maxp 指向这个字符,用 maxin 标识它在 in 中的下标 if (*p==*q) { k=q-post; if (k>maxpost) { maxpost=k; maxp=p; maxin=p-in; } } s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树节点*s s->data=post[maxpost]; s->lchild=CreateBT2(post,in,maxin,m); s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m); return s; } void DispBTNode1(BTNode *b) //以凹入表表示法输出一棵二叉树 { BTNode *St[MaxSize],*p;

int level[MaxSize][2],top=-1,n,i,width=4; char type; if (b!=NULL) { top++; St[top]=b; //根节点入栈 level[top][0]=width; level[top][1]=2; //2 表示是根 while (top>-1) { p=St[top]; //退栈并凹入显示该节点值 n=level[top][0]; switch(level[top][1]) { case 0:type='L';break; //左节点之后输出(L) case 1:type='R';break; //右节点之后输出(R) case 2:type='B';break; //根节点之后前输出(B) } for (i=1;i<=n;i++) //其中 n 为显示场宽,字符以右对齐显示 printf(""); printf("%c(%c)",p->data,type); for (i=n+1;i<=MaxWidth;i+=2) printf("--"); printf("\n"); top--; if (p->rchild!=NULL) { //将右子树根节点入栈 top++; St[top]=p->rchild; level[top][0]=n+width; //显示场宽增 width level[top][1]=1; //1 表示是右子树 } if (p->lchild!=NULL) { //将左子树根节点入栈 top++; St[top]=p->lchild; level[top][0]=n+width; //显示场宽增 width level[top][1]=0; //0 表示是左子树 } } } } void main() { BTN

ode *b; ElemType pre[]="ABDEHJKLMNCFGI"; ElemType in[]="DBJHLKMNEAFCGI"; ElemType post[]="DJLNMKHEBFIGCA"; b=CreateBT1(pre,in,14); printf("先序序列:%s\n",pre); printf("中序序列:%s\n",in); printf("构造一棵二叉树 b:\n"); printf(" 括号表示法:");DispBTNode(b);printf("\n"); printf(" 凹入表示法:\n");DispBTNode1(b);printf("\n\n"); printf("中序序列:%s\n",in);

printf("后序序列:%s\n",post); b=CreateBT2(post,in,14,14); printf("构造一棵二叉树 b:\n"); printf(" 括号表示法:");DispBTNode(b);printf("\n"); printf(" 凹入表示法:\n");DispBTNode1(b);printf("\n"); DestroyBTNode(b);

} 2 运行程序，如图

○

7.5 实现中序线索化二叉树设计一个程序 exp7-5.cpp 实现中序线索化二叉树采用递归和非递归两种方式输出 线索中序序列。

1 输入程序如下： ○// 4.cpp : Defines the entry point for the console application #include "stdafx.h" //文件名:exp7-5.cpp #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; int ltag,rtag; //增加的线索标记 struct node *lchild; //左孩子指针 struct node *rchild; //右孩子指针 } TBTNode; void CreateTBTNode(TBTNode * &b,char *str) { TBTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; //建立的二叉树初始时为空 ch=str[j]; while (ch!='\0') //str 未扫描完时循环 { switch(ch) { case '(':top++;St[top]=p;k=1; break; //为左节点 case ')':top--;break; case ',':k=2; break; //为右节点 default:p=(TBTNode *)malloc(sizeof(TBTNode)); p->data=ch;p->lchild=p->rchild=NULL; if (b==NULL) //*p 为二叉树的根节点 b=p; else //已建立二叉树根节点 { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } void DispTBTNode(TBTNode *b) { if (b!=NULL) { printf("%c",b->data); if (b->lchild!=NULL || b->rchild!=NULL) { printf("("); DispTBTNode(b->lchild); if (b->rchild!=NULL) printf(","); DispTBTNode(b->rchild); printf(")"); } } } TBTNode *pre; //全局变量

void Thread(TBTNode *&p) { if (p!=NULL) { Thread(p->lchild); //左子树线索化 if (p->lchild==NULL) //前驱线索 { p->lchild=pre; //建立当前节点的前驱线索 p->ltag=1; } else p->ltag=0; if (pre->rchild==NULL) //后继线索 { pre->rchild=p; //建立前驱节点的后继线索 pre->rtag=1; } else pre->rtag=0; pre=p; Thread(p->rchild); //右子树线索化 } } TBTNode *CreateThread(TBTNode *b) //中序线索化二叉树 { TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode)); //创建根节点 root->ltag=0;root->rtag=1; root->rchild=b; if (b==NULL) //空二叉树 root->lchild=root; else { root->lchild=b; pre=root; //pre 是*p 的前驱节点,供加线索用 Thread(b); //中序遍历线索化二叉树 pre->rchild=root; //最后处理,加入指向根节点的线索 pre->rtag=1; root->rchild=pre; //根节点右线索化 } return root; } void InOrder(TBTNode *tb) //被 ThInOrder 算法调用 { if (tb->lchild!=NULL && tb->ltag==0) /

/有左孩子 InOrder(tb->lchild); printf("%c ",tb->data); if (tb->rchild!=NULL && tb->rtag==0) //有右孩子 InOrder(tb->rchild); } void ThInOrder(TBTNode *tb) //中序递归算法 { InOrder(tb->lchild); } void ThInOrder1(TBTNode *tb) //中序非递归算法 { TBTNode *p=tb->lchild; //指向根节点 while (p!=tb) { while (p->ltag==0) p=p->lchild; printf("%c ",p->data); while (p->rtag==1 && p->rchild!=tb) { p=p->rchild; printf("%c ",p->data); }

p=p->rchild; } } void DestroyTBTNode1(TBTNode *tb) //被 DestroyTBTNode 算法调用 { if (tb!=NULL) { if (tb->lchild!=NULL && tb->ltag==0) //有左孩子 DestroyTBTNode1(tb->lchild); if (tb->rchild!=NULL && tb->rtag==0) //有右孩子 DestroyTBTNode1(tb->rchild); free(tb); } } void DestroyTBTNode(TBTNode *tb) //释放中序线索二叉树的所有节点 { DestroyTBTNode1(tb->lchild); free(tb); } void main() { TBTNode *b,*tb; CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树:");DispTBTNode(b);printf("\n"); tb=CreateThread(b); printf("线索中序序列:\n"); printf(" 递归算法:");ThInOrder(tb);printf("\n"); printf(" 非递归算法:");ThInOrder1(tb);printf("\n"); DestroyTBTNode(tb);

} 2 运行程序，如图

○

7.6 构造哈夫曼树设计一个程序 exp7-6.cpp 构造一颗哈弗曼树，输出对应哈弗曼树编码和平均查找 长度。 1 输入程序如下 ○#include "stdafx.h" //文件名:exp7-6.cpp #include <stdio.h> #include <string.h> #define N 50 #define M 2*N-1 typedef struct { char data[5];

//叶子节点数 //树中节点总数

//节点值

int weight; //权重 int parent; //双亲节点 int lchild; //左孩子节点 int rchild; //右孩子节点 } HTNode; typedef struct { char cd[N]; //存放哈夫曼码 int start; } HCode; void CreateHT(HTNode ht[],int n) { int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++) //所有节点的相关域置初值-1 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for (i=n;i<2*n-1;i++) //构造哈夫曼树 { min1=min2=32767; //lnode 和 rnode 为最小权重的两个节点位置 lnode=rnode=-1; for (k=0;k<=i-1;k++) if (ht[k].parent==-1) //只在尚未构造二叉树的节点中查找 { if (ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } else if (ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; } } void CreateHCode(HTNode ht[],HCode hcd[],int n) { int i,f,c; HCode hc; for (i=0;i<n;i++) //根据哈夫曼树求哈夫曼编码 { hc.start=n;c=i; f=ht[i].parent; while (f!=-1) //循序直到树根节点 { if (ht[f].lchild==c) //处理左孩子节点 hc.cd[hc.start--]='0'; else //处理右孩子节点 hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; } hc.start++; //start 指向哈夫曼编码最开始字符

hcd[i]=hc; } } void DispHCode(HTNode ht[],HCode hcd[],int n) { int i,k; int sum=0,m=0,j; printf("输出哈夫曼编码:\n"); //输出哈夫曼编码 for (i=0;i<n;i++) { j=0;

printf(" %s:\t",ht[i].data); for (k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf("\n"); } printf("平均长度=%g\n",1.0*sum/m); } void main() { int n=15,i; char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"}; int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNode ht[M]; HCode hcd[N]; for (i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); }

2 运行程序，如图+ ○

7.7 用二叉树来表示代数表达式设计一个程序 exp7-7.cpp 用二叉树来表示代数表达式，树的每一个节点包括一个 运算符，代数表达式中只包含 +、-、*、/和一位整数且没有错误，并且要按照先 乘除后加减的原则构造二叉树，如下图是 1+2*3-4/5 代数表达是对应的二叉树。然 后有对应的二叉树计算该表达式的值 / / 1 * 4 / // 5

+

1 输入程序如下： ○

2

3

#include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #include "algo7-1.cpp" #define MaxSize 100 typedef char ElemType; BTNode *CRTree(char s[],int i,int j) { BTNode *p; int k,plus=0,posi; if (i==j) { p=(BTNode *)malloc(sizeof(BTNode));