3

これはインタビューの質問です。

二分探索木が与えられ、2 つのノードの値が交換されています。問題は、ツリーの 1 回のトラバーサルでノードとスワップされた値の両方を見つける方法です。

以下のコードを使用してこれを解決しようとしましたが、再帰を停止できないため、セグメンテーション違反が発生しています。再帰を止める方法を教えてください。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdlib.h>

 /* A binary tree node has data, pointer to left child
 and a pointer to right child */
 struct node
{
 int data;
 struct node* left;
 struct node* right;
};
/* Helper function that allocates a new node with the
 given data and NULL left and right pointers. */
 struct node* newNode(int data)
 {
  struct node* node = (struct node*)
                    malloc(sizeof(struct node));
 node->data = data;
 node->left = NULL;
 node->right = NULL;
 return(node);
 }
void modifiedInorder(struct node *root, struct node **nextNode)
 {
    static int nextdata=INT_MAX;
    if(root)
    {       
        modifiedInorder(root->right, nextNode);
        if(root->data > nextdata)
        return;
        *nextNode = root;
        nextdata = root->data;

        modifiedInorder(root->left, nextNode);          
    }
}

void inorder(struct node *root, struct node *copyroot, struct node **prevNode)
{
    static int prevdata = INT_MIN; 
    if(root)
    {
        inorder(root->left, copyroot, prevNode);
        if(root->data < prevdata)
        {
            struct node *nextNode = NULL;
            modifiedInorder(copyroot, &nextNode);

            int data = nextNode->data;
            nextNode->data = (*prevNode)->data;
            (*prevNode)->data = data;
            return;
        }
        *prevNode = root;
        prevdata = root->data;
        inorder(root->right, copyroot, prevNode);           
    }
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
    if (node == NULL)
        return;

    /* first recur on left child */
    printInorder(node->left);

    /* then print the data of node */
    printf("%d ", node->data);

    /* now recur on right child */
    printInorder(node->right);
}


int main()
{
    /*   4
        /  \
       2    3
      / \
     1   5
    */

    struct node *root = newNode(1);  // newNode will return a node.
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
    printf("Inorder Traversal of the original tree\n ");
    printInorder(root);

    struct node *prevNode=NULL;
    inorder(root, root, &prevNode);

    printf("\nInorder Traversal of the fixed tree \n");
    printInorder(root);

    return 0;

}
4

5 に答える 5

7

inorder traversal を使用してツリーまで歩きます。これを使用すると、すべての要素が並べ替えられ、周囲の要素よりも大きい要素が 1 つ交換されます。

たとえば、以下の二分木を考えてみましょう

          _  20  _
         /         \
      15             30
     /   \         /   \ 
   10    17      25     33
  / |   /  \    /  \    |  \
9  16  12  18  22  26  31  34

まず、これを線形化して配列にすると、

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34

16 は周囲の要素よりも大きく、12 はそれらよりも小さいことがわかります。これにより、12 と 16 が入れ替わったことがすぐにわかります。

于 2012-09-04T11:12:34.603 に答える
2

次の関数は、境界を狭めながら左右のサブツリーを再帰的に反復することにより、ツリーが BST であるかどうかを検証します。

上記のタスクを達成するために変更できると思います

  1. false を返す代わりに、ツリーが BST であることに失敗したノードへの一時ポインタ、つまりポインタを返します。
  2. スワップされた値の両方を与えるインスタンスが 2 つあります。

編集: true を返す再帰関数と、スワップされたノードへのポインターを区別する必要があります。

これは、問題の定義で言及されているような値が 2 つしかないことを前提としています。

bool validate_bst(tnode *temp, int min, int max)
{
        if(temp == NULL)
                return true;

        if(temp->data > min && temp->data < max)
        {
                if( validate_bst(temp->left, min, temp->data) && 
                    validate_bst(temp->right, temp->data, max) )
                        return true;
        }

        return false;
}

メインは上記のAPIを次のように呼び出します

   validate_bst(root, -1, 100); // Basically we pass -1 as min and 100 as max in
                                     // this instance
于 2012-09-04T12:05:24.157 に答える
0

Geeksforgeeks.com でこの質問に対する別の解決策を見つけました..............みんな、このスレッドを調べて、以下のコードの詳細な説明を得ることができますhttp://www.geeksforgeeks.org/archives/ 23616

// Two nodes in the BST's swapped, correct the BST.
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node *left, *right;
};

// A utility function to swap two integers
void swap( int* a, int* b )
{
int t = *a;
*a = *b;
*b = t;
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

// This function does inorder traversal to find out the two swapped nodes.
// It sets three pointers, first, middle and last.  If the swapped nodes are
// adjacent to each other, then first and middle contain the resultant nodes
// Else, first and last contain the resultant nodes
void correctBSTUtil( struct node* root, struct node** first,
                 struct node** middle, struct node** last,
                 struct node** prev )
{
if( root )
{
    // Recur for the left subtree
    correctBSTUtil( root->left, first, middle, last, prev );

    // If this node is smaller than the previous node, it's violating
    // the BST rule.
    if (*prev && root->data < (*prev)->data)
    {
        // If this is first violation, mark these two nodes as
        // 'first' and 'middle'
        if ( !*first )
        {
            *first = *prev;
            *middle = root;
        }

        // If this is second violation, mark this node as last
        else
            *last = root;
    }

    // Mark this node as previous
    *prev = root;

    // Recur for the right subtree
    correctBSTUtil( root->right, first, middle, last, prev );
}
}

// A function to fix a given BST where two nodes are swapped.  This
// function uses correctBSTUtil() to find out two nodes and swaps the
// nodes to fix the BST
void correctBST( struct node* root )
{
// Initialize pointers needed for correctBSTUtil()
struct node *first, *middle, *last, *prev;
first = middle = last = prev = NULL;

// Set the poiters to find out two nodes
correctBSTUtil( root, &first, &middle, &last, &prev );

// Fix (or correct) the tree
if( first && last )
    swap( &(first->data), &(last->data) );
else if( first && middle ) // Adjacent nodes swapped
    swap( &(first->data), &(middle->data) );

// else nodes have not been swapped, passed tree is really BST.
}

/* A utility function to print Inoder traversal */
void printInorder(struct node* node)
{
if (node == NULL)
    return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
/*   6
    /  \
   10    2
  / \   / \
 1   3 7  12
 10 and 2 are swapped
*/

struct node *root = newNode(6);
root->left        = newNode(10);
root->right       = newNode(2);
root->left->left  = newNode(1);
root->left->right = newNode(3);
root->right->right = newNode(12);
root->right->left = newNode(7);

printf("Inorder Traversal of the original tree \n");
printInorder(root);

correctBST(root);

printf("\nInorder Traversal of the fixed tree \n");
printInorder(root);

return 0;
}
Output:

 Inorder Traversal of the original tree
 1 10 3 6 7 2 12
 Inorder Traversal of the fixed tree
 1 2 3 6 7 10 12
 Time Complexity: O(n)

その他のテスト ケースについては、このリンクを参照してくださいhttp://ideone.com/uNlPx

于 2012-09-14T05:14:34.650 に答える