21

これは面接の質問です。BSTで2番目の最大値を見つけます。

max要素は、BSTの右端のリーフです。2番目の最大値は、その親またはその左の子のいずれかです。したがって、解決策は、BSTをトラバースして右端の葉を見つけ、その親と左の子を確認することです。

それは意味がありますか？

4

15 に答える 15

31

いいえ、それは間違っています。このBSTを検討してください。

        137
       /
      42
       \
        99

ここで、最大値から2番目の値は、最大値の左の子の右端の子です。最大値の親、または最大値の左の子の右端のサブ子をチェックするように、アルゴリズムを更新する必要があります。

また、maxは必ずしも右端の葉ノードではなく、ツリーの右スパインの下部にあるノードであることに注意してください。上記では、137は葉ではありません。

お役に立てれば！

于 2012-07-11T04:16:18.050 に答える
15

最初に適切なサブツリーを探索する修正された順序トラバーサルを実行することにより、BSTのノードを逆の順序でリストできることを思い出してください。これにより、単純なアルゴリズムが実現します。

Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
    return findRightmostNode(rightmost.left)
else{
    return rightmost.parent
}

ツリーに要素が1つしかない場合は、nullを返します。

于 2012-07-11T04:24:48.140 に答える
5

アルゴリズムは次のようになります

1. find the largest number in the tree. 

  private static int findLargestValueInTree(Node root) {
    while (root.right != null) {
     root = root.right;
    }
    return root.data;
  }

2. Find the largest number in the tree that is smaller than the number we found in step 1

 public static int findSecondLargest(Node root, int largest, int current) {
   while (root != null) {
    if (root.data < largest) {
      current = root.data;
      root = root.right;
    } else {
      root = root.left;
   }
   }
  return current;
 }

「現在」は、ステップ1で見つかった数よりも小さい現在の最大数を追跡します

于 2012-08-31T23:55:47.853 に答える
2

シンプルな JavaScript の実装。 

function Node (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right; 
}

function second (node, prev, wentLeft) {
    if (node.right) {
        return second(node.right, node, wentLeft);
    } else if (node.left) {
        return second(node.left, node, true);
    } else {
        if (wentLeft) return node.value;
        return prev.value;
    }
}
second(root);
于 2017-01-02T03:16:26.670 に答える
1

これについて考える非常に直感的な方法は、次の 2 つのケースを検討することです。2 番目に大きいノードを S、最大のノードを L とします。

i) S は L よりも「前に」BST に挿入されます。 ii) S は L よりも「後で」BST に挿入されます。

最初のケースでは、L が S の右側の子であることは明らかです。これは、L 以外のノードは S より小さいため、S の右側には配置されないためです。したがって、L が配置されている場合、 Sの右の子になります。

2 番目のケースでは、S が挿入されるまでに、L が BST の右端のノードになります。明らかに、L は最大であるため、適切な子を持ちません。ただし、L は独自の左サブツリーを持つことができます。S が挿入されると、S は L に出会うまで「右のパス」をたどり、次に左に曲がって L の左のサブツリーに移動します。ここで、L の左のサブツリーのすべてのノードが S より小さいことがわかっているため、Sサブツリーの右端のノードになります。

于 2014-09-21T05:09:17.247 に答える
1 
int getSecondLargest(Node root){
    if(root==null)
        return 0;
    Node curr=root;
    Node prev=root;
    //Go to the largest node
    while(curr.right != null){
        prev = curr;
        curr= curr.right;
    }
    //If largest Node has left child, Then largest element of tree with its root as largest.left will be the second largest number.
    if(curr.left == null)
        return prev.data;
    else
        return findLargest(curr.left);
}

int findLargest(Node root){
    // No need toi check for null condition as in getSecondLargest method, its already done.
    Node curr=root;
    //To find largest just keep on going to right child till leaf is encountered.
    while(curr.right != null){
        curr = curr.right;
    }
    return curr.data;
}
于 2016-06-03T09:02:29.863 に答える
1

最大の要素から最小の要素までツリーをたどり、要求された位置に到達したときに値を返すことでそれを行います。2番目に大きい値に対して同様のタスクを実装しました。

void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
    if(r->right) {
        this->findSecondLargestValueUtil(r->right, c, v);
    }

    c++;

    if(c==2) {
        v = r->value;
        return;
    }

    if(r->left) {
        this->findSecondLargestValueUtil(r->left, c, v);
    }
}


int BTree::findSecondLargestValue()
{
    int c = 0;
    int v = -1;

    this->findSecondLargestValueUtil(this->root, c, v);

    return v;
}
于 2016-10-17T22:53:44.293 に答える
1

1 つのトラバーサル バリアント:

   public Tree GetSecondMax(Tree root)
    {
        Tree parentOfMax = null;

        var maxNode = GetMaxNode(root, ref parentOfMax);

        if (maxNode == root || maxnode.left != null)
        {
            // if maximum node is root or have left subtree, then return maximum from left subtree
            return GetMaxNode(maxnode.left, ref parentOfMax);
        }

        // if maximum node is not root, then return parent of maximum node
        return parentOfMax;
    }

    private Tree GetMaxNode(Tree root, ref Tree previousNode)
    {
        if (root == null || root.right == null)
        {
            // The most right element have reached
            return root;
        }

        // we was there
        previousNode = root;

        return GetMaxNode(root.right, ref previousNode);
    }
于 2013-02-09T13:00:45.713 に答える