I09630126 - 实验三（二叉树的基本操作）

数据结构与算法课程实验报告

实验三：二叉树的基本操作

姓名：张宏

班级：09信息与计算科学1班 学号：I09630126

实验内容：

实现创建和遍历二叉树的基本操作 实验目的：

掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

问题描述：

（1） 编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建

立，并进行相应异常处理。

（2） 编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递

归或者非递归实现，遍历算法可在先序、中序和后序遍历算法中任选其一。

问题设计： 建立树的结构体

typedef struct BiTNode { // 结点结构 char data;

struct BiTNode *lchild, *rchild; // 左右孩子指针 } *BiTree;

用二叉链表lchild, rchild;分别表示其左右孩子指向，先建立二叉数的结构，建立二叉树也用先序的顺序输入，其数据用data 字符串型表示，当左右孩子为空时，用 k 表示空，则其data=null，否则则为输入的字符，并用递归实现,直至输入的当前值为空为止，就表示建立二叉树成功。 int cr(BiTree &t){

}

char k;

if(k=='k') t=NULL; else{ }

if(!(t=(BiTNode *)malloc(sizeof(BiTNode)))) return 0; t->data =k;

cr(t->lchild ); // 建立做子树 cr(t->rchild ); // 建立右子树

cin>>k;

return 0;

遍历二叉树，用的也是递归算法，所以比较简单，以输出的data为表示遍历该节点，三种遍历算法所以也相差不多。

void xianxu (BiTree T) { // 先序遍历二叉树 if (T) {

cout<data <<\; // 访问结点 xianxu(T->lchild); // 遍历左子树

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

void zhongxu (BiTree T) { // 中序遍历二叉树 if (T) {

zhongxu (T->lchild); // 遍历左子树 cout<data <<\; // 访问结点 zhongxu (T->rchild);// 遍历右子树 } }

void houxu (BiTree T) { // 后序遍历二叉树 if (T) {

houxu (T->lchild); // 遍历左子树 houxu(T->rchild);// 遍历右子树 cout<data <<\; // 访问结点 } }

实验截图：

总结：二叉树建立有很多种方法，有递归的算法和非递归的，递归的代码量和想法比非递归的相差很多，用递归的三个遍历除了访问节点外都差不多，主要是判断二叉树什么时候为空，什么时候结束，除了要求外，我还加了用递归算法的算叶子节点和深度的函数，感觉还比较 简单。

本文来源：https://www.bwwdw.com/article/nvet.html