建立从preorder BST [英] Build BST from Preorder
问题描述
像很多新手,我的头从递归炸毁。我抬头一看很多答案/解释对SO。但我仍然不清楚的概念。 (这不是功课,我想重新学习什么,我没有学问和递归从来就不是一个串点)
由于一个preorder遍历,构造一个二叉树。递归,它必须是看似简单的:)但我就是不明白。
我的看的是,ARR的顺序必须是在节点顺序插入。我是什么错误:
- 如果该节点已经有一个左/右?这是如何工作的?
-
如何递归插入结点,在说下preorder?
12,10,6,13
15根,5,3和左
如何获得6正确插入10的左子?
12
10 13
6 *
下面是骨骼code:
的main()
{
INT [] ARR = {};
//使第一节点的根节点。
节点n =新节点(改编[0]);
buildbst(N,编曲,0)
}
buildbst(节点根,INT []改编,int i)以
{
如果(我== arr.length)回报;
如果(ARR [1] - ; root.data)
root.left =新节点(ARR [I]);
其他
root.right =新节点(ARR [I]);
buildbst(root.left,编曲,我++);
buildbst(root.right,编曲,我++);
}
编辑:
我才意识到,如果我通过在递归调用 buildbst(root.left,编曲+我,我++)
这是正确的方式?还是我处理这个都错了 - 一个大杂烩动态规划和递归和分而治之...
-
这已经不能有一个左/右孩子。你怎么称呼它为根,它有没有孩子下手。然后,你把它的左孩子和孩子创造酌情并调用该函数的那些孩子等等。你从来没有访问左子再次一旦你权利,你不能从一个呼吁其子功能的节点(因为没有了树没有任何联系,除了递归栈)。
李> -
这是给定的时候会发生什么
12,10,6,13
:- 创建了根
12
- 呼叫
buildbst(节点(12),编曲,1)
- 创建
节点(12)。左=节点(10)
- 呼叫
buildbst(节点(10),编曲,2)
- 创建
节点(10)。左=节点(6)
- 呼叫
buildbst(节点(6),编曲,3)
-
13> 12
,必须12
的右孩子,所以什么也不做
-
-
13> 12
,必须12
的右孩子,所以什么也不做
- 创建
- 创建
节点(12).right =节点(13)
- 呼叫
buildbst(节点(13),编曲,3)
- 哦,看,没有更多的元素,我们就大功告成了。
- 创建
- 创建了根
以上是不是必须用自己的code发生什么有2个原因:
- 您$ C $ C只会造成左或右的孩子,(因为
的if-else
)不能同时) - 您$ C $ C没有'12'的
必须是正确的孩子
检查,这是一个有点复杂
下面code应该覆盖它。
节点buildbst(INT [] ARR)
{
节点n =新节点(改编[0]);
// 9999999999,就是要与GT;比数据的最大元素
buildbst(N,编曲,1,9999999999);
返回节点;
}
INT buildbst(节点电流,INT []改编,诠释我,诠释biggestSoFar)
{
如果(我== arr.length)回报我;
//递归左
如果(ARR [1] - ; current.data)
{
current.left =新节点(ARR [我++]);
I = buildbst(current.left,编曲,我,current.data);
}
//递归权
如果(ⅰ&其中; arr.length&安培;&安培;常用3 [1] - ; biggestSoFar)
{
current.right =新节点(ARR [我++]);
I = buildbst(current.right,编曲,我,biggestSoFar);
}
返回我;
}
说明:
biggestSoFar
的目的是prevent:
15 15
/ / \
5对(正确)5月20日
/ \ /
1 20 1
当从 15
例如递归离开,我们需要尽快停止处理单元,因为我们得到一个元素> 15
,当我们将发生 20
。因此,我们通过 current.data code>并停止处理元素,如果我们获得更大的价值。
当从 5
例如递归的权利,我们需要尽快停止处理单元,因为我们得到一个元素> 15
,当我们将发生 20
。因此,我们通过 biggestSoFar
并停止处理元素,如果我们获得更大的价值。
Like many newbies, my head blows up from recursion. I looked up a lot of answers/explanations on SO. but I am still unclear on the concept. (This is not homework, I am trying to relearn what I unlearned and recursion was never a string point)
Given a preorder traversal, construct a binary tree. With recursion, it has to be deceptively simple :) but I just can't get it.
I see that the order of the arr has to be in the order nodes are inserted. What bugs me is:
- What if the node already has a left/right? How does this work?
How can the recursion insert nodes, in say the following preorder?
12, 10, 6, 13
15 is root, 5, 3 and left
How does 6 get inserted correctly as 10's left child?
12
10 13
6*
Here is the skeleton code:
main()
{
int[] arr = {};
//make the first node a root node.
node n = new node(arr[0]);
buildbst(n, arr, 0)
}
buildbst(node root, int[] arr, int i)
{
if (i == arr.length) return;
if (arr[i] < root.data)
root.left = new node (arr[i]);
else
root.right = new node(arr[i]);
buildbst(root.left, arr, i++);
buildbst(root.right, arr, i++);
}
EDIT:
I just realised, if I pass in the recursive call buildbst(root.left, arr+i, i++)
is that the right way? Or am I approaching this all wrong - a mish-mash of dynamic programming and recursion and divide and conquer...
It can't already have a left / right child. You call it for the root, which has no children to start. Then you call it for the left child and create children where appropriate and call the function for those children and so on. You never visit the left child again once you go right and you can't get to a node from a function called on its child (since there is no connection up the tree, except the recursion stack).
This is what should happen when given
12, 10, 6, 13
:- Creates the root
12
- Calls
buildbst(node(12), arr, 1)
- Create
node(12).left = node(10)
- Calls
buildbst(node(10), arr, 2)
- Create
node(10).left = node(6)
- Calls
buildbst(node(6), arr, 3)
13 > 12
, must be right child of12
, so do nothing
13 > 12
, must be right child of12
, so do nothing
- Create
- Create
node(12).right = node(13)
- Calls
buildbst(node(13), arr, 3)
- Oh look, no more elements, we're done.
- Create
- Creates the root
The above is not what will happen with your code for 2 reasons:
- Your code will only create either a left or a right child, not both (because of the
if-else
)) - Your code doesn't have the
must be right child of '12'
check, which is a little complex
The below code should cover it.
node buildbst(int[] arr)
{
node n = new node(arr[0]);
// 9999999999 is meant to be > than the biggest element in your data
buildbst(n, arr, 1, 9999999999);
return node;
}
int buildbst(node current, int[] arr, int i, int biggestSoFar)
{
if (i == arr.length) return i;
// recurse left
if (arr[i] < current.data)
{
current.left = new node(arr[i++]);
i = buildbst(current.left, arr, i, current.data);
}
// recurse right
if (i < arr.length && arr[i] < biggestSoFar)
{
current.right = new node(arr[i++]);
i = buildbst(current.right, arr, i, biggestSoFar);
}
return i;
}
Explanation:
The purpose of biggestSoFar
is to prevent:
15 15
/ /\
5 versus (the correct) 5 20
/ \ /
1 20 1
When recursing left from 15
for example, we need to stop processing elements as soon as we get an element > 15
, which will happen when we get 20
. Thus we pass current.data
and stop processing elements if we get a bigger value.
When recursing right from 5
for example, we need to stop processing elements as soon as we get an element > 15
, which will happen when we get 20
. Thus we pass biggestSoFar
and stop processing elements if we get a bigger value.
这篇关于建立从preorder BST的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!