Меню

Дървета в C ++: Основна терминология, техники за преминаване и типове дървета на C ++

  • Основен
  • Други
  • Дървета в C ++: Основна терминология, техники за преминаване и типове дървета на C ++

trees c basic terminology

Опитайте Нашия Инструмент За Премахване На Проблемите

Този задълбочен урок за C ++ дървета обяснява типовете дървета, техниките за обхождане на дървета и основната терминология със снимки и примерни програми:

В тази серия C ++ досега сме виждали линейната структура на данните както от статичен, така и от динамичен характер. Сега ще продължим с нелинейната структура на данните. Първата структура от данни в тази категория е „Дървета“.

java интервю въпрос и отговори за по-свежи

Дърветата са нелинейни йерархични структури от данни. Дървото е колекция от възли, свързани помежду си посредством „ръбове“, които са или насочени, или ненасочени. Един от възлите е обозначен като „корен възел“, а останалите възли се наричат ​​дъщерни възли или листни възли на кореновия възел.

По принцип всеки възел може да има толкова много деца, но само един родителски възел.

=> Вижте цялата серия за обучение на C ++

Дърво в C ++

Възлите на дърво са или на едно и също ниво, наречени сестрински възли, или могат да имат връзка родител-дете. Възлите с един и същ родител са братя и сестри.

Какво ще научите:

Дървета в C ++

Дадено по-долу е Примерно дърво с различните му части.

Дърво в C ++ с различните му части

Нека да разгледаме определенията на някои основни термини, които използваме за дървета.

  • Основен възел: Това е най-горният възел в йерархията на дървото. В горната диаграма възел A е основният възел. Обърнете внимание, че основният възел няма родител.
  • Листен възел: Това е най-долният възел в йерархията на дърво. Листовите възли са възлите, които нямат дъщерни възли. Те са известни и като външни възли. Възлите E, F, G, H и C в горното дърво са всички листни възли.
  • Поддърво: Поддърво представлява различни потомци на възел, когато коренът не е нула. Дървото обикновено се състои от корен възел и едно или повече поддървета. В горната диаграма (B-E, B-F) и (D-G, D-H) са поддървета.
  • Родителски възел: Всеки възел с изключение на главния възел, който има дъщерен възел и ръб нагоре към родителя.
  • Възел на предците: Това е всеки предшественик възел по път от корена до този възел. Имайте предвид, че коренът няма предци. В горната диаграма A и B са предците на E.
  • Ключ: Той представлява стойността на възел.
  • Ниво: Представлява генерирането на възел. Коренният възел е винаги на ниво 1. Дочерните възли на корена са на ниво 2, внуците на корена са на ниво 3 и така нататък. По принцип всеки възел е на ниво по-високо от своя родител.
  • Път: Пътят е последователност от последователни ръбове. В горната диаграма пътят към E е A => B-> E.
  • Степен: Степента на възел показва броя на децата, които има възел. В горната диаграма степента на B и D е по 2, докато степента на C е 0.

Видове C ++ дървета

Структурата на дървесните данни може да бъде класифицирана в следните подтипове, както е показано на диаграмата по-долу.

Видове дърво в C ++

# 1) Общо дърво

Общото дърво е основното представяне на дърво. Той има възел и един или повече дъщерни възли. Възелът от най-високо ниво, т.е.коренният възел присъства на ниво 1, а всички останали възли могат да присъстват на различни нива.

Общо дърво е показано на фигурата по-долу.

Общо дърво

Както е показано на горната фигура, общото дърво може да съдържа произволен брой поддървета. Възлите 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

# 2) Гори

Всеки път, когато изтрием кореновия възел от дървото и ръбовете, съединяващи елементите от следващото ниво и корена, получаваме несъединени набори от дървета, както е показано по-долу.

Гори

На горната фигура получихме две гори, като изтрихме кореновия възел 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: '<

Изход:

добавяне на стойности към масив java

Създадено двоично дърво:

5 10 15 20 30 40 45

# 4) Бинарно дърво за търсене

Подреденото двоично дърво се нарича двоично дърво за търсене. В двоично дърво за търсене, възлите вляво са по-малки от кореновия възел, докато възлите вдясно са по-големи или равни на кореновия възел.

Пример за бинарно дърво за търсене е показан по-долу.

Двоично дърво за търсене

На горната фигура можем да видим, че всички леви възли са по-малки от 20, което е основният елемент. Десните възли, от друга страна, са по-големи от кореновия възел. Бинарното дърво за търсене се използва в техниките за търсене и сортиране.

# 5) Дърво на израза

Двоично дърво, което се използва за оценка на прости аритметични изрази, се нарича дърво на израза.

Просто дърво на израза е показано по-долу.

Дърво на израза

В горното примерно дърво на израза ние представяме израза (a + b) / (a-b). Както е показано на горната фигура, нелистовите възли на дървото представляват операторите на израза, докато листните възли представляват операндите.

Дърветата на изразите се използват главно за решаване на алгебрични изрази.

Техники за обръщане на дървета

Виждали сме линейни структури от данни като масиви, свързани списъци, стекове, опашки и др. Всички тези структури от данни имат обща техника на обхождане, която обхожда структурата само по един начин, т.е. линейно.

Но в случая с дърветата имаме различни техники за преминаване, изброени по-долу:

# 1) За да: В тази техника на обхождане първо обхождаме лявото поддърво, докато няма повече възли в лявото поддърво. След това посещаваме кореновия възел и след това продължаваме да пресичаме дясното поддърво, докато няма повече възли, които да прекосяваме в дясното поддърво. По този начин редът на обръщане inOrder е ляв-> корен-> десен.

# 2) Предварителна поръчка: За техниката за обръщане на предварителна поръчка първо обработваме кореновия възел, след това обхождаме цялото ляво поддърво и накрая обхождаме дясното поддърво. Следователно редът на обръщане на предварителна поръчка е корен-> ляв-> десен.

# 3) Следваща поръчка: В техниката за обръщане след поръчка прекосяваме лявото поддърво, след това дясното поддърво и накрая коренния възел. Редът на обхождане за техниката за поднареждане е ляв-> десен-> корен.

Ако n е коренният възел и „l“ и „r“ са съответно леви и десни възли на дървото, тогава алгоритмите за обръщане на дървото са както следва:

За алгоритъм (lnr):

  1. Преместете лявото поддърво с помощта на inOrder (ляво - Поддърво).
  2. Посетете основния възел (n).
  3. Преместете дясно поддърво с помощта на inOrder (дясно поддърво).

Алгоритъм за предварително поръчване (nlr):

  1. Посетете основния възел (n).
  2. Преместете лявото поддърво, като използвате предварително поръчка (ляво поддърво).
  3. Прекосете дясното поддърво, като използвате предварителна поръчка (дясно поддърво).

Алгоритъм за поръчка (lrn):

  1. Преместете лявото поддърво с помощта на postOrder (ляво поддърво).
  2. Прекосете дясното поддърво с помощта на postOrder (дясно поддърво).
  3. Посетете основния възел (n).

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

Помислете за следното дърво.

въпроси за ръчно тестване на интервю за 5 години опит

Алгоритъм за постподреждане (lrn)

Използвайки горните техники на обхождане, последователността на обхождане за горното дърво е дадена по-долу:

  1. Обръщане на InOrder: 2 3 5 6 10
  2. Обхождане на PreOrder: 6 3 2 5 10
  3. Обръщане на PostOrder: 2 5 3 10 6

Заключение

Дърветата са нелинейна йерархична структура от данни, която се използва в много приложения в областта на софтуера.

За разлика от линейните структури от данни, които имат само един начин да прекосят списъка, ние можем да прекосим дървета по различни начини. Имахме подробно проучване на техниките за преминаване и различните видове дървета в този урок.

=> Погледнете тук ръководството за начинаещи C ++

Препоръчително четене

^