内容简介:上一篇 我们简单介绍了什么是二叉查找树,并实现了该结构。这一篇我们来看如何遍历二叉树。常用的三种遍历方式有“先序” “中序” “后序”。对于二次查找树来说,中序遍历刚好可以得到一个有序的结果(即排序)。三种遍历方式的定义如下从根结点出发,逆时针(访问左子树)沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。
上一篇 我们简单介绍了什么是二叉查找树,并实现了该结构。
这一篇我们来看如何遍历二叉树。常用的三种遍历方式有“先序” “中序” “后序”。对于二次查找树来说,中序遍历刚好可以得到一个有序的结果(即排序)。三种遍历方式的定义如下
从根结点出发,逆时针(访问左子树)沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。
- 先序:访问结点均是第一次经过结点时进行的(根节点 -> 左节点 -> 右节点)。
- 中序:访问结点均是第二次经过结点时进行的(左节点 -> 根节点 -> 右节点)。
- 后序:访问结点均是第三次经过结点时进行的(左节点 -> 右节点 -> 根节点)。
是不是看了云里雾里,没关系,我们来画个图,注意箭头方向
有两个子节点的好理解一点,像节点 D 只有一个节点是I,那这种到底是先D 还是先I,还是搞不明白。那我们再画一人图,注意数字。
上一个图的基础上,结合上一遍 的节点的实现,所有节点都有两个子节点,只不过有的子节点的是null。我们为所有没有两个叶子节点的节点以空节点来补齐两个。
这样子是不是很清晰了。
接下来我们把这个思路转化为代码实现。
public function preOrder() { $stack = []; // 先访问根结点 $current = $this->root; $pre = []; while (!empty($stack) || $current != null) { // 访问左子树 while ($current != null) { $pre[] = $current->data; $stack[] = $current; $current = $current->left; } $current = array_pop($stack); // 访问右子树 $current = $current->right; } return $pre; } public function inOrder() { $stack = []; // 先访问根结点 $current = $this->root; $sort = []; while (!empty($stack) || $current != null) { // 访问左子树 while ($current != null) { $stack[] = $current; $current = $current->left; } $current = array_pop($stack); $sort[] = $current->data; // 访问右子树 $current = $current->right; } return $sort; } public function postOrder() { $stack = []; $visitStack = []; $current = $this->root; while ($current != null) { $visitStack[] = $current; if ($current->left != null) { $stack[] = $current->left; } if ($current->right != null) { $stack[] = $current->right; } $current = array_pop($stack); } $next = []; while ($current = array_pop($visitStack)) { $next[] = $current->data; } return $next; }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构-二叉树遍历
- 数据结构基础:根据先序、中序遍历结果构造二叉树
- 【图解数据结构】 一组动画彻底理解二叉树三种遍历
- 数据结构 2 字符串 数组、二叉树以及二叉树的遍历
- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Linux内核设计与实现(原书第3版)
Robert Love / 陈莉君、康华 / 机械工业出版社华章公司 / 2011-4-30 / 69.00元
《Linux内核设计与实现(原书第3版)》详细描述了Linux内核的设计与实现。内核代码的编写者、开发者以及程序开发人员都可以通过阅读本书受益,他们可以更好理解操作系统原理,并将其应用在自己的编码中以提高效率和生产率。 《Linux内核设计与实现(原书第3版)》详细描述了Linux内核的主要子系统和特点,包括Linux内核的设计、实现和接口。从理论到实践涵盖了Linux内核的方方面面,可以满......一起来看看 《Linux内核设计与实现(原书第3版)》 这本书的介绍吧!