二叉树的建立与遍历

《二叉树的建立与遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握二叉树的结构、构造和遍历等内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2.编写程序生成下面所示的二叉树，并采用先序遍历的非递归算法对此二叉树进行遍历。四、实验步骤（描述实验步骤及中间的结果或现象。在实验中

2、做了什么事情，怎么做的，发生的现象和中间结果）代码：#include#includetypedefintElemType;typedefboolStatus;#defineOK1#defineERROR0#defineOVERFLOW-2#defineSTACK_INT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量//树typedefstructNode9{ElemTypedata;structNode*lchild,*rchild;}BiTNode,*BiTree;//栈ty

3、pedefstruct{BiTree*base;BiTree*top;intstacksize;//当前已分配的存储空间}SqStack;//————————————————————————————//构造一个空栈StatusInitStack(SqStack&S){S.base=(BiTree*)malloc(sizeof(BiTree));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INT_SIZE;returnOK;}//插入元素e为栈顶元素StatusPush(SqStack&S,BiTreee

4、){if(S.top-S.base>=S.stacksize){//若栈满，则追加存储空间S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;returnOK;}//删除S的栈顶元素，并用e返回StatusPop(SqStack&S,BiTree&e){if(S.base==S.top)r

5、eturnERROR;S.top--;e=*S.top;returnOK;}//若栈S为空栈，则返回OK，否则返回ERRORStatusStackEmpty(SqStackS){9if(S.top==S.base)returnOK;elsereturnERROR;}//----------------------------------------------------------------------------------------------------------------//先序创建二叉树StatusCreatBiTree(BiTree&T){intch

6、;scanf("%d",&ch);if(ch==0)T=NULL;else{if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}returnOK;}//访问数据StatusVisit(ElemTypee){printf("%d",e);returnOK;}//先序遍历二叉树StatusPreOrder(BiTreeT){if(T){Visit(T->data);//访问结点PreOrder(T->lc

7、hild);//遍历左子树PreOrder(T->rchild);//遍历右子树}returnOK;}//中序遍历StatusInOrder(BiTree&T){if(T){InOrder(T->lchild);Visit(T->data);InOrder(T->rchild);}returnOK;}9//后序遍历StatusPostOrder(BiTree&T){if(T){PostOrder(T->lchild);PostOrder(T->rchild);Visit(T->data);}returnOK;}//求二叉树的深