PHP implements pre-order, in-order and post-order traversal binary tree operation examples

This article mainly introduces PHP to implement pre-order, in-order and post-order traversal operations on binary trees based on non-recursive algorithms. It analyzes the principles of PHP using non-recursive algorithms to perform pre-order, in-order and post-order traversal operations on binary trees based on examples. Friends who need it can refer to the specific implementation techniques. I hope it can help everyone.

Overview:

The principle of binary tree traversal is as follows:

For the binary tree traversal shown in the above figure:

1. Preorder traversal: traverse the root node first, then traverse the left subtree, and finally traverse the right subtree.

ABDHECFG

2. In-order traversal: first traverse the left subtree, then traverse the root node, and finally traverse the right subtree.

HDBEAFCG

3. Post-order traversal: first traverse the left subtree, then traverse the right subtree, and finally traverse the root node.

HDEBFGCA

Implementation method:

Pre-order traversal: Using the first-in-last-out feature of the stack, first visit the root node, then push the right subtree, and then push left subtree. When taking it out in this way, the left subtree is taken out first, and the right subtree is taken out last.

function preorder($root){
 $stack = array();
 array_push($stack, $root);
 while(!empty($stack)){
  $center_node = array_pop($stack);
  echo $center_node->value; // 根节点
  if($center_node->right != null)
   array_push($stack, $center_node->right); // 压入右子树
  if($center_node->left != null)
   array_push($stack, $center_node->left); // 压入左子树
 }
}

In-order: It needs to be traversed from bottom to top, so first push the left subtree onto the stack, and then access the root nodes and nodes one by one Right subtree.

function inorder($root){
 $stack = array();
 $center_node = $root;
 while(!empty($stack) || $center_node != null){
  while($center_node != null){
   array_push($stack, $center_node);
   $center_node = $center_node->left;
  }
  $center_node = array_pop($stack);
  echo $center_node->value;
  $center_node = $center_node->right;
 }
}

Post-order: first store the root node, then store the left subtree and right subtree in sequence. Then output.

function tailorder($root){
 $stack = array();
 $outstack = array();
 array_push($$stack, $root);
 while($empty($stack)){
  $center_node = array_pop($stack);
  array_push($outstack, $center_node);
  if($center_node->right != null)
   array_push($stack, $center_node->right);
  if($center_node->left != null)
   array_push($stack, $center_node->left);
 }
 while($empty($outstack)){
  $center_node = array_pop($outstack);
  echo $center_node->value;
 }
}

Related recommendations:

How to use PHP to determine whether a binary tree is symmetrical

JavaScript to implement a binary tree Pre-order, in-order and post-order traversal methods

Detailed explanation of the binary tree traversal algorithm sample code implemented in PHP

The above is the detailed content of PHP implements pre-order, in-order and post-order traversal binary tree operation examples. For more information, please follow other related articles on the PHP Chinese website!