c语言，二叉搜索树，完成bst.c中未完成的insert函数

Question

主函数用不同的键调用插入，然后通过对二叉搜索树的顺序遍历，按顺序打印插入的键。最终运行确保在电脑终端上可运行。
一个主程序文件，叫做btree.c， 主要的程序代码，无任何错误，不需要任何更改

// DSA Programming 4.1 - Binary search tree
// You do not need to change anything here

#include <stdio.h>
#include <stdlib.h>
#include "bst.h"



int main(){
    
    bst tree;
    tree.root = 0; 
   
    bst_insert(&tree, 50);
    bst_insert(&tree, 20);
    bst_insert(&tree, 80);
    bst_insert(&tree, 30);
    bst_insert(&tree, 70);
    bst_insert(&tree, 40);

    print_tree_inorder(tree);
    printf("\n");
    
    // Free memory
    bst_delete(tree.root);

    return 0;
}

头文件bst.h, 无任何错误，不需要更改

// DSA Programming 4.1 - Binary search tree
// You do not need to change anything here

#ifndef BST_H_INCLUDED
#define BST_H_INCLUDED

// Defines node and its pointer
typedef struct bstnd {
    int key;
    struct bstnd* parent;
    struct bstnd* left;
    struct bstnd* right;
} bstnode, *pbstnode;

// Defines the tree
typedef struct bt {
    pbstnode root;
} bst;

// Inserts key in the tree
void bst_insert(bst *bt, int key);

// Prints node
void print_node(pbstnode n);

// Prints the tree
void print_tree_inorder(bst bt);

// Deletes a tree whose root is node
void bst_delete(pbstnode node);

#endif

bst.c 包含二叉搜索树的实现，但是insert 函数未完成，这是一个将节点插入到二叉搜索树中的函数，从TODO开始的地方开始完善

// DSA Programming 4.1 - Binary search tree
// You work at the place where TODO is

#include <stdio.h>
#include <stdlib.h>
#include "bst.h"

// Prints a node
void print_node(pbstnode n){
    if(n != 0){
        printf("%d ",(n->key));
    }
}

// Calls the printing of a node in inorder traversal
void print_inorder(pbstnode pnode){
    if (pnode != 0) {
        print_inorder(pnode->left);
        print_node(pnode);
        print_inorder(pnode->right);
    }
}

// Prints the whole tree inorder
void print_tree_inorder(bst bt){
    print_inorder(bt.root);
}

/*
   Allocates a node with key as data
   and inserts it in the tree
*/

void bst_insert(bst *bt, int key){
    bstnode *newnode = (bstnode *)malloc(sizeof(bstnode));
    newnode->key = key;
    newnode->left = 0;
    newnode->right = 0;
    newnode->parent = 0;
    
    pbstnode x = bt->root;
    pbstnode y=0;

    // TODO! Your implementation here!

}

// Delete the whole tree to free the memory
void bst_delete(pbstnode node){
    if(node != 0) {
        bst_delete(node->left);
        bst_delete(node->right);
        free(node);
    }
}

Answer 1

思路：既然x存的是bt的根节点，那么我们就顺着根节点往下遍历，直到找出比当前key还要大，或者比当前key还要小的叶子节点，所以需要一个while循环，用y来临时保存当前遍历到哪个节点了，防止有可能遍历的叶子节点可能是空的，反而找不到空叶子节点对应的父节点，
一旦跳出while循环了说明我们找到了需要插入的叶子节点的位置了，我们再给他赋值，看是往左叶子还是右叶子节点加即可。

void bst_insert(bst* bt, int key) {
    bstnode* newnode = (bstnode*)malloc(sizeof(bstnode));
    newnode->key = key;
    newnode->left = 0;
    newnode->right = 0;
    newnode->parent = 0;

    pbstnode x = bt->root;
    pbstnode y = 0;

    // TODO! Your implementation here!
    while (x != NULL) {
        y = x;
        if (key < x->key)
        {
            x = x->left;
        }
        else 
        {
            x = x->right;
        }
    }

    newnode->parent = y;

    if (y == NULL) {
        bt->root = newnode;
    }
    else if (key < y->key) {
        y->left = newnode;
    }
    else {
        y->right = newnode;
    }
}