在PHP中删除/折叠二叉树 - Delete/Collapse Binary Tree in PHP

Delete/Collapse Binary Tree in PHP

本文关键字：折叠二叉树删除 PHP | 更新日期: 2023-09-27

我有一个类似的表

----------------------------------
CUSTOMER_ID    | REF_CUSTOMER_ID |   
----------------------------------
1              | NULL            | 
2              | 1               | 
3              | 2               | 
4              | 2               | 
5              | 3               |
6              | 3               | 
7              | 4               |
8              | 4               |  
9              | 1               |  
----------------------------------

从该表可知，2是1的子，3，4是2的子等等。。这使得树看起来像这个

                1
                |
        ------------------
        |                |
        2                9
        |                |
    -----------     
    |        |                
    3        4   
    |        |
  -----    -----
  |   |    |   |
  5   6    7   8

好吧，在每个父母都有2个孩子和4片叶子之后，在这种情况下，2个孩子有3个和4个，叶子有5、6、7、8，树将不得不倒塌。这意味着它只会在树上留下1个。但由于2是1的子代，3，4是1的叶子，1还没有完成它的循环，所以1还不能崩溃。

问题

我如何仍然将2的树作为根倒下，但将1的树及其子树和叶子保持不变？我该如何处理？我必须创建另一个表吗？还是只使用现有的表

您不必使用额外的表，您可以使用递归删除树：

伪码：

function deleteChildBranches(node)
{
    get left and right child nodes
    if(there's left branch node)
       deleteANode(left branch node)
    if(there's right branch node)
       deleteANode(right branch node)       
}
function deleteANode(node)
{
    get left and right child nodes
    if(there's left branch node)
       deleteANode(left branch node)
    if(there's right branch node)
       deleteANode(right branch node)
    delete this node
}

这段代码将首先遍历一棵树到底部，从底部到顶部删除节点。