压扁二叉树在Java中的数组 [英] Flattening a binary tree to an array in Java

问题描述

我发现<一href="http://commoninterview.com/Programming_Interview_Questions/write-a-function-which-will-flatten-a-binary-tree-into-an-array/"相对=nofollow>这code 压扁二叉树到阵列中的Java。我有很难理解它是如何工作的。

下面是code：

 私有静态诠释FlattenTreeIntoArray（节点树，INT []数组，int i）以
{
    如果（树== NULL）回报我;
    //拼合左子树
    I = FlattenTreeIntoArray（tree.Left，数组，I）;
    //从当前节点获取数据
    数组[我] = tree.Data;
    //拼合右子树
    I = FlattenTreeIntoArray（tree.Right，数组，I + 1）;
    返回我;
}
 

我的问题如下：

1. 这是辅助方法，如何才是真正的方法实际上是调用，或者是被作为参数传递（INT []数组和 > INT I ）？我们不知道的二进制树的大小

2. 如何进行工作的方法？当树是空，它返回我。这是什么意思？

3. 如何扁平化发生的呢？为什么 I + 1 传递给右键树，但我以左树？

如果你能证明这个二叉树，这将是容易遵循：

解决方案

这是一个简单的递归的例子，一旦你理解了这一点，所有的递归树算法应该开始变得有意义。我会尽量回答你的问题，尽我所能：

这是辅助方法，如何才是真正的方法实际上是调用，或什么是作为参数传递给INT I和int []数组 - 我们不知道二叉树 <大小/ P>

纵观code，而因为这是接受记者采访时类型的问题，我们将假设INT []数组足够大，以适应一切。

我似乎是数组来填充，以便第一次调用扁平化树将设置我 0。

此方法还返回一个整数，是已被填充迄今元件的数目。这意味着，最终返回将返回全长树（和填充阵列中的元素数）

  INT []数组=新INT [尺寸]
节点根= ...
INT bytesWritten = FlattenTreeIntoArray（根，阵列，0）;

// bytesWritten应该大小相等
断言（bytesWritten ==大小）;
 

如何做的方法功能：当树为空，则返回我。这是什么意思？

这假定一个节点的左边或右边字段指向空，如果没有孩子。由于我们使用我来保持我们在数组中，如果没有孩子，我们不更新 i的值。

如何扁平化会发生什么？为什么我+ 1被传递到正确的树，但我要离开了树。   压扁发生通过寻找最左边的节点，并把它放在我。然后寻找下一个最左边的节点，并把它放在 I + 1 等。

让我们通过你给树例如：

节点= 8 I = 0; 阵列= {}

得到根左节点，也就是3并递归调用此压平方法，它获取的3为1的左节点和递归再次调用扁平化方法中，当得到的1的左节点是空。返回我 = 0。 现在，我们都在扁平化方法节点1 数组[0] =节点1的值 =`数组[0] = 1。

现在称之为节点1的右场和扁平的递增我。节点1的权字段为空，所以我们返回我的当前值（即1）。

现在我们又回到了节点1的扁平化的方法，并finsished recurssing的左，右，并已达到该方法的末尾，以便我们返回的电流值i 这1。

现在我们又回到了节点3，我们刚刚完成调用扁平化方法，它返回的1，它的值左外野平化方法现在我们设置我要。

现在我们更新与节点3的值数组

 数组[1] = 3;
 

现在我们压扁节点3的右场（节点6）具有增加我这样 I = 2

等

希望帮助

I found this code for flattening a binary tree into array in Java. I am having hard time understanding how it works.

Here is the code:

private static int FlattenTreeIntoArray(Node tree, int[] array, int i)
{
    if (tree == null) return i;
    // Flatten left subtree
    i = FlattenTreeIntoArray(tree.Left, array, i);
    // Get data from the current node
    array[i] = tree.Data;
    // Flatten right subtree
    i = FlattenTreeIntoArray(tree.Right, array, i + 1);
    return i;
} 

My questions are as follows:

1. This is the helper method, how is the real method actually called, or what is passed as parameters (int[] array and int i)? We do not know the size of binary tree.

2. How does the method work? When the tree is null, it returns i. What does that mean?

3. How does the flattening happen? Why i+1 is passed to right tree but i to left tree?

If you could demonstrate with this binary tree, it will be easy to follow:

解决方案

This is a simple recursive example, once you understand this, all recursive tree algorithms should begin to make sense. I will try to answer your questions as best I can:

This is the helper method, how is the real method actually called, or what is passed as parameters to int i and int[] array -- we do not know the size of binary tree

Looking at the code, and since this is an interview type question, we will assume that the int[] array is big enough to fit everything.

i appears to be the current index of the array to populate so the first call to flatten the tree will be to set i to 0.

This method also returns an integer which is the number of elements that have been populated so far. This means that the final return will return the full length of the tree (and the number of elements populated in the array)

int[] array = new int[size];
Node root = ...
int bytesWritten = FlattenTreeIntoArray(root, array, 0);

//bytesWritten should equal size
assert(bytesWritten == size);

How does the method function: when the tree is null, it returns i. what does that mean?

This assumes that a Node's left or right fields point to null if there is no child. Since we are using i to maintain where we are in the array, if there is no child, we don't update the value of i.

how does the flattening happens? why i+1 is passed to right tree but i to left tree. The flattening happens by finding the left most node and putting it in i. Then finding the next most left node and putting it in i+1 etc.

Let's walk through the tree example you gave:

node= 8 i =0; array = {}

get left node of root, which is 3 and recursively call this flatten method, which gets the left node of 3 which is 1 and recursively calls the flatten method again, when gets the left node of 1 which is null. returns i = 0. Now we are in the flatten method for Node 1 array[0] = Node 1's value = `array[0] = 1.

Now call node 1's right field and flatten that incrementing i. Node 1's right field is null so we return the current value of i (which is 1).

Now we are back in node 1's flatten method and have finsished recurssing the left and right and have reached the end of the method so we return the current value of i which is 1.

Now we are back in the flatten method for node 3. We have just finished calling the flatten method for the left field which returned a value of 1 which is now what we set i to.

Now we update the array with node 3's value

array[1] = 3;

Now we flatten Node 3's right field (Node 6) with the incremented i so i=2

etc

Hope that helps

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