trees c basic terminology
Цей поглиблений підручник з дерев C ++ пояснює типи дерев, методи обходу дерев та базову термінологію із зображеннями та прикладами програм:
У цій серії С ++ досі ми бачили лінійну структуру даних як статичної, так і динамічної природи. Тепер ми перейдемо до нелінійної структури даних. Перша структура даних у цій категорії - “Дерева”.
Дерева - це нелінійні ієрархічні структури даних. Дерево - це сукупність вузлів, з’єднаних між собою за допомогою “ребер”, які є напрямленими або ненаправленими. Один із вузлів позначається як “Кореневий вузол”, а решта вузлів називаються дочірніми вузлами або листовими вузлами кореневого вузла.
Загалом, кожен вузол може мати стільки дітей, але лише один батьківський вузол.
=> Ознайомтесь із цілою серією навчальних програм C ++
Вузли дерева або на одному рівні називаються сестринськими вузлами, або вони можуть мати стосунки батьків і дітей. Вузли з однаковим батьком - це вузли братів і сестер.
Що ви дізнаєтесь:
Дерева в C ++
Нижче наведено Приклад дерева з різними частинами.
Давайте розглянемо визначення деяких основних термінів, які ми використовуємо для дерев.
- Кореневий вузол: Це найвищий вузол в ієрархії дерева. На наведеній вище схемі вузол A є кореневим вузлом. Зверніть увагу, що кореневий вузол не має батьківського елемента.
- Листовий вузол: Це найнижчий вузол в ієрархії дерев. Листові вузли - це вузли, які не мають дочірніх вузлів. Вони також відомі як зовнішні вузли. Вузли E, F, G, H і C у вищеназваному дереві - це всі вузли листя.
- Піддерево: Піддерево представляє різних нащадків вузла, коли корінь не є нульовим. Дерево зазвичай складається з кореневого вузла та одного або декількох піддерев. На наведеній вище схемі (B-E, B-F) та (D-G, D-H) є піддеревами.
- Батьківський вузол: Будь-який вузол, крім кореневого вузла, який має дочірній вузол і край вгору до батьківського.
- Вузол предків: Це будь-який вузол-попередник на шляху від кореня до цього вузла. Зверніть увагу, що корінь не має предків. На наведеній вище схемі А і В - предки Е.
- Ключ: Він представляє значення вузла.
- Рівень: Представляє генерацію вузла. Кореневий вузол завжди знаходиться на рівні 1. Дочірні вузли кореня знаходяться на рівні 2, онуки кореня - на рівні 3 тощо. Загалом, кожен вузол знаходиться на рівні вищому, ніж його батьківський.
- Шлях: Шлях - це послідовність послідовних ребер. На наведеній вище схемі шлях до Е дорівнює A => B-> E.
- Ступінь: Ступінь вузла вказує кількість дітей, які має вузол. На наведеній вище діаграмі ступінь B і D дорівнює 2, тоді як ступінь C дорівнює 0.
Типи дерев C ++
Деревову структуру даних можна класифікувати на наступні підтипи, як показано на діаграмі нижче.
# 1) Загальне дерево
Загальне дерево - це основне зображення дерева. Він має вузол і один або кілька дочірніх вузлів. Вузол верхнього рівня, тобто кореневий вузол, присутній на рівні 1, а всі інші вузли можуть бути на різних рівнях.
Загальне дерево показано на малюнку нижче.
друг функціонує в C ++
Як показано на малюнку вище, загальне дерево може містити будь-яку кількість піддерев. Вузли B, C та D присутні на рівні 2 і є вузлами братів та сестер. Подібним чином вузли E, F, G та H також є вузлами братів і сестер.
Вузли, присутні на різних рівнях, можуть мати взаємозв'язок батьків і дітей. На наведеному малюнку вузли B, C і D є дочірніми для A. Вузли E і F є дочірніми для B, тоді як вузли G і H є дочірніми для D.
Загальне дерево показано нижче, використовуючи реалізацію C ++:
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; } Вихід:
Загальне дерево, яке створюється, є таким:
10
/
20 30
/
40
No2) Ліси
Кожного разу, коли ми видаляємо кореневий вузол з дерева та краї, що приєднують елементи наступного рівня та корінь, ми отримуємо несуміжні набори дерев, як показано нижче.
На наведеному вище малюнку ми отримали два ліси, видаливши кореневий вузол A та три ребра, що з’єднували кореневий вузол з вузлами B, C та D.
# 3) Бінарне дерево
Деревоподібна структура даних, у якій кожен вузол має не більше двох дочірніх вузлів, називається двійковим деревом. Бінарне дерево - це найпопулярніша деревоподібна структура даних і використовується в ряді додатків, таких як оцінка виразів, бази даних тощо.
На наступному малюнку показано двійкове дерево.
На наведеному малюнку ми бачимо, що вузли A, B і D мають по двоє дітей. Бінарне дерево, в якому кожен вузол має рівно нуль або два дочірні органи, називається повним бінарним деревом. У цьому дереві немає вузлів, у яких є одна дитина.
Повне двійкове дерево має двійкове дерево, яке повністю заповнене, за винятком найнижчого рівня, який заповнюється зліва направо. Бінарне дерево, показане вище, є повним бінарним деревом.
Далі проста програма для демонстрації двійкового дерева. Зверніть увагу, що висновок дерева - це послідовність обходу в порядку вхідного дерева.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< Вихід:
Створено бінарне дерево:
5 10 15 20 30 40 45
# 4) Бінарне дерево пошуку
Бінарне дерево, яке впорядковується, називається бінарним деревом пошуку. У двійковому дереві пошуку вузли ліворуч менше кореневого вузла, тоді як вузли праворуч більше або дорівнюють кореневому вузлу.
Приклад бінарного дерева пошуку показано нижче.
На наведеному малюнку ми бачимо, що ліві вузли мають менше 20, що є кореневим елементом. Праві вузли, навпаки, більші за кореневий вузол. Бінарне дерево пошуку використовується в техніці пошуку та сортування.
# 5) Дерево виразів
Бінарне дерево, яке використовується для обчислення простих арифметичних виразів, називається деревом виразів.
Просте дерево виразів показано нижче.
У наведеному вище зразку дерева виразів ми представляємо вираз (a + b) / (a-b). Як показано на наведеному малюнку, нелистові вузли дерева представляють оператори виразу, тоді як листові вузли представляють операнди.
Дерева виразів в основному використовуються для розв’язування алгебраїчних виразів.
Методи обходу дерев
Ми бачили лінійні структури даних, такі як масиви, зв’язані списки, стеки, черги тощо. Усі ці структури даних мають загальну техніку обходу, яка обводить структуру лише одним способом, тобто лінійно.
Але у випадку з деревами ми маємо різні методи обходу, як зазначено нижче:
# 1) Для того, щоб: У цій техніці обходу ми спочатку обходимо ліве піддерево, поки в лівому піддереві більше не буде вузлів. Після цього ми відвідуємо кореневий вузол, а потім переходимо до траверсу правого піддерева, поки в правому піддереві не залишиться жодних вузлів. Таким чином, порядок обходу inOrder - лівий-> корінь-> правий.
# 2) Попереднє замовлення: Для техніки обходу попереднього замовлення ми спочатку обробляємо кореневий вузол, потім обходимо все ліве піддерево і, нарешті, обходимо праве піддерево. Отже, порядок обходу попереднього замовлення є коренем-> лівим-> правим.
# 3) Після замовлення: У техніці обходу після замовлення ми обходимо ліве піддерево, потім праве піддерево і, нарешті, кореневий вузол. Порядок обходу для техніки післяпорядку - лівий-> правий-> корінь.
Якщо n - кореневий вузол, а «l» та «r» - лівий та правий вузли дерева відповідно, то алгоритми обходу дерева такі:
Для алгоритму (lnr):
- Перемістіть ліве піддерево за допомогою inOrder (ліве - Піддерево).
- Відвідайте кореневий вузол (n).
- Обхід правого піддерева за допомогою inOrder (праве піддерево).
Алгоритм попереднього замовлення (nlr):
- Відвідайте кореневий вузол (n).
- Обхід лівого піддерева за допомогою попереднього замовлення (ліве піддерево).
- Обхід правого піддерева, використовуючи попереднє замовлення (праве піддерево).
Алгоритм Postorder (LRN):
- Обхід лівого піддерева за допомогою postOrder (ліве піддерево).
- Обхід правого піддерева за допомогою postOrder (праве піддерево).
- Відвідайте кореневий вузол (n).
З наведених алгоритмів обхідних методів ми бачимо, що прийоми можуть застосовуватися до даного дерева рекурсивно, щоб отримати бажаний результат.
Розглянемо наступне дерево.
Використовуючи вищезазначені методи обходу, послідовність обходу для вищезазначеного дерева наведена нижче:
- Обхід InOrder: 2 3 5 6 10
- Обхід попереднього замовлення: 6 3 2 5 10
- Обхід PostOrder: 2 5 3 10 6
Висновок
Дерева - це нелінійна ієрархічна структура даних, яка використовується в багатьох додатках у галузі програмного забезпечення.
На відміну від лінійних структур даних, які мають лише один спосіб переходу за списком, ми можемо обходити дерева різними способами. У цьому посібнику ми детально вивчили техніки обходу та різні типи дерев.
=> Погляньте на посібник для початківців C ++ тут
Рекомендована література
- Структура даних дерева B та дерева B + у C ++
- Структура даних двійкового дерева в C ++
- Види ризиків у програмних проектах
- Структура даних дерева та купи AVL у C ++
- Типи даних Python
- 20 простих запитань для перевірки програмного забезпечення для перевірки базових знань (Інтернет-вікторина)
- Типи даних C ++
- Основні операції введення / виводу на C ++
