如何找到一个二叉搜索树交换节点？ [英] How to find swapped nodes in a binary search tree?
问题描述
这是一个面试问题。
二叉搜索树，并给出两个节点的值已被调换。现在的问题是如何找到在树中的一个穿越两个节点和交换价值？
我已经尝试过这种使用下面code，但我不能够让我得到段错误的递归停下来解决。帮我如何停止递归。
的#include＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; limits.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
/ *一个二叉树节点有数据指针，左子
的指针和指向右孩子* /
结构节点
{
int数据;
结构节点*离开;
结构节点*权利;
};
/ *辅助函数，分配一个新的节点与
给定的数据和NULL左，右指针。 * /
结构节点* newNode（int数据）
{
结构节点*节点=（结构节点*）
的malloc（的sizeof（结构节点））;
- 于节点GT;数据=数据;
- 于节点GT;左= NULL;
- 于节点GT;右= NULL;
返回（节点）;
}
无效modifiedInorder（结构节点*根，结构节点** nextNode）
{
静态INT nextdata = INT_MAX;
如果（根）
{
modifiedInorder（根 - ＆GT;右，nextNode）;
如果（根 - ＆GT;数据＆GT; nextdata）
返回;
* nextNode =根;
nextdata =根 - ＆GT;的数据;
modifiedInorder（根 - ＆GT;左，nextNode）;
}
}
无效序（结构节点*根，结构节点* copyroot，结构节点** prevNode）
{
静态INT prevdata = INT_MIN;
如果（根）
{
序（根 - ＆GT;左，copyroot，prevNode）;
如果（根 - ＆GT;数据＆LT; prevdata）
{
结构节点* nextNode = NULL;
modifiedInorder（copyroot，和放大器; nextNode）;
int数据= nextNode-＆GT;的数据;
nextNode-＆GT;数据=（* prevNode） - ＆GT;的数据;
（* prevNode） - ＆GT;数据=数据;
返回;
}
* prevNode =根;
prevdata =根 - ＆GT;的数据;
序（根 - ＆GT;右，copyroot，prevNode）;
}
}
/ *给定一个二叉树，打印序的节点* /
无效printInorder（结构节点*节点）
{
如果（节点== NULL）
返回;
/ *先易复发的左子* /
printInorder（与于节点GT;左）;
/ *然后打印节点的数据* /
的printf（％D，与于节点GT;数据）;
/ *现在再次出现在右子* /
printInorder（与于节点GT;右一）;
}
诠释的main（）
{
/ * 4
/ \
2 3
/ \
1 5
* /
结构节点*根= newNode（1）; // newNode将返回一个节点。
根 - ＆GT;左= newNode（2）;
根 - ＆GT;右= newNode（3）;
根 - ＆GT;左＆GT;左= newNode（4）;
根 - ＆GT;左＆GT;右= newNode（5）;
的printf（序遍历原树的\ n）;
printInorder（根）;
结构节点* prevNode = NULL;
序（根，根，和放大器; prevNode）;
的printf（\ nInorder穿越固定树的\ n）;
printInorder（根）;
返回0;
}
步行到使用序遍历的树。通过使用将得到的所有元素进行排序，并且将大于周边元件被交换的一个元件。
例如考虑下面这个二叉树
_ 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交换。
This is an interview Question.
A binary search tree is given and the values of two nodes have been swapped. The question is how to find both the nodes and the swapped values in a single traversal of the tree?
i have tried to solve this using below code but i am not able to stop the recursion so i am getting segmentation fault. help me how to stop recursion.
#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;
}
Walk to the tree using inorder traversal. By using that you will get all the elements sorted and the one element that will be greater than the surrounding elements is swapped.
For example consider this below binary tree
_ 20 _
/ \
15 30
/ \ / \
10 17 25 33
/ | / \ / \ | \
9 16 12 18 22 26 31 34
First, we linearize this into an array and we get
9 10 16 15 12 17 18 20 22 25 26 30 31 33 34
Now you can notice that 16 is greater than its surrounding elements and that 12 is less than them. This immediately tells us that 12 and 16 were swapped.
这篇关于如何找到一个二叉搜索树交换节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
