【PHP 实现数据结构】遍历二叉查找树

栏目: IT技术 · 发布时间: 4年前

内容简介:上一篇 我们简单介绍了什么是二叉查找树,并实现了该结构。这一篇我们来看如何遍历二叉树。常用的三种遍历方式有“先序” “中序” “后序”。对于二次查找树来说,中序遍历刚好可以得到一个有序的结果(即排序)。三种遍历方式的定义如下从根结点出发,逆时针(访问左子树)沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。

上一篇 我们简单介绍了什么是二叉查找树,并实现了该结构。

这一篇我们来看如何遍历二叉树。常用的三种遍历方式有“先序” “中序” “后序”。对于二次查找树来说,中序遍历刚好可以得到一个有序的结果(即排序)。三种遍历方式的定义如下

从根结点出发,逆时针(访问左子树)沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。

  1. 先序:访问结点均是第一次经过结点时进行的(根节点 -> 左节点 -> 右节点)。
  2. 中序:访问结点均是第二次经过结点时进行的(左节点 -> 根节点 -> 右节点)。
  3. 后序:访问结点均是第三次经过结点时进行的(左节点 -> 右节点 -> 根节点)。

是不是看了云里雾里,没关系,我们来画个图,注意箭头方向

【PHP 实现数据结构】遍历二叉查找树

有两个子节点的好理解一点,像节点 D 只有一个节点是I,那这种到底是先D 还是先I,还是搞不明白。那我们再画一人图,注意数字。

【PHP 实现数据结构】遍历二叉查找树

上一个图的基础上,结合上一遍 的节点的实现,所有节点都有两个子节点,只不过有的子节点的是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;
    }

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Linux内核设计与实现(原书第3版)

Linux内核设计与实现(原书第3版)

Robert Love / 陈莉君、康华 / 机械工业出版社华章公司 / 2011-4-30 / 69.00元

《Linux内核设计与实现(原书第3版)》详细描述了Linux内核的设计与实现。内核代码的编写者、开发者以及程序开发人员都可以通过阅读本书受益,他们可以更好理解操作系统原理,并将其应用在自己的编码中以提高效率和生产率。 《Linux内核设计与实现(原书第3版)》详细描述了Linux内核的主要子系统和特点,包括Linux内核的设计、实现和接口。从理论到实践涵盖了Linux内核的方方面面,可以满......一起来看看 《Linux内核设计与实现(原书第3版)》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具