s******t
发帖数: 2374 | 1 我想了好久还是不知道怎么用递归做。。。
笨死了。
上来求教一下，不想浪费时间了。
如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
static int = k;
void search(Node cur){
if(cur == null || index < 0) return;
search(cur.left);
if(--index == 0) {System.out.println(cur.value); return;}
search(cur.right);
}
很土。。。。感觉是totally wrong.... |
s******t
发帖数: 2374 | 2 难道是这么写？
int search(Node cur, int index){
if(cur == null) return index;
if(index < 0) return -1;
index = search(cur.left, index);
if(--index == 0) {System.out.println(cur.value); return -1;}
index = search(cur.right, index);
return index;
} |
s******t
发帖数: 2374 | 3 想了想，其实可以用stack来做，
把左子树压入stack，直到没有左子树为止，然后弹出的时候开始计数，
如果有右子树右子树压stack。然后重复。
总之就是每次拼命往左压站，然后出栈的时候计数，同时压右子树，同时重复上述对右
子树的左子树操作。
不知道思路对不对。睡觉了。。。 |
P*******e
发帖数: 1353 | 4 用quicksort的那个partition函数
是不被favorable的吧。。。
【在 s******t 的大作中提到】
: 我想了好久还是不知道怎么用递归做。。。
: 笨死了。
: 上来求教一下，不想浪费时间了。
: 如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
: static int = k;
: void search(Node cur){
: if(cur == null || index < 0) return;
: search(cur.left);
: if(--index == 0) {System.out.println(cur.value); return;}
: search(cur.right);
|
j**l
发帖数: 2911 | 5 假设要找第i大的数，也就是升序排序后从右向左数第i个数
首先编写一个函数Count(tree* root)，用来统计一棵二叉树有多少个节点。
调用Count函数，求出BST的右子树的大小RSize
如果i = Rsize + 1，则根节点即为所求
如果i < RSize + 1, 则递归继续在右子树中找i
如果i > Risze + 1, 则递归在左子树中找 i - (Rsize + 1) |
w******1
发帖数: 520 | 6 建立一个有序堆，最大的值在最上。
然后， LOG N 就可以找到这个最 I大的。 |
r****o
发帖数: 1950 | 7 问一下，Count函数也可以用递归实现吧，感觉这样做了重复工作啊。
能不能把两个递归写一起?
【在 j**l 的大作中提到】
: 假设要找第i大的数，也就是升序排序后从右向左数第i个数
: 首先编写一个函数Count(tree* root)，用来统计一棵二叉树有多少个节点。
: 调用Count函数，求出BST的右子树的大小RSize
: 如果i = Rsize + 1，则根节点即为所求
: 如果i < RSize + 1, 则递归继续在右子树中找i
: 如果i > Risze + 1, 则递归在左子树中找 i - (Rsize + 1)
|
B*****t
发帖数: 335 | 8 use DP
不被favorable的吧。。。
【在 s******t 的大作中提到】
: 我想了好久还是不知道怎么用递归做。。。
: 笨死了。
: 上来求教一下，不想浪费时间了。
: 如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
: static int = k;
: void search(Node cur){
: if(cur == null || index < 0) return;
: search(cur.left);
: if(--index == 0) {System.out.println(cur.value); return;}
: search(cur.right);
|
c****2
发帖数: 31 | 9 Binary Search Tree is already sorted: all the nodes on the left branch is
less than the root node, all the nodes on the right branch is greater than
the root node.
Use recursion to search the kth smallest and use numOfNodes records down the
nodes that have been traversed. When you search the left branches. the
numOfNodes will records down the number of nodes in the left branch. If you
can not find in the left branch, then search the (k-numOfNodes) smallest
node in the right branch.
BST_Search(No
【在 s******t 的大作中提到】
: 我想了好久还是不知道怎么用递归做。。。
: 笨死了。
: 上来求教一下，不想浪费时间了。
: 如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
: static int = k;
: void search(Node cur){
: if(cur == null || index < 0) return;
: search(cur.left);
: if(--index == 0) {System.out.println(cur.value); return;}
: search(cur.right);
|
s********f
发帖数: 510 | 10 就是preorder反过来,第I大就是第I个,
你想想找第I小就好啦.
是不被favorable的吧。。。
【在 s******t 的大作中提到】
: 我想了好久还是不知道怎么用递归做。。。
: 笨死了。
: 上来求教一下，不想浪费时间了。
: 如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
: static int = k;
: void search(Node cur){
: if(cur == null || index < 0) return;
: search(cur.left);
: if(--index == 0) {System.out.println(cur.value); return;}
: search(cur.right);
|
|
|
s******t
发帖数: 2374 | 11 你看我写的那个left和right互换之后对不对呀。
【在 s********f 的大作中提到】
: 就是preorder反过来,第I大就是第I个,
: 你想想找第I小就好啦.
:
: 是不被favorable的吧。。。
|
j**l
发帖数: 2911 | 12 看不懂代码。有跑过实际的例子验证过么？
函数原型BST_Search(Node *root, int k, int *numOfNodes)
函数调用BST_Search(root->right, (k-numOfNodes), 0);
没见过这样写的
每次k-1是什么用意？为什么要到k == 0 才累加numOfNodes
此外不如用C++的引用。
the
you
【在 c****2 的大作中提到】
: Binary Search Tree is already sorted: all the nodes on the left branch is
: less than the root node, all the nodes on the right branch is greater than
: the root node.
: Use recursion to search the kth smallest and use numOfNodes records down the
: nodes that have been traversed. When you search the left branches. the
: numOfNodes will records down the number of nodes in the left branch. If you
: can not find in the left branch, then search the (k-numOfNodes) smallest
: node in the right branch.
: BST_Search(No
|
j**l
发帖数: 2911 | 13 6
/ \
5 7
/ \
4 8
/ \
3 9
/ \
2 10
/ \
1 11
对上面这棵BST, 找第4小的数, k = 4，应该返回4,
但是好像这段代码要返回2？
the
you
【在 c****2 的大作中提到】
: Binary Search Tree is already sorted: all the nodes on the left branch is
: less than the root node, all the nodes on the right branch is greater than
: the root node.
: Use recursion to search the kth smallest and use numOfNodes records down the
: nodes that have been traversed. When you search the left branches. the
: numOfNodes will records down the number of nodes in the left branch. If you
: can not find in the left branch, then search the (k-numOfNodes) smallest
: node in the right branch.
: BST_Search(No
|
s******t
发帖数: 2374 | 14 我觉得我写的那个应该可以work吧。第二个
【在 j**l 的大作中提到】
: 6
: / \
: 5 7
: / \
: 4 8
: / \
: 3 9
: / \
: 2 10
: / \
|
l******c
发帖数: 2555 | 15 find 5th max element in BST
void max5th(Node * p)
{
static num = 0;
if(p == 0)
return;
max5th(p->right);
num++;
if(num == 5)
{
printf("%d", p->i);
return;
}
max5th(p->left);
}; |
g********d
发帖数: 43 | 16
// should add following piece of code to improve performance
if (num >= 5) return; //we have found the num, no need to go to left
subtree
【在 l******c 的大作中提到】
: find 5th max element in BST
: void max5th(Node * p)
: {
: static num = 0;
: if(p == 0)
: return;
: max5th(p->right);
: num++;
: if(num == 5)
: {
|
m******9
发帖数: 968 | 17 直接把inorder改一改就可以了:
void find_ith(Node* root, int i, int& count)
{
if(root!=NULL)
{
find_ith(root->left, i, count);
count++;
if(count==i){
cout<key<
return;
}
find_ith(root->right,i,count);
}
}
int count = 0;
find_ith(root, 5, count) print 5-th min |
r****o
发帖数: 1950 | 18 这个是第k小的数吧。
如果找第k大的数是不是把right, left换一下就可?
【在 m******9 的大作中提到】
: 直接把inorder改一改就可以了:
: void find_ith(Node* root, int i, int& count)
: {
: if(root!=NULL)
: {
: find_ith(root->left, i, count);
: count++;
: if(count==i){
: cout<key<: return;
|
m******9
发帖数: 968 | 19 是, 我题目看错了.
把right left换一下就是ith max了
【在 r****o 的大作中提到】
: 这个是第k小的数吧。
: 如果找第k大的数是不是把right, left换一下就可?
|
s******t
发帖数: 2374 | 20 你的代码在找到了第n个之后不会停止吧。
【在 m******9 的大作中提到】
: 是, 我题目看错了.
: 把right left换一下就是ith max了
|
|
|
r****o
发帖数: 1950 | 21 是不是在函数里面刚开始的时候加个判断语句count>=n，让它停止就可以了？
【在 s******t 的大作中提到】
: 你的代码在找到了第n个之后不会停止吧。
|
d**e
发帖数: 6098 | 22 第n个是指最后一个？
他上面的 root != NULL 就可以判断返回了吧
【在 r****o 的大作中提到】
: 是不是在函数里面刚开始的时候加个判断语句count>=n，让它停止就可以了？
|
f****4
发帖数: 1359 | 23 Node* NextInorderNode(Node* current);
// 返回current在中序遍历的前一个节点
// (这个参照返回current在中序遍历的后一个节点的代码就可以写出来了)
// 1. current == root 2. cureent has left child
// 3. current is left child 4. current is right child
Node* biggestNode = root;
while(biggestNode->rptr)
biggestNode = biggestNode->rptr;
for(int i = 0; i < k; ++i)
biggestNode = NextInorderNode(NextInorderNode);
return NextInorderNode; |
g*****u
发帖数: 298 | 24 你这是什么啊，看不懂
而且，你光考虑最右最远节点，回溯怎么办
【在 f****4 的大作中提到】
: Node* NextInorderNode(Node* current);
: // 返回current在中序遍历的前一个节点
: // (这个参照返回current在中序遍历的后一个节点的代码就可以写出来了)
: // 1. current == root 2. cureent has left child
: // 3. current is left child 4. current is right child
: Node* biggestNode = root;
: while(biggestNode->rptr)
: biggestNode = biggestNode->rptr;
: for(int i = 0; i < k; ++i)
: biggestNode = NextInorderNode(NextInorderNode);
|
y****w
发帖数: 3747 | 25 re, right-root-left patten
【在 s********f 的大作中提到】
: 就是preorder反过来,第I大就是第I个,
: 你想想找第I小就好啦.
:
: 是不被favorable的吧。。。
|
