Полное двоичное дерево с

Построить полное бинарное дерево из его представления в виде связанного списка

Имея связанный список, постройте из него полное бинарное дерево. Предположим, что порядок элементов, представленных в связанном списке, такой же, как и в полном представлении массива дерева.

Для узла дерева в позиции i в связанном списке левый дочерний элемент присутствует в позиции 2×i , и правый потомок присутствует в позиции 2×i + 1 . (Здесь положение i начинается с 1).

Например, связанный список 1 —> 2 —> 3 —> 4 —> 5 —> 6 должны быть преобразованы в следующее полное бинарное дерево:

В отличие от массива, мы не можем напрямую обращаться к узлам в связанном списке. Поэтому невозможно рекурсивно построить полное двоичное дерево со связанным списком.

Обратите внимание, что корень полного бинарного дерева — это голова связанного списка, а два его потомка — следующие два узла в связанном списке, и каждый уровень полного бинарного дерева содержит последовательные узлы в связанном списке.

Мы знаем, что каждый уровень в полном бинарном дереве заполнен, за исключением, возможно, последнего, где узлы заполняются слева направо. Идея состоит в том, чтобы построить полное бинарное дерево уровень за уровнем. Ниже приведен псевдокод для простого queueоснованный на алгоритме с использованием обход порядка уровней:

construct(head):

root —> next_node(head)
q —> empty queue
q.enqueue(root)

while (next_node(head))
node —> q.dequeue()

node.left = next_node(head)
q.enqueue(node.left)

node.right = next_node(head)
q.enqueue(node.right)

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Источник

Реализуйте структуру данных двоичного дерева в C++

1. Реализуйте двоичное дерево с помощью ключевого слова struct в C++
2. Реализуйте функции для вычисления размера и высоты древовидной структуры и функцию для печати элементов в C++

В этой статье объясняется, как реализовать структуру данных двоичного дерева в C++.

Реализуйте двоичное дерево с помощью ключевого слова struct в C++

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

Бинарное дерево является одним из подклассов древовидной структуры данных и определяется как дерево, в котором каждый узел должен иметь не более двух дочерних узлов, включая дочерние узлы, обозначенные как left и right . В этом случае мы реализуем двоичное дерево с помощью функции struct , поскольку она объявляет класс, члены которого по умолчанию являются общедоступными. Узел в двоичном дереве содержит два указателя на левый/правый узлы и данные по мере необходимости. Обратите внимание, что мы объявили один член int для представления данных, хранящихся в узле, только в целях объяснения.

Мы определяем конструктор, который принимает целое число в качестве аргумента и инициализирует член данные его значением. Затем он инициализирует двухузловые указатели со значениями nullptr , что является обычным способом обозначения конечных узлов. Пример кода драйвера создает примерный граф и сохраняет случайные целые числа в каждом узле. Существует несколько подтипов двоичных деревьев, например, полное двоичное дерево — это структура, в которой каждый узел имеет 0 или 2 потомков. Другое называется идеальным двоичным деревом, в котором все внутренние узлы имеют двух дочерних элементов, а все листовые узлы имеют одинаковую глубину.

#include #include  using std::cout; using std::endl;  struct BinTreeNode   int data;  struct BinTreeNode *left;  struct BinTreeNode *right;   BinTreeNode() = default;  explicit BinTreeNode(int d): data(d)   left = nullptr;  right = nullptr;  > >;  constexpr int MIN = 1; constexpr int MAX = 10000;  int main()   std::random_device rd;  std::mt19937 eng(rd());  std::uniform_int_distributionint> distr(MIN, MAX);   auto root = new BinTreeNode(distr(eng));  root->left = new BinTreeNode(distr(eng));  root->right = new BinTreeNode(distr(eng));  root->right->left = new BinTreeNode(distr(eng));  root->right->right = new BinTreeNode(distr(eng));   return EXIT_SUCCESS; > 

Обратите внимание, что приведенный выше код дает полную двоичную древовидную структуру, как показано на следующем графике. Мы выделили каждый узел с помощью оператора new и передали значение инициализатора с помощью генератора псевдослучайных чисел.

 root  / \  left right  / \ / \ nullptr nullptr left right  / \ / \  nullptr nullptr nullptr nullptr 

Реализуйте функции для вычисления размера и высоты древовидной структуры и функцию для печати элементов в C++

Поскольку древовидная структура представляет собой форму, в которой выполняются алгоритмы разделяй и властвуй , последний метод часто используется для реализации функций, управляющих их элементами. Функция treeSize извлекает размер дерева, который обозначает количество всех узлов, включая корень. Обратите внимание, что нам нужно только использовать простую рекурсию и вернуть размер root значения (которое равно 1) плюс размеры левого / правого узлов.

Следующая функция — treeHeight — извлекает высоту дерева, которая обычно известна как количество узлов на самом длинном пути от корня до листа. Эта функция также использует рекурсию, вызывая себя на обоих дочерних узлах и возвращая высоту root значения (равного 1) плюс большее значение из предыдущих вызовов.

С другой стороны, функция printData выводит элемент data из каждого узла в поток cout . Существует несколько способов обхода бинарной древовидной структуры: обход, предварительный и последующий обход.

В следующем примере используется способ обхода в порядке. Процесс сначала распечатывает данные из крайних левых листовых узлов, идущих вправо на той же глубине, а затем переходит на верхние уровни. Следующий фрагмент кода создает частично случайное двоичное дерево, а затем вызывает на нем каждую из вышеперечисленных функций. Если на первый взгляд рекурсивная природа этих функций сбивает с толку, вам следует попробовать отладить их пошагово на меньших объектах дерева и понаблюдать за поведением при каждом вызове рекурсивной функции.

#include #include  using std::cout; using std::endl;  struct BinTreeNode   int data;  struct BinTreeNode *left;  struct BinTreeNode *right;   BinTreeNode() = default;  explicit BinTreeNode(int d): data(d)   left = nullptr;  right = nullptr;  > >;  int treeSize(BinTreeNode *n)   if (n == nullptr)  return 0;  else  return 1 + treeSize(n->left) + treeSize(n->right); >  int treeHeight(BinTreeNode *n)   int lh, rh;   if (n == nullptr)  return -1;  else   lh = treeHeight(n->left);  rh = treeHeight(n->right);  return 1 + (lh > rh ? lh : rh);  > >  void printData(BinTreeNode *n)   if (n != nullptr)   printData(n->left);  cout  ->data  <"; ";  printData(n->right);  > >  constexpr int MIN = 1; constexpr int MAX = 10000;  int main()   std::random_device rd;  std::mt19937 eng(rd());  std::uniform_int_distributionint> distr(MIN, MAX);   auto root = new BinTreeNode(distr(eng));  auto tmp = root;   auto iter = 100;  while (iter > 0)   auto val = distr(eng);  if (val % 5 == 0)   tmp->left = new BinTreeNode(distr(eng));  tmp = tmp->left;  > else if (val % 4 == 0)   tmp->right = new BinTreeNode(distr(eng));  tmp = tmp->right;  > else if (val % 6 == 0)   tmp->left = new BinTreeNode(distr(eng));  > else if (val % 100 == 0)   tmp = root;  > else if (val % 2 == 0)   tmp->right = new BinTreeNode(distr(eng));  >  iter -= 1;  >   cout  <"size of tree = "     cout  <"height of tree = "     printData(root);   return EXIT_SUCCESS; > 

size of tree = 45 height of tree = 37 . (elements in the tree) 

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

Сопутствующая статья — C++ Data Structure

Источник

Двоичное дерево

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

Типы двоичных деревьев

Полное двоичное дерево

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.

Совершенное двоичное дерево

Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

1. Все уровни должны быть заполнены.
2. Все листовые вершины склоняются влево.
3. У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.

Представление двоичного дерева

Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.

Примеры реализации

Python

# Двоичное дерево в Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Прямой обход дерева def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Центрированный обход дерева def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Обратный обход дерева def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Прямой обход дерева: ", end="") root.traversePreOrder() print("\nЦентрированный обход дерева: ", end="") root.traverseInOrder() print("\nОбратный обход дерева: ", end="") root.traversePostOrder()

Java

// Двоичное дерево на Java // Создание узла class Node < int key; Node left, right; public Node(int item) < key = item; left = right = null; >> class BinaryTree < Node root; BinaryTree(int key) < root = new Node(key); >BinaryTree() < root = null; >// Центрированный обход дерева public void traverseInOrder(Node node) < if (node != null) < traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); >> // Обратный обход дерева public void traversePostOrder(Node node) < if (node != null) < traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); >> // Прямой обход дерева public void traversePreOrder(Node node) < if (node != null) < System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); >> public static void main(String[] args) < BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Прямой обход дерева: "); tree.traversePreOrder(tree.root); System.out.print("\nЦентрированный обход дерева: "); tree.traverseInOrder(tree.root); System.out.print("\nОбратный обход дерева: "); tree.traversePostOrder(tree.root); >>

Си

// Обход дерева на Си #include #include struct node < int item; struct node* left; struct node* right; >; // Центрированный обход дерева void inorderTraversal(struct node* root) < if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); > // Прямой обход дерева void preorderTraversal(struct node* root) < if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); > // Обратный обход дерева void postorderTraversal(struct node* root) < if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); > // Создание нового узла struct node* createNode(value) < struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; > // Вставка потомка слева от родительской вершины struct node* insertLeft(struct node* root, int value) < root->left = createNode(value); return root->left; > // Вставка потомка справа от родительской вершины struct node* insertRight(struct node* root, int value) < root->right = createNode(value); return root->right; > int main() < struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Центрированный обход дерева\n"); inorderTraversal(root); printf("\nПрямой обход дерева\n"); preorderTraversal(root); printf("\nОбратный обход дерева\n"); postorderTraversal(root); >

С++

// Двоичное дерево на С++ #include #include using namespace std; struct node < int data; struct node *left; struct node *right; >; // Создание нового узла struct node *newNode(int data) < struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); > // Прямой обход дерева void traversePreOrder(struct node *temp) < if (temp != NULL) < cout data; traversePreOrder(temp->left); traversePreOrder(temp->right); > > // Центрированный обход дерева void traverseInOrder(struct node *temp) < if (temp != NULL) < traverseInOrder(temp->left); cout data; traverseInOrder(temp->right); > > // Обратный обход дерева void traversePostOrder(struct node *temp) < if (temp != NULL) < traversePostOrder(temp->left); traversePostOrder(temp->right); cout data; > > int main() < struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout

Где используется

• Для быстрого доступа к данным.
• В алгоритмах маршрутизации.
• Для реализации куч.
• В синтаксических деревьях.

Источник