php - 如何在不使用广度优先顺序遍历的情况下找到二叉树第 k 层的节点数？

Question

给定这个二叉树（实际上，二叉树可以是随机的和动态的，这只是一个例子......）：

请参阅二叉树图像的链接：二叉树示例

这是给定的事实：

所有节点都连接到它们的父亲，以便我们可以从下到上（当然也从上到下）遍历。
所有节点都保存关于它们左右部分有多少后代的信息。

问题是这样的：我需要找到一种方法来计算级别 2 中的节点总数（实际上，在任何级别，但现在，让我们专注于级别 2）。显然，如果我们事先知道二叉树的结构，答案是 3，但假设我们没有这个图像，只有给定的事实。

这里的另一个问题是我们将从第 2 级（我们的目标级别）中的节点而不是根节点开始。在这个例子中，我选择了 NODE F。

我知道使用广度优先顺序遍历是直接的解决方案，但我发现它太耗时了，因为每次我读取一个节点时，我都会从数据库中查询它。

我正在寻找更实用的方法。但是，如果由于给定数据不足而“不可能”解决这个问题，请告诉我应该提供哪些其他数据才能解决这个问题。我会评估它是否可行。

顺便说一句，我正在创建一个网站，并使用 PHP 和 MySQL。但我只想要解决方案的概念或解释，更像是算法而不是编程片段或代码......

我希望有人能回答我...非常感谢！

score 2 · Accepted Answer

“广度优先搜索”就是这样做的方法。但是，如果您不想使用它，我建议在节点中包含指向兄弟的指针。如果您通常必须执行这种查询，那将是一个很大的节省。

编辑：

如果您可以非规范化您的节点并将所有节点的兄弟姐妹和级别存储在表中，那么您可以毫无问题地进行查询。

SELECT * FROM nodes where level=2

score 1 · Accepted Answer

一个选项是在 php 中加载完整的表，并创建一个数组树。如果你有很多行（100k+），你可以在表格加载完成之前开始这个过程，但是你需要更多的代码来控制它。

或者，您可以使用触发器将结果存储在每个节点上。

编辑：经过一番思考，阅读不同的答案和评论。我认为最好的选择是拆分解决方案：

创建一个表nodesPerLevel，有2个列：level，nbNodes。
在每个节点的插入/删除上创建一个触发器，将 1 添加/减去 1 到此新表中的相应级别。
当需要结果时，执行select sum(nbNodes) from nodesPerLevel where level >= ?

score 1 · Accepted Answer

对于 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)

score 0 · Accepted Answer

除了从根完全读取树直到级别 2 并计算实例之外，唯一的事情是在同一级别的实例之间设置一个关系字段，或者，如果您的数据太不稳定而无法更好地执行该方法，则实现一个简短的- 定时但快速（内存？）缓存系统，可让您快速识别同一级别的节点。

score 0 · Accepted Answer

由于您的节点存储在数据库中，最好的解决方案可能是这样的 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

像这样的查询将为您提供节点，而无需为每个节点额外访问数据库。但这对您的数据库来说可能代价高昂（取决于数据库和节点数量）。您还可以将节点级别存储在节点本身中 - 这样查询会更简单并且需要更少的资源。

score 0 · Accepted Answer

最简单的方法是

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)

 }

score 0 · Accepted Answer

将数据放入二叉搜索树后，您可以像下面这样递归它。使用递归来跟踪树中每个节点的深度。

在每次递归调用中，将当前级别的节点推送到哈希表，使用级别作为键，节点作为值。

在 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] }

ETC...

在推送之前，请检查密钥是否存在。如果它不存在，只需将节点插入到包含在数组中的散列中。

如果存在键（意味着存在级别冲突），则只需通过在该键处推送到数组来调用冲突解决方案。

现在，您将每个级别的所有节点都存储在对象内的唯一数组中。它应该如下所示：

{ '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

php - 如何在不使用广度优先顺序遍历的情况下找到二叉树第 k 层的节点数？

7 回答 7

Related

Reference