c - 如何在二叉搜索树中找到交换节点？

Question

这是一个面试问题。

给定一棵二叉搜索树，交换两个节点的值。问题是如何在树的单次遍历中同时找到节点和交换值？

我曾尝试使用以下代码解决此问题，但我无法停止递归，因此我遇到了段错误。帮助我如何停止递归。

#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;

}

Answer 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 被交换了。