4

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

在此处输入图像描述

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

例如

  1. 如果给定的父节点是 1，那么函数必须返回节点 4，因为它有可用的位置。
  2. 如果给定的父节点是 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。但在下一次迭代中，我需要检查@节点 7，因为节点将按照 5 的顺序排列到 n 并且它不是有限的树结构。

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

4

1 回答 1

1

我仍在思考，但比遍历树快得多的是每个可能位置的 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 行中的所有子节点都有

  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
}

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

于 2013-05-03T15:29:44.600 回答