【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;
    }

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

查看所有标签

猜你喜欢:

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

Distributed Algorithms

Distributed Algorithms

Wan Fokkink / The MIT Press / 2013-12-6 / USD 40.00

This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentat......一起来看看 《Distributed Algorithms》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具