二叉树的遍历实现 | 小熊の小站

0 概述

本实验使用C++语言与指针实现了二叉树的遍历。

1 实验设计

1.1 算法实现原理

定义BinTreeNode节点为二叉树的一个结点。

一个结点拥有value, left 和 right属性。

其中 value 属性为结点的值，left 和 right 属性分别为左右子树的指针。

1.2 算法设计与分析

首先通过将二叉树补全成满二叉树的形式进行补全。

创建一个如图所示的树。

将其用 @ 补全成满二叉树输入，构建二叉树结构。

输入序列为 ABDF@@@E@G@@C@IJ@@K@@，其中 @ 为空节点，由此创建了一个二叉树结构。

本实验使用递归实现二叉树的前序，中序与后序遍历。

前序遍历：先访问根结点，再访问左子树，最后访问右子树。

中序遍历：先访问左子树，再访问根结点，最后访问右子树。

后序遍历：先访问左子树，再访问右子树，最后访问根结点。

本实验使用队列实现二叉树的层次遍历。

把每一层的所有子树放入队列中，然后从队列中取出子树，并逐个进行访问。

2 实验结果说明与分析

输出结果：

PreOrder: A B D F E G C I J K 
InOrder: F D B E G A C J I K 
PostOrder: F D G E B J K I C A 
LevelOrder: A B C D E I F G J K 

PreOrder: 前序遍历

InOrder: 中序遍历

PostOrder: 后序遍历

LevelOrder: 层次遍历

几种不同的遍历方式输出结果与构造的树预期遍历结果相同。

代码开源在：https://gitee.com/littlebear0729/data-structure-and-algorithm/tree/master/homework2