给定这个二叉树(实际上,二叉树可以是随机的和动态的,这只是一个例子…):
见二叉树图片链接:二叉树示例
这是给定的事实:
- 所有节点都连接到它们的父节点,这样我们就可以从下到上(当然也可以从上到下)遍历。
- 所有节点在其左侧和右侧部分保存有多少后代的信息。
问题在于:我需要找到一种方法来计算关卡2中的节点总数(实际上,在任何关卡中都是如此,但现在让我们专注于关卡2)。显然,如果我们事先知道二叉树的结构,答案是3,但假设我们没有这个图像,只有给定的事实。
这里的另一个问题是,我们将从级别2(目标级别)的节点开始,而不是从根节点开始。在这个例子中,我选择了NODE f
我知道使用宽度优先遍历是直接的解决方案,但我发现它太耗时了,因为每次读取节点时,我都会从数据库中查询它。
我在寻找一种更实用的方法。但是,如果由于给出的数据不足而"不可能"解决这个问题,请让我知道需要提供哪些其他数据才能解决这个问题。我将评估它是否可行。
我正在创建一个网站,顺便使用PHP和MySQL。但我只想要解决方案的概念或解释,更像是一个算法,而不是一个编程片段或代码…
我希望有人能回答我…非常感谢!
"广度优先搜索"就是这样做的。但是,如果你不想使用它,我建议在节点中包含指向兄弟的指针。如果你必须执行这类查询,这将是一个很大的节省。
编辑:如果你可以反规范化你的节点,并在表中存储所有节点的兄弟姐妹和级别,那么你可以毫无问题地进行查询。
SELECT * FROM nodes where level=2
选项在php中加载完整的表,并创建一个数组树。如果您有很多行(100k+),您可以在表完成加载之前启动该进程,但是您需要更多的代码来控制它。
或者,您可以使用触发器将结果存储在每个节点。
EDIT:经过思考,阅读了不同的答案和评论。我认为最好的选择是拆分解决方案:
- 创建一个表nodesPerLevel,包含2列:level, nbNodes.
- 在每个节点插入/删除时创建一个触发器,在这个新表中添加/减去1对应的级别。
- 需要结果时,执行
select sum(nbNodes) from nodesPerLevel where level >= ?
对于DBMS中的树,您可以使用WITH RECURSIVE cte-idiom并在适当的递归级别剪切(==给定节点的递归级别,这可能需要另一个递归子选择)
编辑:(添加代码)
-- the test table
DROP table tree CASCADE;
CREATE table tree
( id CHAR(1) NOT NULL PRIMARY KEY
, pa CHAR(1) REFERENCES tree(id)
, le CHAR(1) REFERENCES tree(id)
, ri CHAR(1) REFERENCES tree(id)
);
-- generate some data
INSERT INTO tree (id, pa, le, ri) VALUES
( 'a', NULL, 'b', 'c' )
, ( 'b', 'a', 'd', 'e' )
, ( 'c', 'a', 'f', NULL )
, ( 'd', 'b', 'g', NULL )
, ( 'e', 'b', NULL, 'h' )
, ( 'f', 'c', NULL, 'i' )
, ( 'g', 'd', NULL, NULL )
, ( 'h', 'e', NULL, NULL )
, ( 'i', 'f', NULL, NULL )
;
-- a room with a view
CREATE VIEW reteview AS (
WITH RECURSIVE re AS (
SELECT 0 AS lev,id, pa, le, ri FROM tree
WHERE pa IS NULL
UNION
SELECT 1+re.lev AS lev
, tr.id, tr.pa, tr.le, tr.ri
FROM tree tr, re
WHERE re.id = tr.pa
)
SELECT * FROM re
);
/* EXPLAIN ANALYZE */ -- SELECT * FROM reteview ;
/* EXPLAIN ANALYZE */ SELECT re0.*
FROM reteview re0
, reteview re1
WHERE re1.id = 'f'
AND re0.lev <= re1.lev
;
结果: lev | id | pa | le | ri
-----+----+----+----+----
0 | a | | b | c
1 | b | a | d | e
1 | c | a | f |
2 | d | b | g |
2 | e | b | | h
2 | f | c | | i
(6 rows)
查询计划(Postgres 9.01)
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=949.93..2773.55 rows=35167 width=36) (actual time=0.159..0.337 rows=6 loops=1)
Join Filter: (re.lev <= re1.lev)
-> CTE Scan on re (cost=474.97..566.71 rows=4587 width=36) (actual time=0.034..0.151 rows=9 loops=1)
CTE re
-> Recursive Union (cost=0.00..474.97 rows=4587 width=36) (actual time=0.021..0.129 rows=9 loops=1)
-> Seq Scan on tree (cost=0.00..23.10 rows=7 width=32) (actual time=0.012..0.014 rows=1 loops=1)
Filter: (pa IS NULL)
-> Hash Join (cost=2.28..36.01 rows=458 width=36) (actual time=0.018..0.022 rows=2 loops=4)
Hash Cond: (tr.pa = re.id)
-> Seq Scan on tree tr (cost=0.00..23.10 rows=1310 width=32) (actual time=0.001..0.003 rows=9 loops=4)
-> Hash (cost=1.40..1.40 rows=70 width=12) (actual time=0.003..0.003 rows=2 loops=4)
Buckets: 1024 Batches: 1 Memory Usage: 1kB
-> WorkTable Scan on re (cost=0.00..1.40 rows=70 width=12) (actual time=0.001..0.002 rows=2 loops=4)
-> Materialize (cost=474.97..578.52 rows=23 width=4) (actual time=0.013..0.018 rows=1 loops=9)
-> Subquery Scan on re1 (cost=474.97..578.40 rows=23 width=4) (actual time=0.111..0.157 rows=1 loops=1)
-> CTE Scan on re (cost=474.97..578.17 rows=23 width=36) (actual time=0.110..0.156 rows=1 loops=1)
Filter: (id = 'f'::bpchar)
CTE re
-> Recursive Union (cost=0.00..474.97 rows=4587 width=36) (actual time=0.008..0.135 rows=9 loops=1)
-> Seq Scan on tree (cost=0.00..23.10 rows=7 width=32) (actual time=0.002..0.008 rows=1 loops=1)
Filter: (pa IS NULL)
-> Hash Join (cost=2.28..36.01 rows=458 width=36) (actual time=0.021..0.024 rows=2 loops=4)
Hash Cond: (tr.pa = re.id)
-> Seq Scan on tree tr (cost=0.00..23.10 rows=1310 width=32) (actual time=0.001..0.004 rows=9 loops=4)
-> Hash (cost=1.40..1.40 rows=70 width=12) (actual time=0.004..0.004 rows=2 loops=4)
Buckets: 1024 Batches: 1 Memory Usage: 1kB
-> WorkTable Scan on re (cost=0.00..1.40 rows=70 width=12) (actual time=0.001..0.001 rows=2 loops=4)
Total runtime: 0.764 ms
(28 rows)
除了从根完全读取树到第2级并计数实例之外,唯一的方法是在相同级别的实例之间设置关系字段,或者,如果您的数据太不稳定,这种方法无法更好地执行,则实现一个短时间但快速(内存?)缓存系统,该系统允许您快速识别相同级别的节点。
由于您的节点存储在数据库中,最好的解决方案可能是这样的SQL查询(语法可能是错误的):
select count(third.id) from node as first, node as second, node as third where first.id =`your top node id` and second.parent = first.id and third.parent = second.id
这样的查询将为您提供节点,而无需为每个单个节点额外访问DB。但是,对于您的数据库(取决于数据库和节点数量)来说,这可能代价高昂。您还可以将节点级别存储在节点本身中——这样查询会更简单,需要的资源也更少。
最简单的方法是
1。查找树的所有路径
50
/ '
30 60
/ ' / '
10 20 55 70
路径:
50-30-10
50-30-20
50-60-55
50-60-70
2。存储在单独的数组中。
3。访问每个数组的第k个元素
查找所有路径的sudo代码:
Inorder(root)
{
//do the required null checks
if(root==null)
return
1. PushOnStack(root->info)
2. Inorder(root->left)
3. peekAllStackElement (read all the elements in stack and store in array an reverse)
4. PopFromStack(root->info)
5. Inorder(root->right)
}
将数据放入二叉搜索树后,可以像下面这样递归它。使用递归跟踪树中每个节点的深度。
在每次递归调用时,将当前级别的节点推入哈希表,使用级别作为键,节点作为值。
在JavaScript中,您可以使用数组或对象字面值来完成此操作。我将所有内容存储在JavaScript对象字面量中,这类似于哈希表。这样的:level = 0
object[level] = [node1] => { '0': [node, node2] }
object[level] = [node2] => { '0': [node1, node2] }
level = 1
object[level] = [node3] => { '0': [node, node2], '1': [node3] }
等等……
在push之前,检查键是否存在。如果它不存在,只需将该节点插入到用数组包装的散列中。
如果一个键存在(意味着存在一个级别冲突),通过简单地将该键推入数组来调用冲突解决。
现在,每个级别的所有节点都存储在对象内的唯一数组中。它应该看起来像这样:
{ '0': [ 20 ],
'1': [ 8, 22 ],
'2': [ 4, 12, 24 ],
'3': [ 10, 14 ] } */
或者如果你存储整个节点:
{ '0': [ { value: 20, right: [Object], left: [Object] } ],
'1':
[ { value: 8, right: [Object], left: [Object] },
{ value: 22, right: [Object], left: null } ],
'2':
[ { value: 4, right: null, left: null },
{ value: 12, right: [Object], left: [Object] },
{ value: 24, right: null, left: null } ],
'3':
[ { value: 10, right: null, left: null },
{ value: 14, right: null, left: null } ] }
在这之后你可以对他们做你想做的事。将每个级别的值求和,转换为链表,或者在您的情况下,仅检查所需级别的数组长度。这将给出节点的数量。
BinaryTree.prototype.kNodesAtDepth = function(level) {
var levels = {};
var traverse = function(current, depth) {
if (!current) return null;
if (!levels[depth]) levels[depth] = [current.value];
else levels[depth].push(current.value);
traverse(current.left, depth + 1);
traverse(current.right, depth + 1);
};
traverse(this.root, 0);
return levels[level].length;
};
//tests
var bst = new BinaryTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
var nodeCount = bst.kNodesAtDepth(2); //3
console.log(nodeCount); //3