小熊の小站

Try my best.

二叉树的遍历实现

Littlebear0729's Avatar 2022-05-16 学习记

  1. 1. 0 概述
  2. 2. 1 实验设计
    1. 2.1. 1.1 算法实现原理
    2. 2.2. 1.2 算法设计与分析
  3. 3. 2 实验结果说明与分析

0 概述

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

1 实验设计

1.1 算法实现原理

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

一个结点拥有value, leftright属性。

其中 value 属性为结点的值,leftright 属性分别为左右子树的指针。

1.2 算法设计与分析

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

创建一个如图所示的树。

img.png

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

img_1.png

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

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

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

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

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

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

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

2 实验结果说明与分析

输出结果:

1
2
3
4
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

本文作者 : Littlebear0729
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
本文链接 : https://blog.hailres.xyz/2022/05/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86%E5%AE%9E%E7%8E%B0/

本文最后更新于 天前,文中所描述的信息可能已发生改变