实验 3 二叉树及其应用
一、实验目的
1. 加深对二叉树结构的理解;
2. 熟练掌握二叉树的存储结构,特别是二叉链表类的描述及其实现方法;
3. 掌握二叉树的遍历算法原理和实现方法;
4. 学会编写对二叉树的各种操作算法;
5. 掌握二叉树结构的应用。
二、实验学时:建议 2~4 学时
三、实验内容
内容 1 二叉树及其操作
1 问题描述
以二叉链表结构存储二叉树,操作主要有创建二叉链表二叉树、遍历二叉树、统计该二叉
树中的结点个数等。
2 数据结构设计
根据问题要求,二叉树采用二叉链表结构存储。
(1) 二叉链表结点结构定义
template <class T>
struct btNode//二叉链表结点结构
{
T data; //二叉树中的元素
btNode<T> *lchild ,*rchild;
btNode():lchild(NULL),rchild(NULL){}//构造函数
btNode(T e,btNode<T> *l=NULL,btNode<T> *r=NULL)
:data(e),lchild(l),rchild(r){}
};
(2) 二叉链表类设计
二叉树的二叉链表类的数据成员主要有指向根结点的根指针,其成员函数有构造、创建、
遍历、统计结点个数、销毁等操作。
template <class T>
class binaryTree //二叉树的二叉链表类
{
private:
btNode<T>*root; //二叉树的根指针
T refValue;//二叉树结点为空标记
void create(btNode<T>*&r);// 先序创建二叉链表结构二叉树 r
void preOrder(btNode<T>*r);//先序遍历二叉树 r
void inOrder(btNode<T>*r);//中序遍历二叉树 r
void postOrder(btNode<T>*r);//后序遍历二叉树 r
int numOfNode(btNode<T>*r);//统计二叉树 r 中的结点个数