php – 以广度优先搜索方式进行的常规树遍历(无限)

发布时间：2020-12-13 22:48:29 所属栏目：PHP教程来源：网络整理

导读：我有一个树结构,其中每个节点有5个子节点,不允许多个节点.我希望以广度优先的搜索方式遍历这棵树. 现在我希望使用广度优先搜索方式从所选父节点计算空节点. 例如如果给定的父项为1,则函数必须返回节点4,因为它具有可用的位置. 如果给定父级是2,则它必须返回

我有一个树结构,其中每个节点有5个子节点,不允许多个节点.我希望以广度优先的搜索方式遍历这棵树.

现在我希望使用广度优先搜索方式从所选父节点计算空节点.

例如

>如果给定的父项为1,则函数必须返回节点4,因为它具有可用的位置.
>如果给定父级是2,则它必须返回节点7

我正在使用PHP(codeigniter)Mysql.

我的控制器

public function addmember()
{
    $current_node = $this->input->post('member');
    $empty_location = $this->tree_model->GetEmptyPositions($current_node);
    if($empty_location != 0) {
        echo "Position available";
    }
    else {
        $next_nodes = $this->tree_model->GetAllChilds($current_node);
        $i=0;
        for($i=0;$i<5;$i++){
            $result = $this->tree_model->GetEmptyPositions($next_nodes[$i]);
            if($result != 0 ) {
                $current_node = $next_nodes[$i];
                goto exe;
            }
        }

    }
    exe:
    echo $current_node;
}

和我的模特

//get number of empty nodes of current member
public function GetEmptyPositions($id) {
    $this->db->select('empty_position');
    $this->db->from('member');
    $this->db->where('member_id',$id);
    $result = $this->db->get();
    if ($result->num_rows() > 0)
        foreach($result->result() as $empty_pos)
            return $empty_pos->empty_position;
}

//get all childs of current node
public function GetAllChilds($id) {
    $this->db->select('member_id');
    $this->db->from('member');
    $this->db->where('tree_parent_id',$id);
    $result = $this->db->get();
    if ($result->num_rows() > 0) {
        $i = 0;
        foreach($result->result_array() as $member_id) {
            $member_array[$i] = $member_id['member_id'];
            $i++;
        }
        return $member_array;
    }
}

数据库

CREATE TABLE IF NOT EXISTS `member` (
   `member_id` int(11) NOT NULL AUTO_INCREMENT,`datetime` datetime DEFAULT NULL,`parent_id` int(11) DEFAULT NULL,`tree_parent_id` int(11) DEFAULT NULL,`empty_position` tinyint(4) DEFAULT '5',// stores how many empty positions remain if zero move to next node
   `name` varchar(20) COLLATE utf8_unicode_ci DEFAULT NULL,PRIMARY KEY (`member_id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

我坚持的地方！

我可以通过上面的代码遍历到节点6.但是在下一次迭代中,我需要检查@ node 7,因为节点将按顺序5到n并且它不是有限树结构.

下一个树遍历令7 8 9 10 11 12 13 14 16 ……

解决方法

我仍然在想,但是比遍历树要快得多的是每个可能位置的position_id.如果你看一个特定级别的完整树,你会看到我的意思 – 你的例子就是这样.

position和position_id之间的连接是简单的int算术(div和modulo).

子树中的所有节点共享其中一些属性 – 例如,节点4的直接子节点(第二行中的第三个节点)是数字

1 + 5 + (3-1)*5 +   1 
1 + 5 + (3-1)*5 +   2
1 + 5 + (3-1)*5 +   3
1 + 5 + (3-1)*5 +   4
1 + 5 + (3-1)*5 +   5

因此,如果您在每个节点中管理该位置编号,您仍然必须遍历循环中的级别,而不是遍历节点.

第2步：

行r有5 ^ r个元素(从第0行开始).

在每个节点中存储行和列,在列的每一行中以0开头.因此第二行不是2,3,4,5,6,而是1 | 0,1 | 1,1 | 2,1：1. 3,1 | 4.

如果您的搜索根是1 | 1(第1行,第二个元素,在名为“3”的漂亮树中),那么第2行中的所有子项都有

col / 5 = 1

第3排的所有孩子都有

col / 25 = 1

等等.

节点2 | 10下面的一个节点是节点3 |(5 * 10)直到3 |(5 * 11-1)= 50 .. 55-1

以下两级是节点4 |(50 * 5)直到4 |(55 * 5-1)

等等.

第3步

伪代码：

getFreeNode($node){
    $rowMax = 100;
    $row   = $node->row + 1;
    $from  = 5 * $node->col;
    $to    = $from + 5;
    while($row <= $rowMax){
        if ($id = query("select id from member " 
            ."where row = $row and col >= $from and col < $bis"
            ." and empty_position > 0"))
        {
            return $id;
        }
        $row++;
        $from *= 5;
        $to *= 5;
    }
}

insertNode($parent,$node){
    $node->row = $parent->row + 1;
    $node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
    $node->parent_id = $parent->member_id
}

请询问是否需要更多详细信息.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!