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

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;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新资格考试认证数据结构实验报告三(3)全文阅读和word下载服务。