本文共 6148 字，大约阅读时间需要 20 分钟。
前面文章介绍了二分搜索树的 前序遍历、中序遍历、后续遍历，这篇文章主要介绍一下如何使用 队列 实现二分搜索树的 层序遍历。
1.队列
1.1 队列的特点队列(Queue) 是一种线性结构。
只能从一端 tail(队尾) 添加元素，从另外一端 front(队首) 取出元素。
是一种 First In First Out(FIFO)，即 先进先出 的结构。
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 队列
这是通过带 尾指针 链表实现的 队列 类，它里面有 入队(enqueue) 方法和 出队(dequque) 方法 :<?php
/**
* 带有尾指针的链表
* Class LinkedListTail
*/
class QueueByLinkedList
{
private $head; //链表头部
private $tail; //链表尾部
private $size; //链表大小
/**
* 构造函数 初始化链表
* QueueByLinkedList constructor.
*/
public function __construct() {
$this->head = null;
$this->tail = null;
$this->size = 0;
}
/**
* 入队操作
* @param $e
*/
public function enqueue($e): void {
if ($this->tail == null) {
$this->tail = $this->head = new Node($e, null);
} else {
$node = new Node($e, null);
$this->tail->next = $node;
$this->tail = $node;
}
$this->size++;
}
/**
* 出队操作
* @return mixed
*/
public function dequeue() {
if ($this->size == 0) {
return "队列已经是空的";
}
$node = $this->head;
$this->head = $node->next;
$this->size--;
if ($node->next == null) {
$this->tail = null;
}
return $node->e;
}
public function getFront() {
if ($this->size == 0) {
return "队列已经是空的";
}
return $this->head->e;
}
public function getSize() {
return $this->size;
}
/**
* 判断队列是否为空
* @return bool
*/
public function isEmpty(): bool {
return $this->size == 0;
}
public function toString() {
$str = "";
for ($node = $this->head; $node != null; $node = $node->next) {
$str .= $node->e . "->";
}
$str .= "null";
return $str;
}
}
class Node
{
public $e;//节点元素
public $next; //下个节点信息
/**
* 构造函数 设置节点信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next) {
$this->e = $e;
$this->next = $next;
}
}
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 二分搜索树层序遍历
下面展示的都是部分代码，需要结合之前的，层序遍历 是按照节点深度一层一层的遍历：/**
* 层序遍历实现
*/
public function tierTraversalByLinkedList() {
$queue = new QueueByLinkedList();
//将根节点入队
$queue->enqueue($this->root);
//循环依次出队
$node = $queue->dequeue();
do {
if ($node != null) { //若出栈的当前节点不是空
echo $node->e . "
"; //然后打印当前节点信息$queue->enqueue($node->left);//左儿子入队
$queue->enqueue($node->right);//右儿子入队
} else { //若是空
echo "null
";}
//继续出队
$node = $queue->dequeue();
} while (!$queue->isEmpty());
}Tips：若不为空的节点没有儿子节点，这里实际处理它的儿子节点也会入栈 null。
下面是打印结果:<?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->tierTraversalByLinkedList();
/**
打印输出
45
30
55
25
35
50
65
15
27
31
null
48
null
60
68
null
null
null
null
null
null
null
null
null
null
null
*/Tips：可以看到打印输出结果和预期一致。
扫码关注爱因诗贤
转载地址：https://blog.csdn.net/weixin_28871097/article/details/116045910 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
