数据结构实验报告-二叉树

数据结构实验报告——二叉树一、实验名称二叉树的构建与基本操作实现二、实验目的理解二叉树的定义、性质及存储结构，掌握二叉树的逻辑特征与物理实现方式。熟练掌握二叉树的构建方法（基于先序、中序、后序遍历序列或层次遍历序列），能够独立完成二叉树的创建代码编写。实现二叉树的基本操作，包括遍历（先序、中序、后序、层次遍历）、求二叉树的深度、统计叶子节点个数、查找指定节点等。通过编程实践，加深对树形结构的理解，提升数据结构的应用能力和代码调试能力，培养逻辑思维和问题解决能力。三、实验环境硬件环境：计算机一台（CPU≥IntelCorei5，内存≥8GB）。软件环境：操作系统（Windows10/11）、编程工具（Dev-C++/VisualStudio2019及以上、Code::Blocks）、C/C++编程语言。四、实验原理4.1二叉树的定义二叉树是n（n≥0）个节点的有限集合，要么为空集（空二叉树），要么由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。二叉树的每个节点最多有两个子节点，分别称为左孩子和右孩子，且子树有左右之分，不能随意交换。4.2二叉树的存储结构本次实验采用链式存储结构（二叉链表），每个节点包含三个域：数据域（存储节点的值）、左指针域（指向左孩子节点）、右指针域（指向右孩子节点）。其结构定义如下（C语言）：c

typedefstructBiTNode{

intdata;//数据域，可根据需求修改数据类型

structBiTNode*lchild,*rchild;//左、右指针域

}BiTNode,*BiTree;4.3二叉树的构建本次实验采用先序遍历序列构建二叉树，约定空节点用特殊符号（如'#'）表示。例如，先序序列"12#4##3##"表示根节点为1，左孩子为2，2的左孩子为空，2的右孩子为4，4的左右孩子均为空，根节点的右孩子为3，3的左右孩子均为空。构建过程通过递归实现，依次读取序列中的字符，若为特殊符号则构建空节点，否则创建新节点并递归构建其左、右子树。4.4二叉树的基本操作原理遍历操作：遍历是指按一定顺序访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。常用的遍历方式有4种：

先序遍历：根节点→左子树→右子树（递归实现）；中序遍历：左子树→根节点→右子树（递归实现）；后序遍历：左子树→右子树→根节点（递归实现）；层次遍历：从上到下、从左到右依次访问每个节点（借助队列实现）。求二叉树深度：二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。空树深度为0，非空树的深度=1+max(左子树深度,右子树深度)，通过递归实现。统计叶子节点个数：叶子节点是指左右子树均为空的节点。空树叶子节点数为0，非空树的叶子节点数=左子树叶子节点数+右子树叶子节点数，递归实现。查找指定节点：根据给定的节点值，在二叉树中查找对应的节点，找到则返回节点指针，否则返回NULL。可通过先序、中序或后序遍历的方式实现查找。五、实验内容与步骤5.1实验内容编写C/C++程序，实现二叉树的构建（基于先序遍历序列），并完成以下基本操作：构建二叉树；先序、中序、后序递归遍历二叉树；层次遍历二叉树；求二叉树的深度；统计二叉树的叶子节点个数；查找指定值的节点。5.2实验步骤定义二叉链表节点结构，明确数据域和指针域的类型及含义。编写二叉树构建函数（CreateBiTree）：采用递归方式，根据先序遍历序列（含空节点标记）创建二叉树，依次读取每个字符，判断是否为空节点，逐步构建根节点及左、右子树。编写遍历函数：分别实现先序（PreOrder）、中序（InOrder）、后序（PostOrder）递归遍历函数，按对应顺序访问节点并输出节点值；实现层次遍历函数（LevelOrder），借助队列存储节点，依次出队访问并将左右孩子入队。编写辅助操作函数：实现求二叉树深度函数（BiTreeDepth）、统计叶子节点个数函数（CountLeaf）、查找指定节点函数（SearchNode），均通过递归或迭代方式实现。编写主函数：设计交互逻辑，提示用户输入先序遍历序列，调用构建函数创建二叉树，然后依次调用各操作函数，输出实验结果，验证程序正确性。调试程序：排查语法错误、逻辑错误（如递归边界处理不当、指针空值异常、队列操作错误等），确保程序能够正常运行并输出正确结果。六、实验代码c

#include<stdio.h>

#include<stdlib.h>

#include<queue.h>//若编译器不自带队列，需自行实现队列结构

//二叉树节点结构定义

typedefstructBiTNode{

intdata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

//1.构建二叉树（先序遍历序列，空节点用#表示）

voidCreateBiTree(BiTree*T){

charch;

scanf("%c",&ch);//读取字符，注意空格和换行符的处理

if(ch=='#'){

*T=NULL;//空节点

}else{

*T=(BiTree)malloc(sizeof(BiTNode));//分配节点空间

if(!*T){

printf("内存分配失败！\n");

exit(1);

}

(*T)->data=ch-'0';//转换为数字（假设输入为数字字符）

CreateBiTree(&((*T)->lchild));//递归构建左子树

CreateBiTree(&((*T)->rchild));//递归构建右子树

}

}

//2.先序遍历（根→左→右）

voidPreOrder(BiTreeT){

if(T!=NULL){

printf("%d",T->data);//访问根节点

PreOrder(T->lchild);//遍历左子树

PreOrder(T->rchild);//遍历右子树

}

}

//3.中序遍历（左→根→右）

voidInOrder(BiTreeT){

if(T!=NULL){

InOrder(T->lchild);//遍历左子树

printf("%d",T->data);//访问根节点

InOrder(T->rchild);//遍历右子树

}

}

//4.后序遍历（左→右→根）

voidPostOrder(BiTreeT){

if(T!=NULL){

PostOrder(T->lchild);//遍历左子树

PostOrder(T->rchild);//遍历右子树

printf("%d",T->data);//访问根节点

}

}

//5.层次遍历（借助队列）

voidLevelOrder(BiTreeT){

if(T==NULL)return;

queueq;//定义队列，存储二叉树节点指针

InitQueue(&q);//初始化队列

EnQueue(&q,T);//根节点入队

while(!QueueEmpty(&q)){

BiTreep;

DeQueue(&q,&p);//出队

printf("%d",p->data);//访问节点

if(p->lchild!=NULL)EnQueue(&q,p->lchild);//左孩子入队

if(p->rchild!=NULL)EnQueue(&q,p->rchild);//右孩子入队

}

DestroyQueue(&q);//销毁队列

}

//6.求二叉树深度

intBiTreeDepth(BiTreeT){

if(T==NULL)return0;//空树深度为0

intleftDepth=BiTreeDepth(T->lchild);//左子树深度

intrightDepth=BiTreeDepth(T->rchild);//右子树深度

returnleftDepth>rightDepth?leftDepth+1:rightDepth+1;

}

//7.统计叶子节点个数

intCountLeaf(BiTreeT){

if(T==NULL)return0;//空树叶子数为0

if(T->lchild==NULL&&T->rchild==NULL){

return1;//叶子节点

}

returnCountLeaf(T->lchild)+CountLeaf(T->rchild);//递归统计

}

//8.查找指定值的节点（返回节点指针）

BiTNode*SearchNode(BiTreeT,inttarget){

if(T==NULL)returnNULL;//空树，未找到

if(T->data==target)returnT;//找到目标节点

BiTNode*leftNode=SearchNode(T->lchild,target);//左子树查找

if(leftNode!=NULL)returnleftNode;//左子树找到，返回

returnSearchNode(T->rchild,target);//右子树查找

}

//队列相关操作（若编译器不自带，自行实现）

typedefstructQueueNode{

BiTreedata;

structQueueNode*next;

}QueueNode,*QueuePtr;

typedefstruct{

QueuePtrfront,rear;//队头、队尾指针

}Queue;

//初始化队列

voidInitQueue(Queue*Q){

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QueueNode));

Q->front->next=NULL;

}

//判断队列是否为空

intQueueEmpty(QueueQ){

returnQ.front->next==NULL;

}

//入队

voidEnQueue(Queue*Q,BiTreee){

QueuePtrp=(QueuePtr)malloc(sizeof(QueueNode));

p->data=e;

p->next=NULL;

Q->rear->next=p;

Q->rear=p;

}

//出队

voidDeQueue(Queue*Q,BiTree*e){

if(QueueEmpty(*Q))return;

QueuePtrp=Q->front->next;

*e=p->data;

Q->front->next=p->next;

if(Q->rear==p)Q->rear=Q->front;

free(p);

}

//销毁队列

voidDestroyQueue(Queue*Q){

while(Q->front!=NULL){

QueuePtrp=Q->front;

Q->front=Q->front->next;

free(p);

}

}

//主函数

intmain(){

BiTreeT;

printf("请输入二叉树的先序遍历序列（空节点用#表示，例如12#4##3##）：\n");

CreateBiTree(&T);

printf("\n先序遍历结果：");

PreOrder(T);

printf("\n中序遍历结果：");

InOrder(T);

printf("\n后序遍历结果：");

PostOrder(T);

printf("\n层次遍历结果：");

LevelOrder(T);

printf("\n二叉树的深度：%d",BiTreeDepth(T));

printf("\n二叉树的叶子节点个数：%d",CountLeaf(T));

inttarget;

printf("\n请输入要查找的节点值：");

scanf("%d",&target);

BiTNode*node=SearchNode(T,target);

if(node!=NULL){

printf("找到节点，节点值为：%d\n",node->data);

}else{

printf("未找到该节点！\n");

}

return0;

}

七、实验结果与分析7.1实验输入先序遍历序列：12#4##3##查找节点值：47.2实验输出7.3结果分析构建正确性：根据输入的先序序列"12#4##3##"，成功构建出符合预期的二叉树。根节点为1，左子树以2为根，2的右孩子为4，4为叶子节点；根节点的右孩子为3，3为叶子节点，与输入序列完全匹配。遍历结果正确性：

先序遍历：1→2→4→3，符合先序遍历“根→左→右”的规则；中序遍历：2→4→1→3，符合中序遍历“左→根→右”的规则；后序遍历：4→2→3→1，符合后序遍历“左→右→根”的规则；层次遍历：1→2→3→4，符合“从上到下、从左到右”的规则。辅助操作正确性：二叉树深度为3，从根节点1到叶子节点4（或3）的最长路径为3个节点（1→2→4），结果正确；叶子节点个数为2，分别是4和3，结果正确；查找节点值4时，成功找到对应的节点并输出，查找功能正常；若输入不存在的节点值（如5），则输出“未找到该节点”，逻辑正确。程序运行稳定性：多次输入不同的先序序列（如空树"#"、单节点"5##"、复杂二叉树"123###4#5##"），程序均能正常运行，无崩溃、无异常输出，说明程序的边界处理和逻辑设计合理。八、实验总结与体会8.1实验总结本次实验围绕二叉树的构建与基本操作展开，成功实现了二叉链表的定义、二叉树的先序构建，以及先序、中序、后序、层次四种遍历方式，同时完成了求深度、统计叶子节点、查找节点等辅助操作。通过实验，验证了二叉树的逻辑特性和存储结构的实用性，掌握了