如何从二叉树数据库中计算左或右 child 的数量

Question

这是我的假人 table

第一个节点是 1
LorR define child ini left(0) or Right(1)
1 st 节点有两个 child 节点 2 和 3 在左和右
2 nd 节点有两个 child 节点 4 和 5 在左和右
3 rd 节点在左和右有两个 child 节点 6 和 7
第4个节点左右有两个child节点8和9
第 5 个节点有一个 child 左边的节点 10
第 6 个节点有一个 child 左边的节点 11
第7个节点右边有一个child节点12

现在如果我想找到每个级别中任何 parent 节点的总 child 节点数例如...

节点 2 (parent) 在级别 1 和 2 child 节点 (8,9) 中有一个 2 child (4,5) 在第 2 级
节点 6 (parent) 在级别 1
节点 3 (parent) 在级别 1 和 2 child 节点中有 2 child (6,7) (11,12) 级别 2

如何使用 php 实现此功能？我的代码是 code

Answer 1

根据我的理解，您应该将 table 转换为信息丰富的 PHP 数组，例如：

$a = array(
    1 => array(
        'children' => array(
            array(2, 'left'),
            array(3, 'right'),
        ),
        'level' => 0
    ),
    2 => array(
        'children' => array(
            array(4, 'left'),
            array(5, 'right'),
        ),
        'level' => 1
    ),
...        
    12 => array(
        'children' => array(),
        'level' => 3
    ),
);

这个任务很简单，只需获取 table 然后 foreach 并将每一行分配到关联的数组中。这是获取所有 children 计数的函数：

function getChildrenCount($nodeId, $a, $rootLevel)
{
    $leftChildren = array();
    $rightChildren = array();
    $countCurrentNode = 0;
    $level = $a[$nodeId]['level'] - $rootLevel;
    if (empty($a[$nodeId]['children'])) {
        return array($level => 1);
    } else {
        foreach ($a[$nodeId]['children'] as $children) {
            if ($children[1] == 'left') {
                $leftChildren = getChildrenCount($children[0], $a, $rootLevel);
                $countCurrentNode++;
            }
            if ($children[1] == 'right') {
                $rightChildren = getChildrenCount($children[0], $a, $rootLevel);
                $countCurrentNode++;
            }
        }

        $current = $leftChildren;
        foreach ($rightChildren as $rightLevel => $count) {
            if (isset($current[$rightLevel])) {
                $current[$rightLevel] += $count;
            } else {
                $current[$rightLevel] = $count;
            }
        }
        $current[$level] = $countCurrentNode;
        return $current;
    }
}

思路是递归遍历每个节点，然后根据其层级（与根层级相比）计算children个数

如何调用：

getChildrenCount(2, $a, $a[2]['level'])

它将return array(level => count):

array (size=3)
0 => int 2 // level 1
1 => int 3 // level 2
2 => int 3 // Should be removed

那么您应该删除最后一个元素 - 它没有用，因为它用于按级别计数 child。

注：

它应该有更好的方法来组织数据（数组 $a），以便更容易地实现 getChildrenCount()。
这段代码没有仔细测试，只是结合了一些案例。

如何从二叉树数据库中计算左或右 child 的数量

how to count no of left or right child from binary tree database

php

mysql

phpmyadmin