PHP实现二叉树的深度广度优先遍历算法步骤详解

/**
* 中序遍历（递归方法）
*/
私有函数 mid_order1($root)
{
    if (!is_null($root)) {
      $函数=函数；
      $this->$function($root->left);
      回显 $root->key 。 “”；
      $this->$function($root->right);
    }
}
/**
* 中序遍历（非递归方法）
* 因为遍历完根节点还要回来，所以必须保存。考虑到后进先出的特点，选择栈存储。
*/
私有函数 mid_order2($root)
{
    如果 (is_null($root)) {
      返回;
    }
    $stack = new splstack();
    $节点=$根；
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        $stack->push($node);
        $node = $node->左；
      }
      $node = $stack->pop();
      回显 $node->key 。 ' ';
      $node = $node->右；
    }
}
//中序遍历
公共函数 MidOrder()
{// $this->mid_order1($this->tree->root);
    $this->mid_order2($this->tree->root);
}

/**
* 后序遍历（递归方法）
*/
私有函数 post_order1($root)
{
    if (!is_null($root)) {
      $函数=函数；
      $this->$function($root->left);
      $this->$function($root->right);
      回显 $root->key 。 “”；
    }
}
/**
* 后序遍历（非递归方法）
* 因为遍历完根节点还要回来，所以必须保存。考虑到后进先出的特点，选择栈存储。
* 由于访问左子节点后很难跳转到右子节点，所以这里使用了一个标记lastVisited来标识最后访问的节点。
*/
私有函数 post_order2($root)
{
    如果 (is_null($root)) {
      返回;
    }
    $节点=$根；
    $stack = new splstack();
    //保存最后访问的节点引用
    $lastVisited = NULL;
    $stack->push($node);
    while(!$stack->isEmpty()){
      $node = $stack->top();//获取栈顶元素，但不弹出
      if(($node->left == NULL && $node->right == NULL) || ($node->right == NULL && $lastVisited == $node->left) || ($lastVisited == $节点->右)){
        回显 $node->key。' ';$lastVisited = $node;
        $stack->pop();
      }别的{
        if($node->右){
          $stack->push($node->right);
        }
        if($node->左){
          $stack->push($node->left);
        }
      }
    }
}
//后序遍历
公共函数 PostOrder()
{
    // $this->post_order1($this->tree->root);
    $this->post_order2($this->tree->root);
}

/**
* 层级遍历（递归方法）
* 由于是逐层遍历，所以传递的是树的层数
*/
私有函数 level_order1($root,$level){
    if($root == NULL || $level < 1){
      返回;
    }
    如果（$级别== 1）{
      回显 $root->key。' ';
      返回;
    }
    if(!is_null($root->left)){
      $this->level_order1($root->left,$level - 1);
    }
    if(!is_null($root->right)){
      $this->level_order1($root->right,$level - 1);
    }
}
/**
* 层级遍历（非递归方法）
*每层输出从左到右
元素的存储需要具有先进先出的特性，因此采用队列存储。
*/
私有函数 level_order2($root){
    如果（is_null（$root））{返回;
    }
    $节点=$根；
    // 利用队列实现
// $queue = array();
// array_push($queue,$node);
//
// while(!is_null($node = array_shift($queue))){
// 回显 $node->key。' ';
// if(!is_null($node->left)){
// array_push($queue,$node->left);
// }
// if(!is_null($node->right)){
// array_push($queue,$node->right);
// }
// }
    $queue = new splqueue();
    $queue->enqueue($node);
    while(!$queue->isEmpty()){
      $node = $queue->dequeue();
      回显 $node->key。' ';
      if (!is_null($node->left)) {
        $queue->enqueue($node->left);
      }
      if (!is_null($node->right)) {
        $queue->enqueue($node->right);
      }
    }
}
// 层次遍历
公共函数 LevelOrder(){
// $level = $this->getdepth($this->tree->root);
// for($i = 1;$i <= $level;$i ++){
// $this->level_order1($this->tree->root,$i);
// }
    $this->level_order2($this->tree->root);}
//获取树的层数
私有函数 getDepth($root){
    如果（is_null（$root））{
      返回0；
    }
    $left = getdepth($root -> left);
    $right = getdepth($root -> right);
    $深度 = ($left > $right ? $left : $right) + 1;
    返回$深度；
}

类客户端
{
  公共静态函数 Main()
  {
    尝试 {
      //实现文件的自动加载
      函数自动加载($class)
      {
        包括 strtolower($class) 。 '.php';
      }
      spl_autoload_register('自动加载');
      $arr = 数组(10, 8, 12, 7, 9, 11, 13);
      $tree = new Bst();
// $tree = new Avl();
// $tree = new Rbt();
      $tree->init($arr);
      $traverse = 新的遍历($tree);
      $traverse->PreOrder();
// $traverse->MidOrder();
// $traverse->PostOrder();// $traverse->LevelOrder();
    } catch (异常$e) {
      回声 $e->getMessage();
    }
  }
}
客户端::Main();