用数组表示的二叉树 [英] Binary Tree represented using array

问题描述

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

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.

这篇关于用数组表示的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！