实验05：二叉树遍历

数据结构实验与课程设计实验

二叉树遍历2012年xx月xx日深圳大学计算机与软件学院白鉴聪

实验五 串应用--KMP算法实验一、实验目的 掌握二叉树的基本概念 一、实验目的 掌握二叉树的链式存储结构 掌握二叉树的三种遍历算法 掌握二叉树的三种遍历算法实现(C++)

实验五 串应用--KMP算法实验二、实验要求二、实验要求 熟悉C++语言编程

熟练使用C++语言实现二叉树链式结构建立 完成先序、中序、后序三种遍历算法

实验五 串应用--KMP算法实验三、实验内容1、问题描述

给定一颗二叉树的逻辑结构(先序遍历的结 果，空树用字符‘0’表示，如下图的二叉树 ，可表示为AB0C00D00),建立该二叉树 的二叉链式存储结构

实验五 串应用--KMP算法实验三、实验内容1、问题描述

建树流程

取序列中的字符 若当前字符为字符‘0’,则建一个空树，即 T=NULL;否则 创建一个二叉树的结点，并把引用赋给T,节点 的数据域赋值为当前字符 递归创建T的左子树 递归创建T的右子树5

实验五 串应用--KMP算法实验三、实验内容2、算法

先序遍历算法 若二叉树为空，则返回；否则： 访问根节点(D) 先序遍历左子树(L) 先序遍历右子树(R)

实验五 串应用--KMP算法实验三、实验内容2、算法

中序遍历算法 若二叉树为空，则返回；否则： 中序遍历左子树(L) 访问根节点(D) 中序遍历右子树(R)

实验五 串应用--KMP算法实验三、实验内容2、算法

后序遍历算法 若二叉树为空，则返回；否则： 后序遍历左子树(L) 后序遍历右子树(R) 访问根节点(D)

实验五 串应用--KMP算法实验三、实验内容3、输入

第一行输入一个整数t,表示有t个测试数据 第二行起输入每个二叉树的先序遍历，连续输 入 t行

实验五 串应用--KMP算法实验三、实验内容4、输出

输出每个二叉树的先序遍历、中序遍历和后 序遍历结果，分三行输出

实验五 串应用--KMP算法实验三、实验内容5、输入样本2 AB0C00D00 AB00C00

实验五 串应用--KMP算法实验三、实验内容6、输出样本ABCD BCAD CBDA ABC BAC BCA

实验五 串应用--KMP算法实验四、实验步骤1、二叉树结点和二叉树类的定义，包括构造函 数、析构函数

2、二叉树创建与销毁函数3、二叉树三种遍历函数 4、主程序13

实验五 串应用--KMP算法实验1 二叉 树结 点定 义

实验五 串应用--KMP算法实验2 二叉 树类 定义

实验五 串应用--KMP算法实验3 销毁 与创 建函 数