《二叉树的遍历 竖向显示.docx》由会员分享，可在线阅读，更多相关《二叉树的遍历 竖向显示.docx（11页珍藏版）》请在三一办公上搜索。
1、实验2树型数据结构实验目的和要求1. 熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先 序递归遍历、中序递归和非递归遍历、后序递归遍历。2. 掌握按先序遍历顺序输入数据，递归建立二叉树的方法。3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。实验环境Turbo C 或 VC+实验学时4学时，必做实验实验题目1. 问题描述建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中 序和后序），打印输出遍历结果。基本要求从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以 先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求 采用递归和非递归两种
2、方法实现。测试数据ABC DE G F （其中中表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2. 已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向 显示就是二叉树的按层显示）。提示:（1）参习题6.20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3. 如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。BCDE F G图 6.35实现代码和运行结果1.实现代码：1)递归：#include#includetypedef char DataType;typedef struct NodeData
3、Type 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);/生 成右子树void Preorder(BiTree bt)if(bt!=NULL) p
4、rintf(%C ”,bt-data);访问根结点Preorder(bt-LChild);/ 先序遍历左子树Preorder(bt-RChild);/ 先序遍历右子树void Inorder(BiTree bt)if(bt!=NULL)Inorder(bt-LChild);/ 中序遍历左子树printf(%C ”,bt-data);访问根结点Inorder(bt-RChild);/ 先序遍历右子树void Postorder(BiTree bt)if(bt!=NULL)Postorder(bt-LChild);Postorder(bt-RChild);printf(%c ”,bt-data);
5、/ 访问根节点int main()BiTree bt;printf(按扩展先序遍历序列建立二叉树，请输入序列:n);CreateBiTree(&bt);printf(n 先序遍历得:n);Preorder( bt);printf(n 中序遍历得:n);Inorder(bt);printf(n 后序遍历得:n);Postorder(bt);return 0;2)#include #include #include #define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define MAXSIZE 50 /*队列的最大长度*/typede
6、f char DataType;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;typedef BiTree QueueElementType;typedef structQueueElementType elementMAXSIZE; /* 队列的元素空间*/int front; /*头指针指示器*/int rear; /*尾指针指示器*/SeqQueue;void CreateBiTree(BiTree *bt)char ch;ch = getchar();i
7、f(ch=.) *bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode); /生成新结点(*bt)-data=ch;CreateBiTree(&(*bt)-LChild); /生成左子树CreateBiTree(&(*bt)-RChild);/生成右子树/*初始化操作*/void InitQueue(SeqQueue *Q)/*将*。初始化为一个空的循环队列*/Q-front=Q-rear=0;/*入队操作*/int EnterQueue(SeqQueue *Q, QueueElementType x)/*将元素x入队*/if(Q-rear+1)%MAXS
8、IZE=Q-front) /* 队列已经满了 */return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */return(TRUE); /* 操作成功 */*出队操作*/int DeleteQueue(SeqQueue *Q, QueueElementType *x)/*删除队列的队头元素，用x返回其值*/if(Q-front=Q-rear) /* 队列为空 */return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /* 重新设置队头指
9、针 */ return(TRUE); /* 操作成功 */int IsEmpty(SeqQueue *Q)/*提取队列的队头元素，用x返回其值*/if(Q-front=Q-rear) /* 队列为空 */return(TRUE);elsereturn(FALSE); /* 操作成功*/int LayerOrder(BiTree bt)SeqQueue *Q;BiTree p;Q=(SeqQueue *)malloc(sizeof(SeqQueue);/p=(BiTree *)malloc(sizeof(BiTree);InitQueue(Q); /*初始化空队列Q*/if(bt = NULL)
10、return ERROR; /*若二叉树bt为空树，则结束遍历*/EnterQueue(Q, bt);/*若二叉树bt非空，则根结点bt入队，开始层次遍历*/ while(!IsEmpty(Q)/*若队列非空，则遍历为结束，继续进行*/ DeleteQueue(Q, &p);/*队头元素出队并访问*/ printf(%c ”,p-data);if(p-LChild )EnterQueue(Q, p-LChild);/*若p的左孩子非空，则进队*/ if(p-RChild )EnterQueue(Q, p-RChild); /*若p的右孩子非空，则进队*/ /*while*/ return OK
11、;/* LayerOrder */void Preorder(BiTree bt)if(bt!=NULL)printf(%c ”,bt-data);/ 访问根节点Preorder(bt-LChild);/ 先序遍历左子树Preorder(bt-RChild);/ 先序遍历右子树void Inorder(BiTree bt)if(bt!=NULL)Inorder(bt-LChild);printf(%c ”,bt-data);/ 访问根节点Inorder(bt-RChild);void Postorder(BiTree bt)if(bt!=NULL)Postorder(bt-LChild);Po
12、storder(bt-RChild);printf(%c ”,bt-data);/ 访问根节点void main()BiTree bt;printf(按扩展先序遍历序列建立二叉树，请输入序列:n);CreateBiTree(&bt);printf(n 先序遍历得:n);Preorder( bt);printf(n 中序遍历得:n);Inorder(bt);printf(n 后序遍历得:n);Postorder(bt);printf(n层次遍历输出结点为:n);LayerOrder(bt);getch();3) #include#includetypedef char DataType;type
13、def struct NodeDataType 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(BiTree);/生成新结点 (*bt)-data=ch;CreateBiTree(&(*bt)-LChild);/生 成左子树CreateBiTree(&(*bt)-RChild);/生 成右子树void Preorder(BiTr
14、ee bt)if(bt!=NULL)printf(%c ”,bt-data);/ 访问根节点Preorder(bt-LChild);/ 先序遍历左子树Preorder(bt-RChild);/ 先序遍历右子树void Inorder(BiTree bt)if(bt!=NULL)Inorder(bt-LChild);printf(%c ”,bt-data);/ 访问根节点Inorder(bt-RChild);void Postorder(BiTree bt)if(bt!=NULL)Postorder(bt-LChild);Postorder(bt-RChild);printf(%c ”,bt-d
15、ata);/ 访问根节点void RDLorder(BiTree bt,int n)if(bt!=NULL)RDLorder(bt-RChild,n+1);for(int i=1;idata);/ 访问根节点RDLorder(bt-LChild,n+1);int main()BiTree bt;printf(按扩展先序遍历序列建立二叉树，请输入序列:n);CreateBiTree(&bt);printf(n 先序遍历得:n);Preorder( bt);printf(n 中序遍历得:n);Inorder(bt);printf(n凹形打印二叉树n);RDLorder(bt,1);printf(nRDLorder:);return 0;2.运行结果：1)递归：2)3)
