1. 首页
  2. PHP
  3. 数据结构-PHP 压栈遍历二分搜索树

数据结构-PHP 压栈遍历二分搜索树

码农天地 -
数据结构-PHP 压栈遍历二分搜索树

前面写了一篇的文章，实现的方法是用的递归思想遍历，这篇文章主要介绍一下如何使用 压栈 的思想来遍历二分搜索树。

1.栈

为了更好的结合压栈的思想，下面先来介绍一下 栈 数据结构的知识：

1.1 栈的特点栈是一种线性数据结构。栈只能从一端添加数据，也只能从同一端取出元素，每次删除的元素都是最后入栈的元素。入栈的元素具有后进先出的特点，即 Last In First Out(LIFO)。栈顶处理方法通常有 入栈(push)、出栈(pop)、查看栈顶(peek)。若是用 链表 数据结构实现的 栈，在 栈顶 会有一个 栈顶指针。栈 这种数据结构的应用举例，如：可以实现 撤销(undo)、程序的调用(系统栈)1.2 栈的图示

1.3 链表的实现

这是封装好的一个链表类，能实现链表的基本功能：

<?php
/**
 * 链表的实现
 * Class LinkedList
 */
class LinkedList
{
    private $dummyHead;
    private $size;
    /**
     * 初始化链表 null->null
     * LinkedList constructor.
     */
    public function __construct() {
        $this->dummyHead = new Node(null, null);
        $this->size = 0;
    }
    /**
     * 获取链表大小
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }
    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }
    /**
     * 在链表的第 index 位置添加元素
     * @param int $index
     * @param $e
     */
    public function add(int $index, $e): void {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        //将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点
        $prve->next = new Node($e, $prve->next);
        $this->size++;
    }
    /**
     * 向链表开头添加元素
     * @param $e
     */
    public function addFirst($e): void {
        $this->add(0, $e);
    }
    /**
     * 向链表末尾添加元素
     * @param $e
     */
    public function addLast($e): void {
        $this->add($this->size, $e);
    }
    /**
     * 获取链表第 index 位置元素
     * @param $index
     */
    public function get($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;
        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        return $node->e;
    }
    /**
     * 获取链表第一个元素
     * @return mixed
     */
    public function getFirst() {
        return $this->get(0);
    }
    /**
     * 获取链表最后一个元素
     * @return mixed
     */
    public function getLast() {
        return $this->get($this->size - 1);
    }
    /**
     * 修改链表中第 index 位置元素值
     * @param $index
     * @param $e
     */
    public function update($index, $e) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;
        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        $node->e = $e;
    }
    /**
     * 判断链表中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            if ($node->e == $e) {
                return true;
            }
        }
        return true;
    }
    /**
     * 删除链表中第 index 位置元素
     * @param $index
     */
    public function remove($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        if ($this->size == 0) {
            echo "链表已经是空";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        $node = $prve->next;
        $prve->next = $node->next;
        $this->size--;
        return $node->e;
    }
    /**
     * 删除链表头元素
     */
    public function removeFirst() {
       return $this->remove(0);
    }
    /**
     * 删除链表末尾元素
     */
    public function removeLast() {
       return $this->remove($this->size - 1);
    }
    /**
     * 链表元素转化为字符串显示
     * @return string
     */
    public function toString(): string {
        $str = "";
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            $str .= $node->e . "->";
        }
        return $str . "null";
    }
}
class Node
{
    public $e;//节点元素
    public $next; //下个节点信息
    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next) {
        $this->e = $e;
        $this->next = $next;
    }
}
1.4 调用链表实现的栈

这是一个封装好的 栈(Stack) ，通过实例化 链表类(LinkedList) 实现了入栈(push)和 出栈(pop)，还有查看栈顶(peek):

<?php
require 'LinkedList.php';
class StackByLinkedList
{
    //链表类对象，用于存放栈元素
    protected $array = null;
    /**
     * 构造函数 定义栈的容量
     * ArrayStruct constructor.
     * @param int $capacity
     */
    public function __construct() {
        $this->array = new LinkedList();
    }
    /**
     * 获取栈大小
     * @return int
     */
    public function getSize(): int {
        return $this->array->getSize();
    }
    /**
     * 判断栈是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->array->isEmpty();
    }
    /**
     * 元素入栈
     */
    public function push($e): void {
        $this->array->addFirst($e);
    }
    /**
     * 出栈
     * @return mixed
     */
    public function pop() {
        return $this->array->removeFirst();
    }
    /**
     * 查看栈顶元素
     * @return mixed
     */
    public function peek() {
        return $this->array->getFirst();
    }
    /**
     * 将栈数组转化为字符串
     * @return string
     */
    public function toString(): string {
        return $this->array->toString();
    }
}
2.二分搜索树压栈思想实现前序遍历2.1 节点定义
2.3 PHP 代码定义节点
class Node
{
    public $e;
    public $left = null;
    public $right = null;
    /**
     * 构造函数 初始化节点数据
     * Node constructor.
     * @param $e
     */
    public function __construct($e) {
        $this->e = $e;
    }
}
2.2 原理说明

这里以前序遍历为例进行说明，利用 栈 的特点，从跟节点开始，先把根节点入栈，然后出栈的时候需要判断出栈元素是否为空，若不为空则需要先把 右儿子节点入栈，然后 左儿子 节点入栈，依此类推直到没有儿子节点的时候就可以继续 出栈 下一个元素了，直到 栈 元素为空表示遍历完毕，通过这种 压栈 的思想可以达到 遍历二分搜索树 的目的。

Tips：若不为空的节点没有儿子节点，这里实际处理它的儿子节点也会入栈 null。2.3 实现原理图示

2.4 二分搜索树前序遍历压栈实现

下面展示的都是部分代码，需要结合之前的《数据结构-PHP 实现二分搜索树》，前序遍历操作就是把所有节点都访问一次，前序遍历 是先访问节点，再遍历左儿子树，然后再遍历右儿子树，要想达到这种效果，对于每个节点都是先处理当前节点，然后入栈右儿子，最后入栈左儿子，若出栈元素为空，打印 null 之后继续出栈：

Tips：若不为空的节点没有儿子节点，这里实际处理它的儿子节点也会入栈 null。
 /**
     * 前序遍历压栈实现
     */
    public function preTraversalByStack() {
        $stack = new StackByLinkedList();
        //将根节点压入栈
        $stack->push($this->root);
        //循环依次出栈
        $node = $stack->pop();
        do {
            if ($node != null) { //若出栈的当前节点不是空
                echo $node->e . "<br>"; //先打印当前节点信息
                //先入栈右儿子
                $stack->push($node->right);
                //然后入栈左儿子
                $stack->push($node->left);
            } else { //若是空
                echo "null<br>";
            }
            //继续出栈
            $node = $stack->pop();
        } while (!$stack->isEmpty());
    }

下面是打印结果:

<?php
require 'BinarySearchTree.php';
$binarySearchTree = new BinarySearchTree();
$binarySearchTree->add(45);
$binarySearchTree->add(30);
$binarySearchTree->add(55);
$binarySearchTree->add(25);
$binarySearchTree->add(35);
$binarySearchTree->add(50);
$binarySearchTree->add(65);
$binarySearchTree->add(15);
$binarySearchTree->add(27);
$binarySearchTree->add(31);
$binarySearchTree->add(48);
$binarySearchTree->add(60);
$binarySearchTree->add(68);
//下面是预期想要的结果
/**
 *                     45
 *           /                   
 *          30                   55
 *        /                    /    
 *      25       35         50       65
 *     /       /          /       /   
 *   15   27  31         48       60     68
 *
 */
//调用前序遍历的递归实现
$binarySearchTree->preTraversalByStack();
/**
打印输出
45
30
25
15
null
null
27
null
null
35
31
null
null
null
 */
Tips：可以看到打印输出结果和预期一致，并且和之前递归实现的方式一致，对于 中序遍历、后续遍历来说具体实现逻辑比 前序遍历 要复杂一些。

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
更多关于php的阅读
上一篇： php公众号链接提取文章标题、封面图、摘要、作者、公众号名称、简介、微信号、正文
下一篇： 数据结构-PHP 二分搜索树的层序遍历(队列实现)

Tags 标签

php算法程序员

扩展阅读

隐藏apache版本信息
2018-09-30 10:56:15 []
CentOS 6.5安装php5.6
2018-09-30 11:36:53 []
PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []
CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []
PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []
PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []
Linux php: command not found
2020-02-05 01:30:13 []
php 缓冲区 buffer 原理
2020-06-28 19:09:43 []
PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []

加个好友，技术交流

1628738909466805.jpg

码农天地

首页 HTML/CSS WEB服务器 PHP Linux 数据库 异常报错 插件工具 美文欣赏 站长直荐
友情链接：码农天地爱厂家深圳钻石回收麦思会议

Copyright © 2019-2024| 沪ICP备19030844号-2 | SiteMap