二叉树的遍历 竖向显示.docx

实验2树型数据结构实验目的和要求1. 熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先 序递归遍历、中序递归和非递归遍历、后序递归遍历。2. 掌握按先序遍历顺序输入数据，递归建立二叉树的方法。3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。实验环境Turbo C 或 VC+实验学时4学时，必做实验实验题目1. 问题描述建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中 序和后序），打印输出遍历结果。基本要求从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以 先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求 采用递归和非递归两种方法实现。测试数据ABC DE G F （其中中表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2. 已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向 显示就是二叉树的按层显示）。提示:（1）参习题6.20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3. 如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。BCDE F G图 6.35实现代码和运行结果1.实现代码：1)递归：#include<stdio.h>#include<malloc.h>typedef char DataType;typedef 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(BiTNode);/生成新结点 (*bt)->data=ch;CreateBiTree(&(*bt)->LChild);/生 成左子树CreateBiTree(&(*bt)->RChild);/生 成右子树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);Postorder(bt->RChild);printf("%c ”,bt->data);/ 访问根节点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 <stdio.h>#include <malloc.h>#include <conio.h>#define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define MAXSIZE 50 /*队列的最大长度*/typedef 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();if(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)%MAXSIZE=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; /* 重新设置队头指针 */ 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)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;/* 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);Postorder(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<stdio.h>#include<malloc.h>typedef char DataType;typedef 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(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);Postorder(bt->RChild);printf("%c ”,bt->data);/ 访问根节点void RDLorder(BiTree bt,int n)if(bt!=NULL)RDLorder(bt->RChild,n+1);for(int i=1;i<=n*5;i+)printf("");printf("%c n",bt->data);/ 访问根节点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)