我有一个树结构，其中每个节点都有 5 个子节点，并且不允许超过 5 个。我希望以广度优先搜索的方式遍历这棵树。

现在我想使用广度优先搜索方式从选定的父节点计算空节点。

例如

1. 如果给定的父节点为 1，则函数必须返回节点 4，因为它有可用的位置。
2. 如果给定的父节点是 2，那么它必须返回节点 7

我为此使用 PHP(codeigniter) + Mysql。

我的 Controller

public function addmember()
{
    $current_node = $this->input->post('member');
    $empty_location = $this->tree_model->GetEmptyPositions($current_node);
    if($empty_location != 0) {
        echo "Position available";
    }
    khác {
        $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;
    }
}

cơ sở dữ liệu

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。但在下一次迭代中，我需要检查@节点 7，因为节点将按顺序从 5 上升到 n，并且它不是有限树结构。

下一棵树的遍历顺序 7 8 9 10 11 12 13 14 16 ......

câu trả lời hay nhất

我还在想，但比遍历树快得多的是每个可能位置的 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|3, 1|4.

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

  col / 5 = 1

第3行的所有 child 都有

  col / 25 = 1

等等。

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

下面两层是节点 4|(50*5) 到 4|(55*5-1)

等等。

第三步

伪代码:

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
}

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

关于php - 广度优先搜索方式的一般树遍历(无限)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16340374/