Здравствуйте, читатели, теперь мы начнем обсуждение бинарных деревьев. Возможно, вы видели линейные структуры данных, но дерево — нелинейное. Итак, давайте углубимся в детали бинарного дерева и посмотрим, что это такое? Как они реализуются? и различные функции бинарного дерева.
Дерево — это нелинейная структура данных с иерархическим расположением элементов данных, называемых узлами. Центральный узел наверху называется корневым узлом, поскольку он является корнем дерева, и этот узел может получить доступ ко всем элементам. Верхние узлы являются родительским узлом, а другие узлы, связанные с ним, являются его дочерними узлами, мы обрабатываем деревья через это родительско-дочернее отношение. Два некорневых узла, подключенных к одному и тому же родителю, называются братьями и сестрами.
Существует много типов деревьев, и наше обсуждение будет посвящено бинарному дереву.
Бинарное дерево
Бинарное дерево — это дерево, в котором каждый родительский узел имеет не более двух дочерних узлов, т. е. каждый узел может иметь 0, 1 или 2 дочерних узла.
Вы можете видеть на рисунке выше, что каждый узел имеет не более 2 узлов. Мы называем дочерние узлы левым и правым узлом.
Типы
По структуре дерева бинарное дерево можно разделить на:
Полное бинарное дерево
В полном бинарном дереве заполнены все уровни, кроме, возможно, последнего, и все узлы заполнены как можно дальше слева, т. е. может быть возможно, что узлы справа не соединены ни с каким другим узлом.
Полное бинарное дерево
В полном бинарном дереве каждый узел имеет либо 0, либо 2 узла.
Идеальное бинарное дерево
В идеальном бинарном дереве все узлы имеют по два потомка и все листья находятся на одном уровне.
Общие термины
Корень
Корневые узлы — это самые верхние узлы дерева.
Родительский узел
Узлы, которые соединены с другими узлами в нисходящем направлении, называются родительскими узлами, поскольку они действуют как родительские по отношению к другим последующим узлам.
Дочерний узел
Узлы, подключенные к родительскому узлу, называются дочерними узлами этого родителя.
Листовой узел
Листовые узлы — это последние узлы, то есть узлы без дочерних элементов или узлы, присутствующие на последнем уровне ветви.
Внутренний узел
Узел, который присутствует в позиции, отличной от последнего уровня. Другими словами, узлы, имеющие 1 или более дочерних узлов, то есть это узлы, отличные от конечных узлов.
Глубина узла
Глубина узла — это количество ребер между узлом и корневым узлом.
Высота узла
Высота узла — это количество ребер между узлами и его листовыми узлами. Высота корневого узла равна высоте дерева.
Создание узла дерева
Теперь мы рассмотрели основные термины бинарного дерева и начнем понимать реализацию и работу бинарного дерева. Базовой единицей бинарного дерева является его узел, и для продвижения вперед мы сначала создадим узел, поэтому давайте посмотрим, как мы можем создать узел бинарного дерева.
Каждый узел содержит три компонента:
- Указатель на левое поддерево.
- Указатель на правое поддерево.
- Элемент данных
class node{ public: int data; node* left; node* right; node(int d){ data = d; left=NULL; right = NULL; } };
Мы использовали класс вместо структуры, как в C++, мы берем три переменных данных для хранения элементов данных и два указателя слева и справа от типа данных «узел», поскольку тип данных указателя на узел должен быть таким же, как у узел. Мы использовали конструктор с тем же именем, что и класс, т. е. node, в конструкторе узла данные передаются и сохраняются в блоке данных, а левый и правый указатели по умолчанию установлены в NULL.
Обход дерева
Обход — это доступ к каждому узлу дерева, обход может быть выполнен разными способами, и мы обсудим их один за другим.
Почтовый заказ
Опубликовать здесь означает, что доступ к родительскому элементу будет последним, то есть сначала мы получим доступ к левому поддереву, затем к правому поддереву, а затем к родительскому узлу. Порядок будет Левый → Правый → Родительский.
Алгоритм
Пока не будут пройдены все узлы —
Шаг 1 — Рекурсивный обход левого поддерева.
Шаг 2 − Рекурсивно пройти по правому поддереву.
Шаг 3 − Посетить корневой узел.
Давайте посмотрим, каким будет обратный обход дерева выше.
POSTORDER:A → C → E → D → B → H → I → G → F
Чтобы
Inorder здесь означает, что доступ к дереву будет осуществляться в порядке слева направо, то есть сначала мы обращаемся к левому поддереву, затем к родительскому узлу, затем к правому поддереву. Порядок будет следующим: Left → Parent → Right .
Алгоритм
Пока не будут пройдены все узлы —
Шаг 1 — Рекурсивный обход левого поддерева.
Шаг 2 − Посетить корневой узел.
Шаг 3 − Рекурсивно пройти по правому поддереву.
Давайте посмотрим, каким будет неупорядоченный обход дерева выше.
НЕПОРЯДОК:A → B → C → D → E → F → G → H → I
Предзаказ
Pre здесь означает, что сначала будет осуществлен доступ к родителю, т. е. сначала мы получим доступ к родительскому узлу, левому поддереву, а затем к правому поддереву. Порядок будет таким: Parent → Left → Right .
Алгоритм
Пока не будут пройдены все узлы –
Шаг 1– Посетите корневой узел.
Шаг 2– Рекурсивно обходим левое поддерево.
Шаг 3 — Рекурсивно обходим правое поддерево.
Давайте посмотрим, каким будет предварительный порядок обхода вышеприведенного дерева.
ПРЕДЗАКАЗ:F → B → A → D → C → E → G → I → H
УровеньПорядок
При обходе по уровням мы будем обращаться к дереву уровень за уровнем слева направо. Мы реализуем его, используя две функции: одну для обхода определенного уровня, а другую для обхода всех уровней, вызывая первую функцию.
Давайте посмотрим, каков порядок обхода вышеприведенного дерева.
LEVELORDER:F → B → G → A → D → I → C → E → H
void printKLevel(node* root,int l){ if(root==NULL) return; if(l==1){ cout<<root->data<<" "; return; } printKLevel(root->left , l-1); printKLevel(root->right , l-1); } void printALLevels(node* root){ int h=height(root); for(int i=0 ; i<h ; i++){ printKLevel(root,i); cout<<endl; } return; }
Операция с двоичным деревом
Строительное дерево
node* buidtree(string s){ if(s=="true"){ int d; cin>>d; node*root=new node(d); string l; cin>>l; if(l=="true"){ root->left=buidtree(l); } string r; cin>>r; if(r=="true"){ root->right=buidtree(r); } return root; } return NULL; }
Вставка
/*function to insert element in binary tree */
void
insert(Node* temp, int
key){
queue<Node*> q; q.push(temp);
while
(!q.empty()) { Node* temp = q.front(); q.pop();
if
(!temp->left) { temp->left = new
Node(key); break;
} else
{q.push(temp->left);
}if
(!temp->right) { temp->right = new
Node(key); break;
} else
{q.push(temp->right);
} }
}
Удаление
Удаление в бинарном дереве проще, чем в других деревьях, поскольку нет определенного порядка, но мы удаляем самый правый элемент на последнем уровне дерева, так как это уменьшит размер дерева при удалении.
Если какой-либо конкретный элемент не определен, то правая большая часть удаляется, но обычно она не используется, в отличие от стека, поэтому обычно пользователь или тестер определяет элемент, который нужно удалить, мы удалим элементы в два этапа:
- Во-первых, мы заменим удаляемый элемент на последний, т.е. самый правый элемент последнего уровня.
- Во-вторых, мы удалим элемент, присутствующий в крайней правой позиции.
Высота дерева
Высота дерева — это высота корневого узла, которая представляет собой количество ребер между корневым узлом и последним узлом.
Мы можем рассчитать высоту, вычислив количество ребер в левом и правом поддеревьях, а затем взять максимальное из них и увеличить на 1, рекурсия делает это довольно просто. Мы добавляем 1 из-за дополнительного ребра, используемого для соединения левого или правого поддерева с корневым узлом.
int height(node* root){ if(root==NULL) return 0; int ls = height(root->left); int rs = height(root->right); return max(ls,rs)+1; }
Конец…
Надеюсь, я смог хорошо объяснить каждую тему, и теперь ваша очередь самостоятельно кодировать двоичное дерево, это сделает ваши концепции более сильными.
Продолжайте учиться и счастливого программирования :-)