时间戳

首页 > 解决方案 > PHP：如何在二叉树上找到最左边的节点？

php - PHP：如何在二叉树上找到最左边的节点？

问题描述

假设我有这棵树：

         root
       /      \
      1        2
    /   \     /
   3     4   5
        /
       6
      /  \
     8    7
    /      \
   9       12
  /
10
  \
  11

我要选择root的话left，结果会是3。如果right，它会的2。

如果我选择6，那么左边将是10，右边将是12。

我一直在使用这个https://packagist.org/packages/kalnoy/nestedset。目前我一直在使用从上到下的递归来查找（从数据库中查询以查找下一个左孩子），但效率不高，因为树会变得更大。

我试过用这个（找到左边）：

if (!$child = self::where('parent_id', $this->id)->where('position', 'left')->first()) {
            return false;
        }

        if (!$grandChild = $child->leftChild()) {
            return $child;
        }

        $outerLeftChild = $child->descendants()->where('position', 'left')->whereIsLeaf()->get();

        if (count($outerLeftChild) <= 0) {
            $outerLeftChild = $child->descendants()->where('position', 'left')->hasChildren()->get();
            if (count($outerLeftChild) <= 0) {
                return $child;
            }
        }

        return $outerLeftChild->sortBy('_lft')->last();

但有时，它会找到错误的节点，比如如果我选择 root，它可能会选择10而不是3，_lft来自包我不知道它实际上做了什么。

我有level, position（左或右）和parent_id每个节点数据。每个节点最多只有 2 个节点（左和右），但它也可以是一个节点或根本没有节点。

谁能至少告诉我这个解决方案的理论？

标签： phplaraveltreebinary

解决方案

推荐阅读