[精品]实验5二叉树的基础实验.doc

《[精品]实验5二叉树的基础实验.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五二叉树的基础实验定义二叉树的数据结构并完成建树、删除和添加结点及先序、中序和后序遍历的递归算法#include"stdafx.h"#include#include#include#defineOK1#defineOVERFLOW-2#defineERROR0#defineFALSE0typedefintStatus;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;)BiTNode,*BiTree;StatusCreateBiTree(Bi

2、Tree&T){〃按先序次序输入二叉树屮结点的值(一个字符)，空格字符表示空树,〃构造二叉链表表示的二叉树Tocharch;scanf(“％c“,&ch);if(ch==**)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);l^>data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);returnOK;}StatusVisit(chare){printf(n%c",e);returnOK;}〃先序遍历StatusPreOrderTr

3、averse(BiTreeT,StatusVisit(chare)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchiId,Visit))returnOK;returnERROR;}elsereturnOK;}〃屮序遍历StatusInOrderTraverse(BiTreeT,StatusVisit(chare)){if(T){if(PreOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(Pr

4、eOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}〃后序遍历StatusLastOrderTraverse(BiTreeT,StatusVisit(chare))if(T){if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchiId,Visit))if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}〃杏找结点(先序杏找)StatusPreOrderLook(Bi

5、TreeT,charx,BiTree&p){//若二叉树屮存在和x相同的元索，则p指向该结点并返回OK,//否则返回FALSE讦(T){讦(T・>data==x){P=T;returnOK;}elseif(PreOrderLook(T->lchiId,x,p))returnOK;elsereturn(PreOrderLook(T->rchild,x,p));})elsereturnFALSE;StatusPPreOrderLook(BiTreeT,charx,BiTree&p){//若二叉树屮存在和X相同的元索，则p指向该结点并返冋OK,//否则返回FALSEif(T)if

6、(T->lchild->data==xllT->rchild->data==x)P=T;returnOK;elseif(PPreOrderLook(T->lchild,x,p))returnOK;elsereturn(PPreOrderLook(T->rchild,x,p));}}elsereturnFALSE;}〃释放节点以及节点的子树所占空间intDestroyBiTree(BiTree&T){if(T){if(T->lchild)DestroyBiTree(T->lchiId);if(T->rchild)DestroyBiTree(T->rchild);free(T)

7、;returnOK;//T=NULL;}returnOK;}〃结点的插入StatusInsertNode(B汀「ee&TBT「eep,charc){intb;charch;BiTrees=(BiTNode*)malIoc(sizeof(BiTNode));printfC1输入节点的插入位置为0则插入左节点，为1则插入右节点:”);inti;cin»i;if(T){b=PreOrderLook(T,c,p);if(b==1&&i==0)BiTreeq=p->lchild;p->lchild=s;printfC*请输入