Здравствуйте, читатели, теперь мы начнем обсуждение бинарных деревьев. Возможно, вы видели линейные структуры данных, но дерево — нелинейное. Итак, давайте углубимся в детали бинарного дерева и посмотрим, что это такое? Как они реализуются? и различные функции бинарного дерева.

Дерево — это нелинейная структура данных с иерархическим расположением элементов данных, называемых узлами. Центральный узел наверху называется корневым узлом, поскольку он является корнем дерева, и этот узел может получить доступ ко всем элементам. Верхние узлы являются родительским узлом, а другие узлы, связанные с ним, являются его дочерними узлами, мы обрабатываем деревья через это родительско-дочернее отношение. Два некорневых узла, подключенных к одному и тому же родителю, называются братьями и сестрами.

Существует много типов деревьев, и наше обсуждение будет посвящено бинарному дереву.

Бинарное дерево

Бинарное дерево — это дерево, в котором каждый родительский узел имеет не более двух дочерних узлов, т. е. каждый узел может иметь 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;
}

Конец…

Надеюсь, я смог хорошо объяснить каждую тему, и теперь ваша очередь самостоятельно кодировать двоичное дерево, это сделает ваши концепции более сильными.

Продолжайте учиться и счастливого программирования :-)