search

Home  >  Article  >  Backend Development  >  Detailed explanation of the steps of binary tree depth and breadth first traversal algorithm in PHP

Detailed explanation of the steps of binary tree depth and breadth first traversal algorithm in PHP

php中世界最好的语言
php中世界最好的语言Original
2018-05-16 15:22:312386browse

This time I will bring you a detailed explanation of the algorithm steps for implementing depth and breadth-first traversal of binary trees in PHP. What are the precautions for implementing depth and breadth-first traversal of binary trees in PHP. Here are practical cases. Let’s take a look. .

Foreword:

Depth-first traversal: Go deep into every possible branch path until it can no longer go deeper. 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);
}

Explanation: 1. I will traverse all The methods are all encapsulated 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 <a href="http://www.php.cn/wiki/1001.html" target="_blank">array_push</a>() 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 . &#39; &#39;;
      $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.&#39; &#39;;
        $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;
}

Description: 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, you can use array_push() and array_shift() Simulation implementation.

Usage:

Now let’s look at the client code: 

class Client
{
  public static function Main()
  {
    try {
      //实现文件的自动加载
      function autoload($class)
      {
        include strtolower($class) . &#39;.php&#39;;
      }
      spl_autoload_register(&#39;autoload&#39;);
      $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();

Supplementary:

1. For the three classes Bst, Avl, and Rbt used in the client, you can refer to the 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

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the PHP Chinese website!

Recommended reading:

Detailed explanation of PHP simple selection sorting case

Detailed explanation of the steps to implement Huffman encoding/decoding in PHP

The above is the detailed content of Detailed explanation of the steps of binary tree depth and breadth first traversal algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!

Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：Detailed explanation of using PHP bubble sortNext article：Detailed explanation of using PHP bubble sort

Related articles

See more