将二进制搜索树转换为数组BFT-Java 学习之路

我希望将二叉树表示为一个数组，使得数组处于广度第一顺序，其中空值在数组中表示 . 我想 not 想要使用数组列表，但很乐意使用链表结构 . 我发现数组最大大小的大小为2 ^ n - 1，其中n是以下情况下树的高度：

5
          /   \
        4       6
      /  \     / \
     3    x   x   7
    /\   /\  /\   /\
   x  x x x x x  x  8


[5, 4, 6, 3, null, null, 7, null, null, null, null, null, null, null, 8]

并且数组的最小大小（除了空树或没有子项的根[相应大小为0和3]）将是（2 ^ n - 1） - 6，其中6可以计算为空的数量在这种情况下，上一级乘以2：

5
          /   \
        4       6
      /  \     / \
     3    x   x   x
    /\   
   2  x 

[5, 4, 6, 3, null, null, null, 2, null]

这些树可以表示为 root 在索引0处的堆，而当前节点在索引i处的左子节点是2i 1，右边的子节点是2i 2吗？

是否有一个递归方法来检查左右节点？

任何人都可以帮助/提供伪代码只使用树和数组来帮助实现这个吗？

2 回答

0

您可以尝试创建一个Node类，并拥有实例变量，如父，左子，右子，值和位置 .

这里的位置与值不同，因为您希望在结构中显示空值，如图中所示 .

Position表示节点在树中的位置，value表示实际节点值 .

回复于 2024-04-30T02:13:03+08:00
0
一些伪代码：
```
putInArray(node, index)
  array[index] = node
  if(node)
    putInArray(node->left, 2*index+1)
    putInArray(node->right, 2*index+2)
```
您可以使用putInArray（root，0）调用它 . 如果node为null，则该方法将在数组内部以相同的方式设置它，但不会进一步递归 .
回复于 2024-04-30T02:13:03+08:00

将二进制搜索树转换为数组BFT

2 回答

相关问题