PHP implements depth-first traversal (pre-order, mid-order, post-order) and breadth-first traversal (level) of binary trees

This article mainly introduces PHP to implement depth-first traversal (pre-order, mid-order, post-order) and breadth-first traversal (level) of binary trees. It analyzes in detail PHP's depth-first traversal and breadth-first traversal of binary trees in the form of examples. For related operating skills and precautions, friends in need can refer to the following

This article describes the implementation of depth-first traversal (pre-order, mid-order, post-order) and breadth-first traversal (level) of a binary tree in PHP. Share it with everyone for your reference, the details are as follows:

Foreword:

Depth-first traversal: for every possibility The branch path goes as deep as it can go no further, and each node can only be visited once. It is important to note that the depth-first traversal of a binary tree is special and can be subdivided into pre-order traversal, in-order traversal, and post-order traversal. The specific instructions are as follows:

Pre-order traversal: root node->left subtree->right subtree
In-order traversal: left subtree->root node->right subtree
Post-order traversal: left subtree->right subtree->root node

Breadth-first traversal: Also called hierarchical traversal, each layer is traversed from top to bottom. Access, in each layer, access nodes from left to right (or right to left). After accessing one layer, enter the next layer until no nodes can be accessed.

For example, for this tree:

Depth-first traversal:

Preorder traversal: 10 8 7 9 12 11 13
In-order traversal: 7 8 9 10 11 12 13
Post-order traversal: 7 9 8 11 13 12 10

Breadth-first traversal:

Level traversal: 10 8 12 7 9 11 13

The common non-recursive method of depth-first traversal of a binary tree is to use a stack, and the common non-recursive method of breadth-first traversal is to use a queue.

Depth first traversal:

1. Preorder traversal:

/**
* 前序遍历(递归方法)
*/
private function pre_order1($root)
{
    if (!is_null($root)) {
      //这里用到常量__FUNCTION__，获取当前函数名，好处是假如修改函数名的时候，里面的实现不用修改
      $function = __FUNCTION__;
      echo $root->key . " ";
      $this->$function($root->left);
      $this->$function($root->right);
    }
}
/**
* 前序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
*/
private function pre_order2($root)
{
    //    $stack = new splstack();
    //    $stack->push($root);
    //    while(!$stack->isEmpty()){
    //      $node = $stack->pop();
    //      echo $node->key.' ';
    //      if(!is_null($node->right)){
    //        $stack->push($node->right);
    //      }
    //      if(!is_null($node->left)){
    //        $stack->push($node->left);
    //      }
    //    }
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        //只要结点不为空就应该入栈保存，与其左右结点无关
        $stack->push($node);
        echo $node->key . ' ';
        $node = $node->left;
      }
      $node = $stack->pop();
      $node = $node->right;
    }
}
//前序遍历
public function PreOrder()
{
    // 所在对象中的tree属性保存了一个树的引用
    //   $this->pre_order1($this->tree->root);
    $this->pre_order2($this->tree->root);
}

Note: 1. I encapsulated all traversal methods in a class traverse. 2. In the pre_order2 method, when using the stack, I use splstack provided by the PHP standard library SPL. If you are used to using arrays, you can use array_push() and array_pop() Simulation implementation.

2. In-order traversal:

/**
* 中序遍历(递归方法)
*/
private function mid_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      echo $root->key . " ";
      $this->$function($root->right);
    }
}
/**
* 中序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
*/
private function mid_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        $stack->push($node);
        $node = $node->left;
      }
      $node = $stack->pop();
      echo $node->key . ' ';
      $node = $node->right;
    }
}
//中序遍历
public function MidOrder()
{
    //    $this->mid_order1($this->tree->root);
    $this->mid_order2($this->tree->root);
}

##3. Post-order traversal:

/**
* 后序遍历(递归方法)
*/
private function post_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      $this->$function($root->right);
      echo $root->key . " ";
    }
}
/**
* 后序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
* 由于在访问了左子节点后怎么跳到右子节点是难点，这里使用一个标识lastVisited来标识上一次访问的结点
*/
private function post_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $node = $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->right)){
        echo $node->key.' ';
        $lastVisited = $node;
        $stack->pop();
      }else{
        if($node->right){
          $stack->push($node->right);
        }
        if($node->left){
          $stack->push($node->left);
        }
      }
    }
}
//后序遍历
public function PostOrder()
{
    //    $this->post_order1($this->tree->root);
    $this->post_order2($this->tree->root);
}

Breadth-first traversal:

1. Level traversal:

/**
* 层次遍历(递归方法)
* 由于是按层逐层遍历，因此传递树的层数
*/
private function level_order1($root,$level){
    if($root == NULL || $level < 1){
      return;
    }
    if($level == 1){
      echo $root->key.&#39; &#39;;
      return;
    }
    if(!is_null($root->left)){
      $this->level_order1($root->left,$level - 1);
    }
    if(!is_null($root->right)){
      $this->level_order1($root->right,$level - 1);
    }
}
/**
* 层次遍历(非递归方法)
* 每一层从左向右输出
元素需要储存有先进先出的特性，所以选用队列存储。
*/
private function level_order2($root){
    if(is_null($root)){
      return;
    }
    $node = $root;
    //利用队列实现
//    $queue = array();
//    array_push($queue,$node);
//
//    while(!is_null($node = array_shift($queue))){
//      echo $node->key.&#39; &#39;;
//      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();
      echo $node->key.&#39; &#39;;
      if (!is_null($node->left)) {
        $queue->enqueue($node->left);
      }
      if (!is_null($node->right)) {
        $queue->enqueue($node->right);
      }
    }
}
//层次遍历
public function 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);
}
//获取树的层数
private function getdepth($root){
    if(is_null($root)){
      return 0;
    }
    $left = getdepth($root -> left);
    $right = getdepth($root -> right);
    $depth = ($left > $right ? $left : $right) + 1;
    return $depth;
}

Note: In the level_order2 method, when using the queue, I use the splqueue provided by the PHP standard library SPL. If you are used to using arrays If so, you can use

array_push() and array_shift() to simulate the implementation.

Usage:

Now let’s look at the client code:

class Client
{
  public static function Main()
  {
    try {
      //实现文件的自动加载
      function autoload($class)
      {
        include strtolower($class) . '.php';
      }
      spl_autoload_register('autoload');
      $arr = array(10, 8, 12, 7, 9, 11, 13);
      $tree = new Bst();
//      $tree = new Avl();
//      $tree = new Rbt();
      $tree->init($arr);
      $traverse = new traverse($tree);
      $traverse->PreOrder();
//      $traverse->MidOrder();
//      $traverse->PostOrder();
//      $traverse->LevelOrder();
    } catch (Exception $e) {
      echo $e->getMessage();
    }
  }
}
CLient::Main();

Supplement:

1. You can refer to the three classes Bst, Avl and Rbt used in the client. Previous article: "Detailed explanation of the graphic display function of drawing binary trees in PHP"

2. Why do I recommend that you use

splstack and splqueue provided in the SPL standard library? This is what I saw in an article: Although we can use traditional variable types to describe data structures, such as using arrays to describe stacks (Strack) - then use the corresponding methods pop and push (array_pop( ), array_push()), but you have to be careful, because after all, they are not specifically designed to describe data structures – one wrong operation may destroy the stack. SPL's SplStack object strictly describes data in the form of a stack and provides corresponding methods. At the same time, such code should also be able to understand that it is operating on a stack rather than an array, allowing your peers to better understand the corresponding code, and it will be faster. Original address: PHP SPL, the lost gem

3. Reference articles related to this article: "Detailed explanation of common operations on binary trees in C language [preorder, inorder, postorder, level traversal and non-recursive search, Count the number, compare, and find the depth]", "Java Implementation of Depth-First Traversal and Breadth-First Traversal Algorithms for Binary Trees"

Related recommendations:

PHP sorting algorithm bubbling Sort(Bubble Sort)

The above is the detailed content of PHP implements depth-first traversal (pre-order, mid-order, post-order) and breadth-first traversal (level) of binary trees. For more information, please follow other related articles on the PHP Chinese website!