《2022年北京理工大学数据结构实验 .pdf》由会员分享，可在线阅读，更多相关《2022年北京理工大学数据结构实验 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1、遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。答：示例：先序建树 :依次输入二叉树的结点号，孩子为空的时候输入空格: 输入： abd f ce 输出：先序遍历二叉树为 :abdfce 中序遍历二叉树为 :dfbaec 后序遍历二叉树为 :fdbeca 代码如下：#include #include #define OVERFLOW -2 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; BiTree cre
2、ate(BiTree T) char ch; scanf(%c,&ch); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - if(ch= ) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T) exit(OVERFLOW); T-data=ch; T-lchild=create(T-lchild); T-rchild=create(T-rchild); return T;
3、void PreOrderTraverse(BiTree T) if(T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - if(T) InOrderTraverse(T-lchild); printf(%c,T-dat
4、a); InOrderTraverse(T-rchild); void PostOrderTraverse(BiTree T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); void main() BiTree T; printf( 先序建树 :依次输入二叉树的结点号，孩子为空的时候输入空格:n); T=create(T); printf(n 先序遍历二叉树为 :); PreOrderTraverse(T); printf(n 中序遍历二叉树为 :); InOrderTrav
5、erse(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - printf(n 后序遍历二叉树为 :); PostOrderTraverse(T); 2、按层次遍历二叉树。答：示例：先序建树 :依次输入二叉树的结点号，孩子为空的时候输入空格: 输入： abd f ce 输出：层次遍历二叉树 :abcdef 代码如下：（程序存为 .cpp）#include #include #include 名师资料总结 - - -精品资料欢
6、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;/ 左右孩子指针BiTNode,*BiTree; typedef struct QNode BiTree data; struct QNode *next; QNode,*QueuePtr;
7、 typedef struct QueuePtr front;/对头指针QueuePtr rear;/ 队尾指针LinkQueue; int InitQueue(LinkQueue &Q) /构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front)exit(OVERFLOW); Q.front-next=NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - -
8、 - - return OK; int EnQueue(LinkQueue &Q,BiTree e) /插入元素 e为 Q 的新的对位队尾元素QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p)exit(OVERFLOW);/ 存储分配失败p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; int DeQueue(LinkQueue &Q,BiTree &e) /若队列不空，则删除Q 的队头元素，用 e返回其值，并返回OK /否则返回 ERROR QueuePtr p; if(
9、Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p)Q.rear=Q.front; free(p); return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - int QueueEmpty(LinkQueue Q) if(Q.front=Q.rear)return 1; else return
10、 0; BiTree CreateBiTree(BiTree &T) /按照先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。char ch; scanf(%c,&ch); if(ch= ) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T)exit(OVERFLOW); T-data=ch;/生成根结点T-lchild=CreateBiTree(T-lchild);/ 构造左子树T-rchild=CreateBiTree(T-rchild);/构造右子树 return T; void LevelT
11、raverse(BiTree T) LinkQueue Q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - BiTree b; InitQueue(Q); if(T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,b); printf(%c,b-data); if(b-lchild)EnQueue(Q,b-lchild); if(b-rchild)EnQueue(Q,b-rchild
12、); main() BiTree T; printf( 先序建树 :依次输入二叉树的结点号，孩子为空时输入空格:n); T=CreateBiTree(T); printf(n 层次遍历二叉树 :); LevelTraverse(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -