数据结构（双语）48课时版11-12实验四-二叉树的基本操作及应用

DataStructure

数据结构计算机与信息技术系袁莹Email:yuanying@2021年05月19日实验报告下载下载：尔雅/作业/实验四

学号_姓名_04实验报告.doc

实验四二叉树的基本操作-空.cpp实验四二叉搜索树-空.cppExperiment4：

Thebasicoperationandapplicationofbinarytree（二叉树的基本操作及应用）Purpose（实验目的）：TheCreation

andDeletion、Threetraversal(preorder/inorder/postorder)、Countleafnodesandheight（5

classes）orbinarysearchtree（5

classes）实验步骤一、二叉树的基本操作（1）二叉树的建立要求实现二叉树的建立，可以任选存储结构。（2）树的遍历要求实现二叉树的前序、中序、后序遍历。（3）二叉树的叶子和深度。要求计算二叉树的叶子节点个数和深度。实验步骤二、二叉查找树的基本操作（1）建立二叉搜索树。（2）实现二叉搜索树的插入。（3）实现二叉搜索树的删除。（4）实现二叉搜索树的查找指定值、查找最小值和查找最大值。结构体声明#include<stdio.h>#include<stdlib.h>#definemaxsize100typedefcharelementType;typedefstructnode{elementTypeelement;structnode*lchild,*rchild;}*BiTree;二叉树的建立递归删除二叉树递归二叉树的前序遍历递归二叉树的中序遍历参考前序遍历二叉树的后序遍历参考前序遍历二叉树的层次遍历计算二叉树的叶子节点个数递归计算二叉树的高度递归main函数case1: {printf("请按照先序遍历的顺序一次输入节点数据，每个叶子节点以#结束。\n");getchar();T1=CreateBiTree();if(T1!=NULL)printf("二叉树创建成功\n");break;}实验结果SearchTreeMakeEmpty(SearchTreeT);PositionFind(ElementTypeX,SearchTreeT);PositionFindMin(SearchTreeT);PositionFindMax(SearchTreeT);SearchTreeInsert(ElementTypeX,SearchTreeT);SearchTreeDelete(ElementTypeX,SearchTreeT);voidInOrder(SearchTreeT)

二叉查找树结构体声明typedefstructTreeNode{ ElementTypeElement; SearchTreeLeft; SearchTreeRight;}*SearchTree,*Position;MakeEmptySearchTree

MakeEmpty(SearchTreeT){

if(T!=NULL)

{

__________________//递归清空左子树

__________________//递归清空右子树 free(T);

}

returnNULL;}FindPositionFind(ElementTypeX,SearchTreeT){

if(T==NULL)

returnNULL;/*notfoundinanemptytree*/

if(X<T->Element)/*ifsmallerthanroot*/_____________________//在左子树中查找X的位置

elseif(X>T->Element)/*iflargerthanroot*/

_____________________//在右子树中查找X的位置

else/*ifX==root*/ returnT;/*found*/}FindMin递归写法FindMax非递归写法SearchTreeInsert(ElementTypeX,SearchTreeT){if(T==NULL){/*Createandreturnaone-nodetree*/

T=(SearchTree)malloc(sizeof(structTreeNode));

if(T==NULL)

printf("Outofspace!!!");

else{

________________________//把X赋值给T的Element域

________________________//将T的左右指针赋值为NULL

}}/*Endcreatingaone-nodetree*/else

/*Ifthereisatree*/

if(X<T->Element)

_________________________//递归，在左子树中插入X

else

if(X>T->Element)

__________________________//递归，在右子树中插入X

/*ElseXisinthetreealready;we'lldonothing*/

returnT;/*Donotforgetthisline!!*/

}InsertInsertionSearchTreeDelete(ElementTypeX,SearchTreeT){PositionTmpCell;

if(T==NULL)Printf("Elementnotfound");

elseif(X<T->Element)/*Goleft*/

T->Left=Delete(X,T->Left);

elseif(X>T->Element)/*Goright*/

T->Right=Delete(X,T->Right);

else

/*Foundelementtobedeleted*/

if(T->Left&&T->Right) {/*Twochildren*/

TmpCell=FindMax(T->Left);

T->Element=TmpCell->Element;

T->Left=Delete(T->Element,T->Left);

}/*Endif*/接下页Deletionelse{/*Oneorzerochild*/

TmpCell=T;

if(T->Left==NULL)/*Alsohandles0child*/

T=T->Right;

elseif(T->Right==NULL) T=T->Left;

free(TmpCell);

}returnT;}T(N)=O(h)wherehistheheightofthetreeDeletionvoidInOrder(SearchTreeT)