乐趣区

关于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 原理阐明

这里以 前序遍历 为例进行阐明,利用  的特点,从跟节点开始,先把根节点 入栈 ,而后 出栈 的时候须要判断出栈元素是否存在儿子节点,若存在则须要先把 右儿子 节点入栈,而后 左儿子  节点入栈顺次类推直到没有儿子节点的时候就能够持续  出栈  下一个元素了,直到  元素为空示意遍历结束,通过这种 压栈  的思维能够达到  遍历二分搜寻树 的目标。

2.3 实现原理图示

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

上面展现的都是局部代码,须要联合之前的《数据结构 -PHP 实现二分搜寻树》,前序遍历操作就是把所有节点都拜访一次,前序遍历  是先拜访节点,再遍历左儿子树,而后再遍历右儿子树,要想达到这种成果,对于每个节点都是 先解决以后节点 而后入栈右儿子 ,最初 入栈左儿子,若出栈元素为空,打印 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…

扫码关注爱因诗贤

退出移动版