Функція вставки використовується для додавання нового елемента в бінарне дерево пошуку у відповідному місці. Функція вставки має бути розроблена таким чином, щоб її вузол порушував властивість бінарного дерева пошуку для кожного значення.
- Виділіть пам'ять для дерева.
- Встановіть для частини даних значення та встановіть лівий і правий покажчики дерева, вказуйте на NULL.
- Якщо елемент, який потрібно вставити, буде першим елементом дерева, то ліворуч і праворуч від цього вузла вказуватимуть на NULL.
- В іншому випадку перевірте, чи елемент менший за кореневий елемент дерева, якщо це правда, тоді рекурсивно виконайте цю операцію з лівою частиною кореня.
- Якщо це невірно, то виконайте цю операцію рекурсивно з правим піддеревом кореня.
Вставити (ДЕРЕВО, ЕЛЕМЕНТ)
Виділити пам'ять для ДЕРЕВА
ВСТАНОВИТИ ДЕРЕВО -> ДАНІ = ЕЛЕМЕНТ
ВСТАНОВИТИ ДЕРЕВО -> ВЛІВО = ДЕРЕВО -> ВПРАВО = NULL
ІНШЕ
IF ITEM DATA
Вставити (ДЕРЕВО -> ВЛІВО, ЕЛЕМЕНТ)
ІНШЕ
Вставити (ДЕРЕВО -> ПРАВОРУЧ, ЕЛЕМЕНТ)
[КІНЕЦЬ ЯКЩО]
[КІНЕЦЬ ЯКЩО]
C Функція
#include #include void insert(int); struct node { int data; struct node *left; struct node *right; }; struct node *root; void main () { int choice,item; do { printf(' Enter the item which you want to insert? '); scanf('%d',&item); insert(item); printf(' Press 0 to insert more ? '); scanf('%d',&choice); }while(choice == 0); } void insert(int item) { struct node *ptr, *parentptr , *nodeptr; ptr = (struct node *) malloc(sizeof (struct node)); if(ptr == NULL) { printf('can't insert'); } else { ptr -> data = item; ptr -> left = NULL; ptr -> right = NULL; if(root == NULL) { root = ptr; root -> left = NULL; root -> right = NULL; } else { parentptr = NULL; nodeptr = root; while(nodeptr != NULL) { parentptr = nodeptr; if(item data) { nodeptr = nodeptr -> left; } else { nodeptr = nodeptr -> right; } } if(item data) { parentptr -> left = ptr; } else { parentptr -> right = ptr; } } printf('Node Inserted'); } }
Вихід
Enter the item which you want to insert? 12 Node Inserted Press 0 to insert more ? 0 Enter the item which you want to insert? 23 Node Inserted Press 0 to insert more ? 1