PHP构造二叉树算法示例

树（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))"

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