数据结构如何解遍历二叉树 树的遍历？

来源：蜘蛛抓取(WebSpider) 时间：2022-12-10 04:05 标签： 数据结构如何解遍历二叉树

 “树”是一种重要的数据结构，本文浅谈二叉树的遍历问题，采用C语言描述。

1）定义：有且仅有一个根结点，除根节点外，每个结点只有一个父结点，最多含有两个子节点，子节点有左右之分。

        在链式存储结构中，与线性链表类似，二叉树的每个结点采用结构体表示，结构体包含三个域：数据域、左指针、右指针。

        “遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，其遍历不像线性链表那样容易，无法通过简单的循环实现。

二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。

        在递归方式中，栈是由操作系统维护的，用户不必关心栈的细节操作，用户只需关心“访问顺序”即可。因而，采用递归方式实现二叉树的遍历比较容易理解，算法简单，容易实现。

大家知道，函数在调用时，会自动进行栈的push，调用返回时，则会自动进行栈的pop。函数递归调用无非是对一个栈进行返回的push与pop，既然递归方式可以实现二叉树的遍历，那么借用“栈”采用非递归方式，也能实现遍历。但是，这时的栈操作（push、pop等）是由用户进行的，因而实现起来会复杂一些，而且也不容易理解，但有助于我们对树结构的遍历有一个深刻、清晰的理解。

        首先考虑非递归先序遍历（NLR）。在遍历某一个二叉（子）树时，以一当前指针记录当前要处理的二叉（左子）树，以一个栈保存当前树之后处理的右子树。首先访问当前树的根结点数据，接下来应该依次遍历其左子树和右子树，然而程序的控制流只能处理其一，所以考虑将右子树的根保存在栈里面，当前指针则指向需先处理的左子树，为下次循环做准备；若当前指针指向的树为空，说明当前树为空树，不需要做任何处理，直接弹出栈顶的子树，为下次循环做准备。相应的C语言代码如下：

        对于非递归中序遍历，若当前树不为空树，则访问其根结点之前应先访问其左子树，因而先将当前根节点入栈，然后考虑其左子树，不断将非空的根节点入栈，直到左子树为一空树；当左子树为空时，不需要做任何处理，弹出并访问栈顶结点，然后指向其右子树，为下次循环做准备。

最后谈谈非递归后序遍历。由于在访问当前树的根结点时，应先访问其左、右子树，因而先将根结点入栈，接着将右子树也入栈，然后考虑左子树，重复这一过程直到某一左子树为空；如果当前考虑的子树为空，若栈顶不为空，说明第二栈顶对应的树的右子树未处理，则弹出栈顶，下次循环处理，并将一空指针入栈以表示其另一子树已做处理；若栈顶也为空树，说明第二栈顶对应的树的左右子树或者为空，或者均已做处理，直接访问第二栈顶的结点，访问完结点后，若栈仍为非空，说明整棵树尚未遍历完，则弹出栈顶，并入栈一空指针表示第二栈顶的子树之一已被处理。

        谈完二叉树的遍历之后，再来谈谈二叉树的创建，这里所说的创建是指从控制台依次（先/中/后序）输入二叉树的各个结点元素（此处为字符），用“空格”表示空树。

对于空树，函数直接返回即可；对于非空树，先读取字符并赋值给当前根结点，然后创建左子树，最后创建右子树。因此，要先知道当前要创建的树是否为空，才能做相应处理，“先序”遍历方式很好地符合了这一点。但是中序或后序就不一样了，更重要的是，中序或后序方式输入的字符序列无法唯一确定一个二叉树。我还没有找到中序/后序实现二叉树的创建（控制台输入）的类似简单的方法，希望各位同仁网友不吝赐教哈！

对于visit函数指针，可以这样简单的理解。visit是一个指针变量，它指向一个函数，这个函数的返回类型是int，这个函数的形参只有一个，也是int。那么怎么样表示这样一个指针才能让编译器知道visit是一个函数指针呢（即指向一个函数）？C标准给我们定了一个形式，就是 int (*visit) (int); 前一个int 表示返回类型，后一个int表示函数形参类型。 说到这里，我想起了之前我对此的一个误解。我之前以为这个被指向的函数肯定是这样的：int visit(int)；visit就是函数名。其实不是这样的，这个被指向的函数可以是这样的，int hanshu(int)。 另外，这个函数指针也不一定非得叫visit，也可以定义为 int (*v)(int)，v照样指向返回类型是int，形参类型是int的一个函数。 这是我当初看到visit的一些误区，我发现把这些误区弄清楚了，我就搞清楚了visit到底是什么了，希望对你有帮助。

又称二分树，它是有限的节点集合，这个集合或者是空，或者是由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。

他和度为2的树是不同的，差别在于

1、度为2的树中至少有一个节点的度为2，而二叉树没有这种要求

2、度为2的数不区分左右子树而二叉树严格区分左右子树。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

⑴访问结点本身（N），

⑵遍历该结点的左子树（L），

⑶遍历该结点的右子树（R）。

以上三种操作有六种执行次序：

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

常规的三种递归遍历方法

访问根节点，先序遍历左子树，先序遍历右子树

中序遍历左子树，访问根节点，中序遍历右子树

后序遍历左子树，访问根节点，后序遍历右子树。

关于层次遍历法从上到下从左到右遍历所有节点。

一般而言，先序遍历不会有什么问题，最主要的是中序遍历。

三种遍历结果(可以利用文章提供的算法验证正确性)如下

上面二叉树中序遍历的错误写法：

错误写法的关键在于错误的选择了E(F,G)二叉树作为遍历的起点，实际上我们应该选择D(,tree)作为遍历的起点。[其中tree指的E(F,G)]

中序遍历遍历二叉树的过程是：中序遍历左子树，访问根节点，中序遍历右子树。这表明二叉树的遍历是个递归过程，拿中序遍历的递归算法来说

中序遍历中选取的遍历起点应该是由整棵二叉树根节点一直往左持续延伸最后形成的叶子节点 。

此外 二叉树的中序遍历可以使用投影法来快速解决比如

二叉树遍历的算法源码：

//已建立二叉树根节点

二叉树的遍历分为前序遍历，中序遍历，后序遍历，层序遍历，在本文中，前三种由递归实现，层序遍历由队列实现。

C++实现二叉树的遍历

我要回帖

更多关于 数据结构如何解遍历二叉树 的文章

 

随机推荐