Установка узлов в бинарном дереве поиска (C)

Я пытаюсь написать функцию, чтобы вставить узел в бинарное дерево поиска, и я следующее:Установка узлов в бинарном дереве поиска (C)

typedef struct Node { 
    int key; 
    struct Node *left; 
    struct Node *right; 
} Node; 

Node *createNode(int key) 
{ 
    Node *newNode = (Node *)malloc(sizeof(Node)); 
    newNode->key = key; 
    newNode->left = NULL; 
    newNode->right = NULL; 

    return newNode; 
} 

Node *insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      node->left = insert(node->left, key); 
     } 
     else 
     { 
      node->right = insert(node->right, key); 
     } 
    } 
    return node; 
} 

int main(int argc, char* argv[]) 
{ 
    Node *root = NULL; 
    root = insert(root, 10); 

    return 0; 
}

Я знаю, что это работает, и если я хочу вставить 5 в дерево с корневым узлом root, я могу написать root = insert(root, 5);. Мой вопрос в том, как я могу написать еще одну версию insert, которая может добиться того же самого, просто с insert(root, 5);? Я пробовал следующее, но безрезультатно.

void insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      insert(node->left, key); 
     } 
     else 
     { 
      insert(node->right, key); 
     } 
    } 
}

Что не так с этим и почему это не работает ?. Любые указатели (не предназначенные для каламбуров) были бы очень признательны!

источник

2015-11-15 Kevin Hsu

Короткий ответ: нет. есть случаи, когда вам нужно изменить значение корня. (например: когда дерево пустое, а корень - NULL). Один из способов - с помощью assignmnt с использованием возвращаемого значения (как в вашем рабочем примере). Другой способ - передать указатель на указатель. (указатель на root) к функции. – wildplasser

Причина в том, что когда вы вставляете значение в BST, вы должны убедиться, что BST * остается * BST (например, левый дочерний элемент содержит узлы со значениями меньше родительского узла и где правый ребенок содержит только узлы со значениями, большими или равными родительскому.). Это означает, что вам нужно будет проверить наличие нескольких условий при вставке, и вам, возможно, придется перемещать узел или лист (или корневой узел) вокруг, чтобы удовлетворить ограничения BST. –

Для меня ваше первое решение элегантно.

Теперь, если вы хотите вставить без использования возвращаемого значения, тогда можно использовать указатель на указатель.

Что-то вроде:

void insert(Node ** node, int key) 
{ 
    if (*node == NULL) 
     *node = createNode(key); 
    else if ((*node)->key > key) 
     insert(&(*node)->left, key); 
    else 
     insert(&(*node)->right, key); 
}

И призыв будет

insert(&root, 10);

источник

2015-11-15 02:17:38 lrleon

Установка узлов в бинарном дереве поиска (C)

ответ

Смежные вопросы