二叉树的遍历实验心得(二叉树深度遍历和广度遍历)

大家好，今天来为大家解答二叉树的遍历实验心得这个问题的一些问题点，包括二叉树深度遍历和广度遍历也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~

二叉树的层序遍历用堆栈

要构建二叉树及对二叉树进行操作首先得构建节点，节点包括节点的值还有它的左右孩子，

对二叉树的操作有构建，遍历（递归，非递归，层次遍历）。栈的特点是先进先出，用栈能保留二叉树的访问路径，所以二叉树的非递归遍历应该用栈来操作，队列是先进后出，用来层次打印二叉树。

顺序存储的二叉树是如何创建和遍历的

一、首先，简单介绍一下什么是“二叉树”

二叉树是n个结点的有限集合，它的定义具有递归性：

（1）当n=0时，为空树；

（2）当n=1时，只有一个结点，该节点称为根结点；

（3）当n>1时，除了根结点外的其他节点可分为互不相交的两个子集，称为左右子树，且左右子树本质上也都是二叉树。

图1二叉树

根据二叉树的结构和定义，可总结出二叉树的特点：

（1）非空二叉树的第i层最多有2∧（i-1）个结点；

（2）深度为k的二叉树最多有2∧k-1个结点

二叉树的存储结构

二叉树是非线性的结构，其每个结点最多有一个“前驱”，但可以有多个“后继”。它可以采用顺序存储结构和链式存储结构。

1、顺序存储结构

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的结点。必须把二叉树的所有结点安排成一个恰当的序列结点在这个序列中的相互位置能反映出结点之间的逻辑关系。

要介绍顺序存储结构，首先要了解一个概念——完全二叉树。如果深度为k，有n个结点的二叉树，当k与n满足2∧(k-1)≦n≦2∧k-1时，该二叉树称为完全二叉树。

对于一个二叉树，如果其不是一个完全二叉树，则首先增添一些并不存在的空结点，使之称为一个完全二叉树的形式，然后按照从上到下、从左到右的顺序将树中的结点存储在数组中。

以图1为例，其补成完全二叉树如图2所示。

图2补完后的二叉树

其顺序存储状态为：

ABCDE∧H∧∧FGI

显然，当一个非完全二叉树采用顺序存储结构时，由于需要增加许多空结点，因此会造成空间的大量浪费。

2、链式存储结构

二叉树的链式存储结构是指用链来表示二叉树结点之间的逻辑关系。

通常的方法是链表中的每个结点由3个域组成：

左指针域＋数据域＋右指针域即：Lchild+data+Rchild其中：data域存放结点的数据信息；Lchild和Rchild分别存放左、右支的指针，当某一支不存在时，相应的指针域为空(用符号∧国NULL表示)。

如图1中的c结点，因其左支不存在，因此其Lchild的值为NULL。

三、二叉树的遍历算法

二叉树常用的遍历方式有：前序遍历、中序遍历、后续遍历以及层序遍历。

1、前序遍历

先访问根结点，然后是左子树，最后是右子树。

图1的前序遍历结果为：

A->B->D->E->F->G->C->H->I

2、中序遍历

先访问左子树，然后是根结点，最后是右子树。

图1的中序遍历结果为：

D->B->F->E->G->A->C->I->H

3、后续遍历

先访问左子树，然后是右子树，最后是根结点。

图1的后续遍历结果为：

D->>F->G->E->I->H->B->C->A

4、层序遍历

从顶层的结点开始，从左向右依次遍历，之后转到第二层，继续从左向右遍历，……，直到所有的结点都遍历完成。

图1的层序遍历结果为：

A->B->C->D->E->H->F->G->I

二叉树的后序遍历的为abcigopq

后序遍历就是先进行左子树，再进行右子树，最后根节点。

二叉树三种遍历顺序的特点

二叉树的遍历分为以下三种：

先序遍历：遍历顺序规则为【根左右】

中序遍历：遍历顺序规则为【左根右】

后序遍历：遍历顺序规则为【左右根】

某二叉树的后序遍历序列与中序遍历序列相同,均为ABCDEF,则前序遍历序列为什么

根据后序和中序，该二叉树如下：F/E/D/C/B/A所以前序遍历是：FEDCBA

一棵二叉树的中序遍历序列为：DGBAECHF，后序遍历序列为：GDBEHFCA，则前序列遍历序列是

不知道你理解前，中，后序遍历的概念没？

前序遍历又叫先根遍历，就是先访问根再访问左子树再访问右子树。

中序就是先访问左子树再访问根再是右子树。

后根就是先访问左子树然后是右子树最后是根。

简单的讲就是，你看后序遍历序列为：GDBEHFCA，最后一个是A，说明A是根。然后再去看中序遍历序列为：DGBAECHF，看到A在中间，把DGBAECHF分成DGB和ECHF两部分，好，现在单独看这两个子树，左子树DGB和右子树ECHF。

同样后序遍历序列GDBEHFCA中，找到DGB这三个字母，发现它是这样排列的，GDB，因为它是后跟遍历，所以子树DGB的根是B，这时候，你通过观察中序的DGB和后序的GDB，发现中序的右边没有东西，所以得出：子树GDB没有右支。同样的道理，发现子树ECHF的根是C，左子树只有E，右子树是HF。

像这样一步步分析

那么结论就是前序遍历是ABDGCEFH。

你最好能画个图就好理解多了。

图给你画了，有点丑，凑合看吧，呵呵。

END，本文到此结束，如果可以帮助到大家，还望关注本站哦！