在PHP中，如何在每个子节点和孙子节点旁边打印最高级别的父节点

Question

我有一个PHP代码，使我能够创建与子节点和孙子节点映射的父节点数组。下面是我使用的代码:

<?php
function parent_map( &$a, $parent_key, $children_key )
{
    $orphans = true; $i;
    while( $orphans )
    {
        $orphans = false;
        foreach( $a as $k=>$v )
        {
            // is there $a[$k] sons?
            $sons = false;
            foreach( $a as $x=>$y )
            if( isset($y[$parent_key]) and $y[$parent_key]!=false and $y[$parent_key]==$k )  
            { 
                $sons=true; 
                $orphans=true; 
                break;
            }
            // $a[$k] is a son, without children, so i can move it
            if( !$sons and isset($v[$parent_key]) and $v[$parent_key]!=false )
            {
                $a[$v[$parent_key]][$children_key][$k] = $v;
                unset( $a[$k] );
            }
        }
    }
}
$ARRAY = array(
    1 => array( 'label' => "A" ),
    2 => array( 'label' => "B" ),
    3 => array( 'label' => "C" ),
    4 => array( 'label' => "D" ),
    5 => array( 'label' => "one", 'father' => '1' ),
    6 => array( 'label' => "two", 'father' => '1' ),
    7 => array( 'label' => "three", 'father' => '1' ),
    8 => array( 'label' => "node 1", 'father' => '2' ),
    9 => array( 'label' => "node 2", 'father' => '2' ),
    10 => array( 'label' => "node 3", 'father' => '2' ),
    11 => array( 'label' => "I", 'father' => '9' ),
    12 => array( 'label' => "II", 'father' => '9' ),
    13 => array( 'label' => "III", 'father' => '9' ),
    14 => array( 'label' => "IV", 'father' => '9' ),
    15 => array( 'label' => "V", 'father' => '9' ),
);
parent_map( $ARRAY, 'father', 'children' );
echo "<pre>"; print_r( $ARRAY);

?>

这可以给我一个父节点及其子节点和子节点的子节点的树结构，等等。

我需要的是数据转换从这个形式:

Parent Child
AAA   BBB
AAA   CCC
AAA   DDD
BBB   EEE
BBB   FFF
CCC   GGG
FFF   HHH
III   JJJ
JJJ   KKK
JJJ   LLL

到这个形式:

Node    1st Level Node
AAA     Root
BBB     AAA
CCC     AAA
DDD     AAA
EEE     AAA
FFF     AAA
GGG     AAA
HHH     AAA
III     Root
JJJ     III
KKK     III
LLL     III

本质上，我希望用它们各自的最高级根节点填充子节点，这样所有子节点都有一个根级数据/父映射到它们。

我试过在excel中使用VBA，它可以工作，但挂在大数据集中。一个解决方案是将所有数据一次输入并一起写入，但我不考虑宏解决方案。

这是我的VBA代码:

Option Explicit
Sub Main_Function_SuperManager()
Dim i, re
Root_Parent
Replace
Replace_Name
i = 1
    While Cells(i, 22) <> ""
         Cells(i, 22) = ""
         Cells(i, 23) = ""
         i = i + 1
    Wend
End Sub
Sub Root_Parent()
    Dim i, re, k
    i = 2
    While Cells(i, 1) <> ""
        Set re = Range("B:B").Find(Cells(i, 1))
        If re Is Nothing Then
            Set re = Range("V:V").Find(Cells(i, 1))
            If re Is Nothing Then
                k = k + 1
                Cells(k, 22) = Cells(i, 1)
                Cells(k, 23) = "Super Manager"
                findchild Cells(k, 22).Value, k
            End If
        End If
        i = i + 1
    Wend
End Sub
Sub findchild(parent, ByRef k)
 Dim i, s, re
 i = 1
    While Cells(i, 2) <> ""
    s = i
        Do
            Set re = Range("B:B").Find(Cells(s, 1))
            If re Is Nothing Then
                If Cells(s, 1) = parent Then
                k = k + 1
                Cells(k, 22) = Cells(i, 2)
                Cells(k, 23) = Cells(s, 1)
                End If
                Exit Do
            Else
                s = re.Row
            End If
        Loop
        i = i + 1
    Wend
End Sub
Sub Replace()
    Dim i, re, s
    i = 2
    While Cells(i, 22) <> ""
        Set re = Range("B:B").Find(Cells(i, 22))
        If re Is Nothing Then
        Cells(10, 24) = ""
        Else
         s = re.Row
         Cells(s, 19) = Cells(i, 23)
        End If
        i = i + 1
    Wend
End Sub
Sub Replace_Name()
    Dim i, re, s
    i = 2
    While Cells(i, 19) <> ""
        Set re = Worksheets("Sheet2").Range("A:A").Find(Cells(i, 19))
        If re Is Nothing Then
        Cells(10, 24) = ""
        Else
         s = re.Row
         Cells(i, 20) = Worksheets("Sheet2").Cells(s, 2)
        End If
        i = i + 1
    Wend
End Sub

我希望我能把同样的功能转换成PHP。我将从数据库中填充数组，但如何创建一个唯一的id/子列表到他们的最高级父/超级父节点是我无法弄清楚的。

期待同样的建议。

Answer 1

您可能应该使用Disjoint-set数据结构。该数据结构中的每个节点都包含对其父节点的引用，每个集合将由其root节点表示。如果您将此算法与路径压缩改进一起使用，则最终的父数组将正是您想要的。

对于这个问题，你应该首先像这样初始化父数组:

parent[A] = A
parent[B] = B
...

然后写入find函数，该函数递归地找到每个集合的根，并将其指定为路径中所有节点的父节点:

function find(x)
    if parent[x] == x: // x is root
        return x
    root = find(parent[x]) 
    parent[x] = root

下一步是处理边缘

for each U->V
    parent[V] = find(U) // finds the root of the tree that U belongs to
                        // and assign that as parent of V
A->B, find(A)=A, parent[B] <- A
A->C, find(A)=A, parent[C] <- A
A->D, find(A)=A, parent[D] <- A
B->E, find(B)=A, parent[E] <- A
B->F, find(B)=A, parent[F] <- A
C->G, find(C)=A, parent[G] <- A
F->H, find(C)=A, parent[F] <- H
I->J, find(I)=I, parent[J] <- I
J->K, find(J)=I, parent[K] <- J
J->L, find(J)=I, parent[L] <- J

Answer 2

修改表应该如下图

CREATE TABLE `parent_child` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `parent` varchar(255) DEFAULT NULL,
  `child` varchar(255) DEFAULT NULL,
  `parent_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=latin1

创建获取父/子元素的函数

DELIMITER $$
USE `yourdatabase`$$
DROP FUNCTION IF EXISTS `GetAllNode1`$$
CREATE DEFINER=`root`@`localhost` FUNCTION `GetAllNode1`(GivenID INT) RETURNS TEXT CHARSET latin1
    DETERMINISTIC
BEGIN
    DECLARE rv,q,queue,queue_children TEXT;
    DECLARE queue_length,front_id,pos INT;
    SET rv = '';
    SET queue = GivenID;
    SET queue_length = 1;
    WHILE queue_length > 0 DO
        SET front_id = queue;
        IF queue_length = 1 THEN
            SET queue = '';
        ELSE
            SET pos = LOCATE(',',queue) + 1;
            SET q = SUBSTR(queue,pos);
            SET queue = q;
        END IF;
        SET queue_length = queue_length - 1;
        SELECT IFNULL(qc,'') INTO queue_children
        FROM (SELECT GROUP_CONCAT(id) AS qc
        FROM `parent_child` WHERE `parent_id` = front_id) A ;
        IF LENGTH(queue_children) = 0 THEN
            IF LENGTH(queue) = 0 THEN
                SET queue_length = 0;
            END IF;
        ELSE
            IF LENGTH(rv) = 0 THEN
                SET rv = queue_children;
            ELSE
                SET rv = CONCAT(rv,',',queue_children);
            END IF;
            IF LENGTH(queue) = 0 THEN
                SET queue = queue_children;
            ELSE
                SET queue = CONCAT(queue,',',queue_children);
            END IF;
            SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
        END IF;
    END WHILE;
    RETURN rv;
END$$
DELIMITER ;

写查询

SELECT GetAllNode1(id) FROM parent_child 
or 
SELECT GetAllNode1(id) FROM parent_child  where id =1 //for specific parent's child element