二叉树第一个不完整

Question

我有以下二叉树：

            [Node1]
    [Node2]        [Node3]
[Node4][Node5] [Node6][Node7]
     [...]          [...]

每个节点都有其唯一的 ID，节点单独存储并持有一个 'parent' 参数。

我需要的是获取第一个 'parent' 不完整的（即没有 2 个子节点的节点）； "first 'parent'" 我的意思是最接近根节点。

我尝试了一些循环，但总是只在一侧循环得到相同的结果...

更新：

这是无穷大，我想不确定是不是DFS

Answer 1

要找到树中满足条件的最浅节点，您需要使用 breadth first search。

它基本上看起来像这样，作为一个片段，以与语言无关的方式

q = empty queue
q.push(root)

while q is not empty
    current = q.pop
    if current meets condition
        return current
    for each child of current
        q.push(child)

这应该可以用任何语言实现，确保 q 实际上是一个 FIFO 队列。

Answer 2

结合这两个函数我得到了想要的结果：

function traverseTree( $id, $level=0 ) {
    static $depths = array();

    $depth++;

    $c = get_comments( array( 'type' => 'member', 'parent' => $id ) );

    if( count( $c ) < 2 ) {
        $depths[$id] = $level;
    }

    if( isset( $c[0] ) )
        traverseTree( $c[0]->comment_ID, $level+1 );

    if( isset( $c[1] ) )
        traverseTree( $c[1]->comment_ID, $level+1 );

    return $depths;
}

function depthChoose( $depths ) {
    return min( array_keys( $depths, min( $depths ) ) );
}

所以 depthChoose( traverseTree( $id ) ); 完成了工作。

注：$c[0]与node->left相同，$c[1]与node->right相同；

二叉树第一个不完整

Binary Tree first incomplete

php

algorithm

binary-search-tree