上一篇我们简单介绍了什么是二叉搜索树，并实现了结构。在本文中，我们将研究如何遍历二叉树。常用的三种遍历方法是“前序”、“中序”和“后序”。对于二级搜索树，中序遍历只能得到一个有序的结果（即排序）。三种遍历方式的定义如下：从根节点开始，沿二叉树的外缘逆时针方向（访问左子树），遍历每个节点三次，最后回到根节点。前序：访问一个节点是在第一次经过该节点（根节点->左节点->右节点）时进行的。Inorder：访问一个节点是在第二次经过该节点时（左节点->根节点->右节点）。后序：访问节点是在第三次经过该节点（左节点->右节点->根节点）时进行的。多云或有雾都没关系。让我们画一幅画。注意箭头方向有两个子节点，比较容易理解。比如节点D只有一个子节点是I。所以先是D还是I，还是搞不懂。那我们再画一张图，注意数字。在上图的基础上，结合上一个节点的实现，所有节点都有两个子节点，但有的子节点为null。对于所有没有两个叶子节点的节点，我们用空节点填充两个。这么清楚吗？接下来，我们将这个想法转化为代码实现。publicfunctionpreOrder(){$stack=[];//先访问根节点$current=$this->root;$pre=[];while(!empty($stack)||$current!=null){//访问左子树while($current!=null){$pre[]=$current->data;$堆栈[]=$当前；$current=$current->left;}$current=array_pop($stack);//访问右子树$current=$current->right;}返回$pre;}publicfunctioninOrder(){$stack=[];//先访问根节点$current=$this->root;$排序=[];while(!empty($stack)||$current!=null){//访问左子树while($current!=null){$stack[]=$current;$current=$current->left;}$current=array_pop($stack);$sort[]=$current->data;//访问右子树$current=$cur租金->权利；}返回$排序；}publicfunctionpostOrder(){$stack=[];$visitStack=[];$current=$this->root;while($current!=null){$visitStack[]=$current;如果($current->left!=null){$stack[]=$current->left;}if($current->right!=null){$stack[]=$current->right;}$current=array_pop($stack);}$下一个=[];while($current=array_pop($visitStack)){$next[]=$current->data;}返回$下一个；}示例还是上一篇的二叉树实例，验证一下$arr=$bst->preOrder();echo"preorder:",implode('',$arr),PHP_EOL;$arr=$bst->inOrder();echo"按顺序:",implode('',$arr),PHP_EOL;$arr=$bst->postOrder();echo"后顺序:",implode('',$arr),PHP_EOL;
