之前写过一篇文章，实现的方法是使用递归思想遍历，本文主要介绍如何使用推栈思想遍历二叉搜索树.1.栈为了更好的结合压栈的思想，我们先来介绍一下栈数据结构的知识：1.1栈的特点栈是一种线性数据结构。栈只能从一端添加数据，也只能从同一端取出元素。每次删除的元素都是栈上的最后一个元素。入栈的元素具有后进先出的特点，即后进先出（LIFO）。栈顶处理方式通常包括push、pop、peek。如果栈是用链表数据结构实现的，栈顶会有一个栈顶指针。Stack应用这种数据结构的例子，如：撤销（undo），程序调用（系统栈）可以实现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->下一个）；$这个->尺寸++；}/***添加元素到链表的开头*@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*/publicfunctionngetLast(){返回$this->get($this->size-1);}/***修改链表中index位置的元素值*@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){returntrue;}}}返回真；}/***删除链表中index位置的元素*@param$index*/publicfunctionremove($index){if($index<0||$index>$this->size){echo"索引范围错误";出口;}if($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;//下一个节点信息/***构造函数设置节点信息*节点构造函数。*@param$e*@param$next*/publicfunction__construct($e,$next){$this->e=$e;$this->next=$next;}}1.4调用链表实现的栈这是一个封装好的栈（Stack），通过实例化链表类（LinkedList）实现push和pop，查看栈顶：array=newLinkedList();}/***获取堆栈大小*@returnint*/publicfunctiongetSize():int{return$this->array->getSize();}/***判断栈是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->array->isEmpty();}/***元素被压入栈中*/publicfunctionpush($e):void{$this->array->addFirst($e);}/***pop*@returnmixed*/publicfunctionpop(){返回$this->array->removeFirst();}/***查看栈顶元素*@returnmixed*/publicfunctionpeek(){return$this->array->getFirst();}/***将堆栈数组转换为字符串*@returnstring*/publicfunctiontoString():string{return$this->array->toString();}}2.二叉查找树压栈实现前序遍历的思想2.1节点定义2.3PHP代码定义节点类Node{public$e;公共$左=空；公共$right=null;/***构造函数初始化节点数据*节点构造函数。*@param$e*/publicfunction__construct($e){$this->e=$e;}}2.2原理解释下面是一个前序遍历的例子。利用栈的特性，从根节点开始，先把根节点压入栈中，然后在出栈的时候需要判断栈元素是否为空，如果不为空，需要把右边子节点先入栈，然后左子节点入栈，以此类推，直到没有子节点，可以继续弹出下一个元素，直到栈元素为Empty表示遍历完成，思路遍历二叉查找树的过程可以通过这种压栈的思想来实现。2.3实现原理图2.4二叉查找树前序遍历压栈实现下面展示部分代码，需要结合前面的《数据结构-PHP 实现二分搜索树》。前序遍历操作是访问所有节点一次，前序遍历是先访问节点，然后遍历左子树，再遍历右子树。要实现这个效果，对于每个节点，先处理当前节点，然后将右儿子压入栈中，最后将左儿子压入栈中。如果出栈元素为空，打印null，继续出栈：提示：如果非空节点没有子节点，这里实际处理的子节点也会将null入栈。/***前序遍历压栈实现*/publicfunctionpreTraversalByStack(){$stack=newStackByLinkedList();//将根节点压入栈$stack->push($this->root);//循环逐个弹出栈$node=$stack->pop();do{if($node!=null){//如果当前出栈的节点不为空echo$node->e.“
”；//先打印当前节点信息//先推右子$stack->push($node->right);//然后压左子$stack->push($node->left);}else{//如果为空echo"null
";}//继续弹出$node=$stack->pop();}while(!$stack->isEmpty());}下面是打印结果：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**///调用序言递归实现oftraversal$binarySearchTree->preTraversalByStack();/**打印输出45302515nullnull27nullnull3531nullnullnull*/Tips:可以看到打印出来的结果和预期一致，和前面的递归实现一致。对于中序遍历和后序遍历具体实现逻辑比前序遍历代码仓库要复杂一些：https://gitee.com/love-for-po...扫码关注爱世贤
