用数组表示的二叉树

本文介绍了用数组表示的二叉树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

请考虑以下数组，该数组据称已表示一棵二叉树:

Consider the following array, which is claimed to have represented a binary tree:

[1、2、5、6，-1、8、11]

[1, 2, 5, 6, -1, 8, 11]

鉴于值为-1的索引表示根元素，我有以下问题:

Given that the index with value -1 indicates the root element, I've below questions:

a)这实际上是怎么表示的?

a) How is this actually represented?

我们应该遵循以下公式(来源此链接)找出这棵树? 通过三个简单的公式，您可以从父级的索引转到其子级的索引，反之亦然:

Should we follow below formulae (source from this link) to figure out the tree? Three simple formulae allow you to go from the index of the parent to the index of its children and vice versa:

* if index(parent) = N, index(left child) = 2*N+1 * if index(parent) = N, index(right child) = 2*N+2 * if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

如果使用上述公式，则index(root)= 3，index(left child)= 7，这不存在.

If we use above formulae, then index(root) = 3, index(left child) = 7, which doesn't exist.

b)了解它是否是完整的二叉树是否重要?

b) Is it important to know whether it's a complete binary tree or not?

推荐答案

给出一个数组，您可以想到多种方式该数组如何表示二叉树.因此，没有办法知道，您必须转到该数组的源(不管是什么).

Given an array, you could think of any number of ways how could that array represent a binary tree. So there is no way to know, you have to go to the source of that array (whatever that is).

其中一种方法是按照您的链接通常表示二进制堆的方式.如果这是使用的表示形式，则-1将不是根元素.而且位置3的节点将没有子节点，即它将是一片叶子.

One of those ways is the way binary heap is usually represented, as per your link. If this was the representation used, -1 would not be the root element. And the node at position 3 would have no children, i.e. it would be a leaf.

是的，知道它是否应该是一棵完整的树可能很重要.

And, yeah, it's probably important to know whether it's supposed to be a complete tree or not.

通常，您不应该试图弄清楚某些数据是什么意思.您应该获得使用该数据的文档或源代码.如果您没有此功能，而您确实需要对其进行反向工程，则您最有可能需要了解有关数据的更多信息.观察使用它的代码的行为应该会对您有所帮助.或反编译代码.

In general, you shouldn't try to figure out what does some data mean like this. You should be given documentation or the source code that uses the data. If you don't have that and you really need to reverse-engineer it, you most likely need to know more about the data. Observing the behavior of the code that uses it should help you. Or decompiling the code.