欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PHP构造二叉树算法示例

程序员文章站 2024-03-12 11:17:44
树(tree)在数据结构还是很重要的,这里表示二叉树用括号表示法表示。先写一个二叉树节点类: // 二叉树节点 class btnode { public...

树(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构造二叉树算法示例

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