C语言中二叉搜索树的中序后继节点,以下代码是否可以实现搜索?

C语言中二叉搜索树的中序后继节点,以下代码是否可以实现搜索?运行显示不对

img


#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* parent;
};
int prev = INT_MIN;
struct node* Insert(struct node* root,int data){
    if (root == NULL)
    {
        struct node* temp = (struct node*)malloc(sizeof(struct node));
        temp->data = data;
        temp->left = temp->right = NULL;
        root = temp;
    }
    else if (data < root->data)
    {
        root->left = Insert(root->left,data);
    }
    else{
        root->right = Insert(root->right,data);
    }
    return root;
}
//check if a tree is a BST
int InOrderBst(struct node* root){
    int a,b;
    if (root == NULL)
        return 1;
    else
        //中序遍历
        a = InOrderBst(root->left);
        if(a == 0 || prev > root->data)
            return 0 ;
        prev = root->data;
        b = InOrderBst(root->right);
        return b;
}
//find the smallest node
struct node* FindMin(struct node* root){
    if (root == NULL)
    {
        return NULL;
    }
    while (root->left != NULL)
    {
        root = root->left;
    }
    return root;
}
//find the node
struct node* Find(struct node* root,int data){
    if (root == NULL){
        return root;
    }
    else if (data < root->data){
        Find(root->left,data);
    }
    else if (data > root->data){
        Find(root->right,data);
    }
    return root;
}
//find the successor of a root
struct node* InOrderSuccessor(struct node* root,int data){
    struct node* current = Find(root,data);
    if (current == NULL)
    {
        return NULL;
    }
    //have right tree
    if (current->right != NULL)
    {
        return FindMin(current->right);
    }
    //no right tree
    else if (current->right == NULL)
    {
        struct node* successor = NULL;
        struct node* ancestor = root;
        while (ancestor != current)
        {
            if (current->data < ancestor->data)
            {
                successor = ancestor;
                ancestor = ancestor->left;
            }
            else{
                ancestor = ancestor->right;
            }
        }
        return successor;
    }  
}
int main(){
    struct node* root = NULL;
    root = Insert(root,15);
    root = Insert(root,10);
    root = Insert(root,20);
    root = Insert(root,22);
    root = Insert(root,19);
    root = Insert(root,13);
    root = Insert(root,8);
    printf("%d\n",InOrderSuccessor(root,20)->data);
}

引用 皆我百晓生 小程序回复内容作答:

是的,以上代码可以实现搜索二叉搜索树中序后继节点的功能。它使用递归地插入节点到二叉搜索树中,并实现了检查树是否符合二叉搜索树的规则,查找二叉搜索树中最小节点,查找指定节点以及查找给定节点的中序后继节点的功能。在主函数中,将一些节点插入二叉搜索树,然后打印出目标节点的中序后继节点的值。