时时商务社区

标题: PHP构造二叉树算法示例 [打印本页]

作者: 新格网络 时间: 2018-2-14 05:25

         树（Tree）在数据结构还是很重要的，这里表示二叉树用括号表示法表示。先写一个二叉树节点类：
// 二叉树节点
class BTNode {
  public $data;
  public $lchild = NULL;
  public $rchild = NULL;
  public function __construct($data) {
$this->data = $data;
  }
}
然后构造二叉树：
function CreateBTNode(&$root,string $str)
{
  $strArr = str_split($str);
  $stack = [];
  $p = NULL; // 指针
  $top = -1;
  $k = $j = 0;
  $root = NULL;
  foreach ($strArr as $ch) {
switch ($ch) {
   case '(':
      $top++;
      array_push($stack, $p);
      $k = 1;
      break;
   case ')':
      array_pop($stack);
      break;
   case ',':
      $k = 2;
      break;
   default:
      $p = new BTNode($ch);
      if($root == NULL) {
      $root = $p;
      } else {
      switch ($k) {
         case 1:
            end($stack)->lchild = $p;
            break;
         case 2:
            end($stack)->rchild = $p;
            break;
      }
      }
      break;
}
  }
}
这里写上一个打印二叉树的函数（中序遍历）：
function PrintBTNode($node)
{
  if($node != NULL) {
PrintBTNode($node->lchild);
echo $node->data;
PrintBTNode($node->rchild);
  }
}
运行结果：
输入一个字符串
"A(B(C,D),G(F))"

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

您可能感兴趣的文章:

PHP实现二叉树的深度优先与广度优先遍历方法

PHP实现的线索二叉树及二叉树遍历方法详解

php实现的二叉树遍历算法示例

PHP完全二叉树定义与实现方法示例

PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

PHP实现判断二叉树是否对称的方法

PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

PHP实现按之字形顺序打印二叉树的方法

PHP获取二叉树镜像的方法

PHP实现从上往下打印二叉树的方法

欢迎光临时时商务社区 (http://bbs.4435.cn/)