如果 BST 中插入的值应该插入到左子树或右子树中，如何打印

Question

我在 BST 中插入值并打印“left”，如果该值应该插入左子树或“ right" 如果应该将值插入右子树，但是当我要打印时，打印了几个 right/left，我该如何解决？我认为这是由于递归但我不能不递归解决它。

BST插入码：

Node *insert(Node **root, int key)
{
    if(*root == NULL)
    {
        Node *newNode = (Node*)malloc(sizeof(Node));
        if(newNode == NULL)
            return NULL;
        newNode->key= key;
        newNode->left = NULL;
        newNode->right = NULL;
        (*root) = newNode; 
        return newNode; 
    }
    if(key < (*root)->key){
        printf("left ");
        return insert(&((*root)->left),key);
    }
    else{
        printf("right ");
        return insert((&(*root)->right),key);
    }
}

示例： 正在插入值：25 - 20 - 36 - 10 - 22 - 30

Answer 1

我从预期输出中得到的是“左”或“右”表示节点相对于其父节点的相对位置。如果是这样，您可以这样做：

if(key < (*root)->key){
    if ( (*root)->left==NULL)
        printf("left ");
    return insert(&((*root)->left),key);
}
else{
    if ( (*root)->right==NULL)
           printf("right ");
    return insert((&(*root)->right),key);
}

逻辑是，我们将在插入步骤前 1 步知道它是左还是右。我刚刚检查了我们要去的下一个节点是否为 NULL。

如果 BST 中插入的值应该插入到左子树或右子树中，如何打印

How to print if the value inserted in a BST should be inserted in the left or right subtree

binary-search-tree