遍历数组形式的不平衡二叉树

Question

不平衡（或非堆）二叉树可以使用数组来表示，如下所示：

array = [1, 2, null, 3, 4, 5, 6, null, 7, 8, null]

         1
        /  \
       2    null
      /  \
    3      4
   / \   /  \
  5   6 null 7
 / \
8  null

如何使用给定的数组遍历树？更具体地说，如何计算父母的左​​右儿童指数？

在平衡树（例如堆树）中，我们可以使用其父级索引轻松计算两个子级索引，反之亦然，如下所示。

leftChildIdx  = 2 * parentIdx + 1
rightChildIdx = 2 * parentIdx + 2

是否有使用数组遍历此不平衡或看似随机的二叉树的简便方法？

Answer 1

将二叉树表示为数组不会从根本上改变遍历。无论平衡如何，或者我们是否考虑使用堆还是BST，这都是适用的，这是强制执行某些排序属性的二进制树的特定情况。

该算法仍是递归定义的，但不是使用节点，而是通过调用堆栈传递索引变量。如您所述，子级分别为i*2+1和i*2+2，但在其他方面，其逻辑与节点中的指针相同。

话虽如此，您提供的树图和数组与您为计算子级而给出的公式不匹配。所示的数组是压缩的表示形式，可将子树向前移动以填充null s留下的间隙。使用您的子索引定义，图中的树将是

tree = [1, 2, null, 3, 4, null, null, 5, 6, null, 7, null, null, null, null, 8]

Extra null必须用作树的空白右侧的占位符。没有这些，节点5和6的原始位置会将它们标记为索引2处null值的子级，这是无效的。

这里是使用提供的子公式在解压缩的树上进行遍历的示例：

const traverseInOrder = (tree, i=0) => {
  if (i < tree.length && tree[i] !== null) {
    traverseInOrder(tree, i * 2 + 1);
    console.log(tree[i]);
    traverseInOrder(tree, i * 2 + 2);
  }
};

/*      1
       /  
      2  
     / \
    3   4
   / \   \
  5   6   7
 / 
8           */
const tree = [1, 2, null, 3, 4, null, null, 5, 6, null, 7, null, null, null, null, 8];
traverseInOrder(tree);