给定一个修改的二叉搜索树，找到第k个最小元素

假设在给定的二叉树中如果每个节点包含子元素数，那么在树中找到第k个最小元素的最优方法是什么？给定一个修改的二叉搜索树，找到第k个最小元素

请注意，这不是普通的BST。每个节点都包含它下面的子元素的编号。

2011-09-06 Ajeet Ganga

作业，偶然？ – Skizz

绝对不是作业。 @Skizz，我想告诉你我的办公室徽章一次。 :) –

find_element(root, k) 

    if(root.left.nchildren + 1 == k - 1) 
     return root; 

    if(root.left.nchildren + 1 >= k) 
     return find_element(root.left, k)    

    else 
     return find_element(root.right, k - (root.left.children + 1))

来源

2011-09-06 13:04:10 Simone

@ajeet，Simone：'每个节点包含多个子元素'。这包括正确的子树。如果您正在寻找具有n个元素的完整二叉树中的第n个元素，则该算法将错误地返回根。 – amit

@amit，请注意Simone正在计算left.nchildren而不是root.nchildren。 Simone从0开始计算K值。考虑到他的算法会返回正确的结果。 –

@ajeet：Simone在发表评论后编辑了答案，并且通过计算左子尺寸而不是根尺寸来解决此问题。我的评论不再相关 – amit

这是我得到：

find (root, k) 
{ 
leftChildCount = root->left->n 
rightChildCount = root->right->n 

if (leftChildCount+1 == k) 
    Print root node 
else if (k< leftChildCount) 
    Find(root->left,k) 
else 
    Find(root->right,k-leftChildCount) 
}

来源

2011-09-06 13:05:07

遍历BST在InOrder遍历方式和存储元件阵列。你的数组是一个有序数组。

来源

2013-05-22 19:15:15 Cannon

给定一个修改的二叉搜索树，找到第k个最小元素

回答

相关问题