二叉树的遍历实验报告

2024年2月7日发(作者：)

二叉树的遍历实验报告

一、实验目的

1.了解二叉树的存储结构。

2.掌握二叉树的遍历方式。

二、实验原理

1.二叉树的定义：

二叉树是一种特殊的树形结构，它的每个结点最多只能有两个子结点，分别称为左子结点和右子结点。

一般有两种存储方式，分别是顺序存储和链式存储。其中顺序存储需要用到数组，而链式存储则需要用到指针。

遍历二叉树的方式主要有三种，分别是前序遍历、中序遍历和后序遍历。其中前序遍历是先遍历根节点，然后遍历左子树和右子树；中序遍历是先遍历左子树，然后遍历根节点和右子树；后序遍历是先遍历左子树和右子树，然后遍历根节点。

三、实验步骤

typedef struct binaryTree {

char data; //数据域

struct binaryTree *left; //左子树

struct binaryTree *right; //右子树

} BTree;

2.创建二叉树：

BTree *createBTree(BTree *bt) {

char ch;

scanf("%c", &ch);

if (ch == '#') {

bt = NULL;

}

else {

bt = (BTree*)malloc(sizeof(BTree));

bt->data = ch;

bt->left = createBTree(bt->left); //递归创建左子树

bt->right = createBTree(bt->right); //递归创建右子树

}

return bt;

}

3.前序遍历：

6.测试代码：

四、实验结果分析

测试所得结果如下：

输入字符：AB#C##D#F##

前序遍历结果：ABCFD

中序遍历结果：BACFD

后序遍历结果：BCFD A

五、实验总结

通过本次实验，我了解了二叉树的基本概念和存储结构，掌握了二叉树的前、中、后序遍历方式的实现方法。这些知识对于我以后学习数据结构和算法，具有重要意义，对我的编程能力的提升也是有益的。