如何按级别的顺序打印二进制搜索树，包括零值

Question

因此，现在，当我有一棵看起来像这样的树时：

       5
         \
          6
           \
            7
             \
              9

我可以按级别的顺序打印它，以便

5, 
6, 
7, 
9, 

打印出来

，我想制作它，以便它打印出类似的东西：

5,
0, 6,
0, 0, 0, 7,
0, 0, 0, 0, 0, 0, 0, 9, 

以便所有无效的节点也被打印为0。

void current_height(tree *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%d, ", root->data);
    }
    else if(level > 1){
        current_height(root->left, level - 1);
        current_height(root->right, level - 1);
    }
}

这是我到目前为止的代码

，我还考虑将索引放入struct树中，以便我可以将树更改为阵列并打印数组。 但是我发现它会使删除功能过于复杂，所以我没有使用这个想法

Answer 1

首先，在每个节点上调用 Current_height （在该节点上遍历整个子树），使该算法效率低下。

您可以使用此想法：

• 创建一个用于存储当前节点级别的数组。确保它的大小可以包含底层。

• 在索引0存储根参考。

• 然后迭代级别：

• 打印当前数组中的节点的数据

• 用两个孩子替换每个节点 - 或当节点实际上是 null 时，请放两个 null null 数组中的值。

• 为了避免在读取数据之前覆盖该数据，请从最右边的节点向后填充数组到索引0，然后将子节点从右到左列入子节点。这样，父母就不会覆盖他们。

这是一个实现：

void level_order(tree *root) {
    if (root == NULL) return; // Nothing to print
    int h = height(root) - 1;
    tree *level[1<<h]; // Allocate 2^h entries 
    level[0] = root;
    for (int depth = 0; depth <= h; depth++) {
        for (int j = (1<<depth) - 1; j >= 0; j--) {
            tree *node = level[j];
            int isNode = node != NULL;
            printf("%d, ", isNode ? node->data : 0);
            if (depth < h) { // Collect children for next iteration
                level[2*j+1] = isNode ? node->left : NULL; 
                level[2*j] = isNode ? node->right : NULL; 
            }
        }
        printf("\n");
    }
}

请注意，您的高度功能返回树中的级别数。 “高度”的标准定义是从根到其最远的叶子的路径的长度，以边缘数表示（请参见 wikipedia ）。因此，只有一个节点的树具有高度0，一个空的树（ null ）的高度-1。这就是为什么以上代码从 height（）调用返回的值中减去1的原因。

Answer 2

对于清晰的BFS视图，我们通常在DSA问题中看到的视图，

请参阅参考，请参阅附加的图像

我们可以在Python中遵循此功能或方法

def bfs(self,bst):
        ans=[]
        if bst is None:
            return
        queue = [bst]

        while len(queue) > 0:
            
            cur_node = queue.pop(0)
            while cur_node=="N" and len(queue)>0:
                cur_node = queue.pop(0)
                ans.append("N")
            if cur_node!="N":
                ans.append(cur_node.val)
            else:
                break
            if cur_node.left is not None:
                queue.append(cur_node.left)
            else:
                queue.append("N")

            if cur_node.right is not None:
                queue.append(cur_node.right)
            else:
                queue.append("N")

        j=len(ans)-1
        
        while j>=0:
            if ans[j]=="N":
                ans.pop(-1)
                j-=1
            else:
                break

        return ans

Answer 3

您必须模拟不存在的树内容。
由于您已经有有关相对目标级别的信息，因为您的附加参数已经到位，这并不难。
只需在目标深度之前发明更多的树节点，始终将无效的指针作为发明的指针。

void current_height(tree *root, int level){
    if(root == NULL){
        if (level>1){
            current_height(NULL, level - 1);
            current_height(NULL, level - 1);
        }
        else {
            printf("%d, ", 0);
        }
        return;
    }
    if(level == 1){
        printf("%d, ", root->data);
    }
    else if(level > 1){
        current_height(root->left, level - 1);
        current_height(root->right, level - 1);
    }
}

在这里输出 https://wwwwwwwww.onlinegdb.com/online_c_compiler

5, 
0, 6, 
0, 0, 0, 7, 
0, 0, 0, 0, 0, 0, 0, 9,