一般树遍历（无限）以广度优先搜索方式 [英] General tree traversal(infinite) in breadth-first search manner

查看：270
本文介绍了一般树遍历（无限）以广度优先搜索方式的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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





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



例如


  1. 如果给定parent为1，则函数必须返回节点4，因为它有可用的位置。

  2. 如果给定的父级为2，则必须返回节点7

（codeigniter）+ Mysql for this。



我的控制器 

  public function addmember（）
 {
 $ current_node = $ this-> input-> post（'member'）; 
 $ empty_location = $ this-> tree_model-> GetEmptyPositions（$ current_node）; 
 if（$ empty_location！= 0）{
 echoPosition 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; 
}

和我的模型
$ b 

  //获取当前成员的空节点数
 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-& 
} 
 
 //获取当前节点的所有子节点
 public function GetAllChilds（$ id）{
 $ this-> db-> select '）; 
 $ 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 //存储如果零移动到下一个节点时剩余的空位数
`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 ......

解决方案

我还在想，树将是每个可能位置的position_id。如果你看一个完整的树的某一级别，你会看到我的意思 - 你的例子看起来像这样。



position和position_id之间的连接是简单int



子树中的所有节点共享一些属性 - 例如节点4的直接子节点（第二行中的第三节点）是数字

  1 + 5 +（3-1）* 5 + 1 
 1 + 5 + * 5 + 2 
 1 + 5 +（3-1）* 5 + 3 
 1 + 5 +（3-1）* 5 + 4 
 1 + 5 + ）* 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行中的所有子级都有

 第3行中的所有子级均具有
 
 $ b。
 
 
 $ b 
  col / 25 = 1 
  
 
 
 
 
节点2 | 10之下的一级是节点3 |（5×10）t 3 |（5×11-1）= 50..55-1 
 
 
 
以下两个级别是节点4 |（50 * 5）至4 |（55 * 5-1）
 
 
 
等。
 
 
 
步骤3 
 
 
 
伪代码：
  getFreeNode（$ node）{
 $ rowMax = 100; 
 $ row = $ node->行+ 1; 
 $ from = 5 * $ node-> col 
 $ to = $ from + 5; 
 while（$ row< = $ rowMax）{
 if（$ id = query（select id from member
。where row = $ row and col> = $ from和col< $ bis
。和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 
} 
  
请问是否需要更多详情。
 
I have a Tree Structure where each node has 5 child nodes and more than that are not allowed. I wish to traverse this tree in breadth-first search manner.






Now I wish to calculate empty node from selected parent using breadth-first search manner.



e.g.
    

  1. if given parent is 1, then function must return node 4 because it has positions available. 
    2. 

  2. If given parent is 2, then it must return node 7
    3. 

I am using PHP(codeigniter) + Mysql for this.



My controler
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;
}

and my model 
//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;
    }
}

Database
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;

Where I stuck up!



I am able to traverse till node 6 by above code. but in next iteration i have need to check @ node 7 since nodes will be in order 5 rase to n and  it is not finite tree structure.



next tree traversal order 7 8 9 10 11 12 13 14 16 ......
 解决方案 
I am still thinking, but much faster than traversing the tree would be a position_id for every possible position. If you look at a complete tree of a certain level you would see what I mean - your example looks like that.



The connections between position and position_id are something with simple int arithmetic (div and modulo).



All nodes in a subtrees share some of those properties - for example the direct subnodes of node 4 (third node in second row) are numbers 
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

So you still would have to traverse the levels in a loop, but not the nodes if you manage that position number in every node.



Step 2:



Row r has 5^r elements (starting with row 0).



Store in every node the row and the column, in every row the column starts with 0. So the second row is not 2,3,4,5,6 but is 1|0, 1|1, 1|2, 1|3, 1|4.



If your search root is 1|1 (row 1, second element, in your nice tree named "3"), then all children in row 2 have
  col / 5 = 1

all children in row 3 have
  col / 25 = 1

and so on.



One level below node 2|10 are nodes 3|(5*10) til 3|(5*11-1) = 50 .. 55-1



two levels below are nodes 4|(50*5) til 4|(55*5-1)



and so on.



Step 3



Pseudocode:
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
}

Please ask if more details are needed.


                        
这篇关于一般树遍历（无限）以广度优先搜索方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
相关文章
PHP最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆