上一篇介绍了二叉搜索树的前序遍历、中序遍历、后序遍历。本文主要介绍如何使用队列实现二叉搜索树的层序遍历。1.队列1.1队列的特点队列是一种线性结构。只能从一端尾部（队尾）添加元素，可以从另一端前端（队头）取元素。它是先进先出（FIFO），即先进先出的结构。1.2队列图1.??3链表这是一个封装好的链表类，可以实现链表的基本功能：null*LinkedList构造函数。*/publicfunction__construct(){$this->dummyHead=newNode(null,null);$this->size=0;}/***获取链表大小*@returnint*/publicfunctiongetSize():int{return$this->size;}/***判断链表是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->size==0;}/***在链表的索引位置添加一个元素*@paramint$index*@param$e*/publicfunctionadd(int$index,$e):void{if($index<0||$index>$this->size){echo"索引范围错误";出口;}$prve=$this->dummyHead;对于($i=0;$i<$index;$i++){$prve=$prve->next;}//将插入位置上一个位置的下一个节点指向插入位置传入节点，插入节点的下一个节点信息指向上一个节点的下一个节点$prve->next=newNode($e,$prve->next);$这个->尺寸++；}/***添加到链表的开头元素*@param$e*/publicfunctionaddFirst($e):void{$this->add(0,$e);}/***添加元素到链表的末尾*@param$e*/publicfunctionaddLast($e):void{$this->add($this->size,$e);}/***获取链表索引位置的元素*@param$index*/publicfunctionget($index){if($index<0||$index>$this->size){echo“索引范围错误”；出口;}$node=$this->dummyHead;对于($i=0;$i<$index+1;$i++){$node=$node->next;}返回$node->e;}/***获取链表的第一个元素*@returnmixed*/publicfunctiongetFirst(){return$this->get(0);}/***获取链表的最后一个元素*@returnmixed*/publicfunctiongetLast(){return$this->get($this->大小-1);}/***修改列表中的索引元素值*@param$index*@param$e*/publicfunctionupdate($index,$e){if($index<0||$index>$this->size){echo"不正确的索引范围";出口;}$node=$this->dummyHead;对于($i=0;$i<$index+1;$i++){$node=$node->next;}$node->e=$e;}/***判断一个元素是否存在于链表中*@param$e*@returnbool*/publicfunctioncontains($e):bool{for($node=$this->dummyHead->next;$node!=null;$node=$node->next){if($node->e==$e){返回真;}}返回真；}/***删除链表中index位置的元素*@param$index*/publicfunctionremove($index){if($index<0||$index>$this->size){echo"索引范围错误";出口;}如果（$this->size==0）{echo"列表为空";出口;}$prve=$this->dummyHead;对于($i=0;$i<$index;$i++){$prve=$prve->next;}$node=$prve->next;$prve->next=$node->next;$这个->大小--;返回$node->e;}/***删除链表的头元素*/publicfunctionremoveFirst(){return$this->remove(0);}/***删除链表末尾的元素*/publicfunctionremoveLast(){return$this->remove($this->size-1);}/***链表元素转换为字符串显示*@returnstring*/publicfunctiontoString():string{$str="";对于($node=$this->dummyHead->next;$node!=null;$node=$node->next){$str.=$node->e.“->”；}返回$str。“无效的”;}}classNode{public$e;//节点元素public$next;//Next节点信息/***构造函数设置节点信息*节点构造函数。*@param$e*@param$next*/公共函数__construct($e,$next){$this->e=$e;$this->next=$next;}}1.4Queue这是一个带尾指针的链表实现的队列类，有入队（enqueue）方法和出队（dequque）方法：head=null;$this->tail=null;$this->size=0;}/***入队操作*@param$e*/publicfunctionenqueue($e):void{if($this->tail==null){$this->tail=$this->head=newNode($e,空);}else{$node=newNode($e,null);$this->tail->next=$node;$this->tail=$node;}$this->size++;}/***出队操作*@returnmixed*/publicfunctiondequeue(){if($this->size==0){return"队列已经为空";}$node=$this->head;$this->head=$node->next;$这个->大小--;if($node->next==null){$this->tail=null;}返回$node->e;}publicfunctiongetFront(){if($this->size==0){return"队列已经为空";}返回$this->head->e;}publicfunctiongetSize(){return$this->size;}/***判断队列是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->size==0;}publicfunctiontoString(){$str="";对于($node=$this->head;$node!=null;$node=$node->next){$str.=$node->e.“->”；}$str.="空";返回$str;}}classNode{public$e;//节点元素public$next;//下一个节点信息/***构造函数设置节点信息*节点构造函数。*@param$e*@param$next*/publicfunction__construct($e,$next){$this->e=$e;$this->next=$next;}}2.二叉查找树层序遍历2.1节点定义2.3PHP代码定义NodeclassNode{public$e;公共$左=空；公共$right=null;/***构造函数初始化节点数据*节点构造函数。*@param$e*/publicfunction__construct($e){$this->e=$e;}}2.2原理解释利用队列的特性，从根节点开始，先将根节点放入队列，然后出队时，需要判断入队元素是否为空，如果不为空，处理它首先对于当前节点，先将左儿子节点放入队列，再将右儿子节点放入队列，以此类推，直到没有儿子节点，就可以继续出队下一个元素，直到队列为空，表示遍历完成。通过这个queue的思想可以达到按层次顺序遍历二叉查找树的目的。Tips：如果一个不为空的节点没有子节点，这里实际处理的子节点也会被null入栈。2.3实现原理图2.4二叉搜索树层次遍历下面是部分代码，需要结合前面的代码。层次遍历是根据节点深度逐层遍历：/***层次遍历实现*/publicfunctiontierTraversalByLinkedList(){$queue=newQueueByLinkedList();//入队根节点$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一起入栈。以下是打印结果：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*/*3055*//*25355065*////*152731486068**/$binarySearchTree->tierTraversalByLinkedList();请按预期查看打印输出。代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
