实验目的： 掌握二叉树的链式存储结构及其遍历
实验重点： 二叉树的链式存储实现方法
实验内容：
基本任务：用二叉链表存储结构表示下图所示二叉树，
并用递归方法输出三种遍历结果。
修改数节点值的数据类型及visit函数后，可以正常输出
进阶任务：
1，计算输出所建树的高度
2，用非递归算法实现中序遍历
3，实现层次遍历，提示见后面。
4，用顺序存储表示，并进行层次遍历、先序、中序和后续遍历
5，用非递归算法实现先序遍历、后续遍历
实验时间：2020年11月10日（周二1，2节）
实验地点：10号楼413
编辑
实验提示:
进阶任务提示：
1，思想：利用队列的思想，根结点不空则入队，队不空则出队并遍历队首结点，然后分别判断队首结点的左右子树是否为空，不空则入队；直至队列为空。则遍历完成。(为了简单可以采用顺序存储队列)
程序流程图：
编辑
程序代码：
#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define MaxSize 100 //#define ERROR 0 //#define OK 1 typedef int DataType; /*示例：1 2 4 0 0 5 0 0 3 0 0 先序： 1 2 4 5 3 中序： 4 2 5 1 3 后续： 4 5 2 3 1 示例：8 3 1 0 0 6 4 0 0 7 0 0 19 14 13 0 0 0 0 二叉树的先序序列： 8 3 1 6 4 7 19 14 13 二叉树的中序序列： 1 3 4 6 7 8 13 14 19 二叉树的后序序列： 1 4 7 6 3 13 14 19 8 */ DataType all[19]={8,3,1,0,0,6,4,0,0,7,0,0,19,14,13,0,0,0,0}; int u=0; typedef struct BiTNode { DataType data; struct BiTNode *lchild; struct BiTNode *rchild; } *BiTree,BitNode; typedef struct Queue{ int first; BitNode*data[MaxSize]; int final; }Queue; void CreateBitTree(BiTree *T); /*按照先序输入字符序列递归创建二叉树*/ void PreOrderTraverse(BiTree T); /*二叉树的先序遍历的递归函数*/ void InOrderTraverse(BiTree T); /*二叉树的中序遍历的递归函数*/ void PostOrderTraverse(BiTree T); /*二叉树的后序遍历的递归函数*/ void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的非递归函数*/ void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的非递归函数*/ void PostOrderTraverse2(BiTree T); /*二叉树的后序遍历的非递归函数*/ void BinaryTreeLeveLOrder(BiTree T);/*二叉树的层次遍历*/ bool enQueue(Queue*& q,BitNode*& T); //入队,层次遍历需求 bool deQueue(Queue*& q,BitNode*& T); //出队,层次遍历需求 bool emptyQueue(Queue*& q); //判断队列是否为空,层次遍历需求 int height(BiTree T);/*二叉树的高度*/ int main() { BiTree T; //构建二叉链表表示的二叉树 T=NULL; //给树初始化 int i=0; printf("按先序序列输入二叉树中结点的值（一个整型）各数字用空格分开，整型0表示空树\n"); for(i=0;i<sizeof(all)/sizeof(int);i++) printf("%d ",all[i]); printf("\n"); CreateBitTree(&T); printf("二叉树的递归先序序列：\n"); PreOrderTraverse(T); printf("\n"); printf("二叉树的递归中序序列：\n"); InOrderTraverse(T); printf("\n"); printf("二叉树的递归后序序列：\n"); PostOrderTraverse(T); printf("\n"); printf("二叉树的非递归先序序列：\n"); PreOrderTraverse2(T); printf("\n"); printf("二叉树的非递归中序序列：\n"); InOrderTraverse2(T); printf("\n"); printf("二叉树的非递归后序序列：\n"); PostOrderTraverse2(T); printf("\n"); printf("二叉树的层次遍历：\n"); BinaryTreeLeveLOrder(T); printf("\n"); printf("二叉树的高度为：\n"); printf("%d\n",height(T)); } void CreateBitTree(BiTree *T) /*递归创建二叉树*/ { DataType ch; //scanf("%d",&ch); //通过键盘输入进行树的赋值 ch=all[u];//通过数组进行对树的赋值 u++; if(ch==0) *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode)); /*生成根结点*/ if(!(*T)) exit(-1); (*T)->data=ch; CreateBitTree(&((*T)->lchild)); /*构造左子树*/ CreateBitTree(&((*T)->rchild)); /*构造右子树*/ } } void PreOrderTraverse(BiTree T) /*先序遍历二叉树的递归实现*/ { if(T) { printf("%d ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiTree T) /*中序遍历二叉树的递归实现*/ { if(T) { InOrderTraverse(T->lchild); printf("%d ",T->data); InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T) /*后序遍历二叉树的递归实现*/ { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%d ",T->data); } } void PreOrderTraverse2(BiTree T)/*二叉树的先序遍历的非递归函数*/ { BiTree stack[MaxSize]; int top=0; BitNode *p; p=T; while(p!=NULL||top>0) { while(p!=NULL) { stack[top++]=p; printf("%d ",p->data); p=p->lchild; } if(top>0) { top--; p=stack[top]; p=p->rchild; } } } void InOrderTraverse2(BiTree T)/*二叉树的中序遍历的非递归函数*/ { BiTree stack[MaxSize]; int top=0; BitNode *p; p=T; while(p!=NULL||top>0) { while(p!=NULL) { stack[top++]=p; p=p->lchild; } if(top>0) { top--; p=stack[top]; printf("%d ",p->data); p=p->rchild; } } } void PostOrderTraverse2(BiTree T)/*二叉树的后序遍历的非递归函数*/ { BiTree stack[MaxSize]; int top=0; BitNode *p,*q; p=T; q=NULL; while(p!=NULL||top>0) { while(p!=NULL) { stack[top++]=p; p=p->lchild; } if(top>0) { p=stack[top-1]; if(p->rchild==NULL||p->rchild==q) { printf("%d ",p->data); q=p; p=NULL; top--; } else p=p->rchild; } } } bool enQueue(Queue*& q,BitNode*& T){ //入队 if(q->final==MaxSize-1){ return false; } q->final++; q->data[q->final]=T; return true; } bool deQueue(Queue*& q,BitNode*& T){ //出队 if(q->first==q->final){ return false; } q->first++; T=q->data[q->first]; return true; } bool emptyQueue(Queue*& q){ //判断队列是否为空 if(q->first==q->final){ return true; } else{ return false; } } void BinaryTreeLeveLOrder(BiTree T)/*二叉树的层次遍历*/ { Queue *q; int num; q=(Queue*)malloc(sizeof(Queue)); q->first=q->final=-1; if(T!=NULL){ enQueue(q,T); } while(emptyQueue(q)!=true){ deQueue(q,T); printf("%d ",T->data); if(T->lchild!=NULL){ enQueue(q,T->lchild); } if(T->rchild!=NULL){ enQueue(q,T->rchild); } } } int height(BiTree T)/*二叉树的高度*/ { BitNode *p; p=T; if(p==NULL) return 0; else { int lheight=height(p->lchild); int rheight=height(p->rchild); if(lheight>rheight) return(lheight+1); else return(rheight+1); } }
运行结果及分析：
编辑
上图为通过键盘输入所构建的树，下图为实验要求通过数组依次写入树的每个结点。
编辑
按先序序列输入二叉树中结点的值（一个整型）各数字用空格分开，整型0表示空树，依次用先序、中序、后序遍历的递归函数实现遍历输出，再依次用先序、中序、后序遍历的非递归函数进行遍历输出，得到以上结果。再利用队列实现二叉树的层次遍历，进行输出。最后输出树的高度。
心得体会：
对C语言的链表进行深刻复习，学习到怎么创建树，怎么实现树的遍历的各种方法，同时也进一步复习栈和队列的用法，对算法有了进一步的学习，得以加强。
