PHP构造二叉树算法示例

树（Tree）在数据结构还是很重要的，这里表示二叉树用括号表示法表示。先写一个二叉树

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

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