Удаление элемента из дерева, С++

#дерево #бинарное_дерево #алгоритм #cpp

Написал алгоритм удаления элемента из бинарного дерева поиска. Алгоритм не рекурсивный.
Так как это академическая задачка, требуют рекурсивный. Рекурсивный метод у меня не
выходит. Код выкладывать смысла нет. Если у кого есть простой и понятный рекурсивный
алгоритм удаления элемента из бинарного дерева поиска, буду благодарен.     

Ответы

Ответ 1

Если взять такое определение бинарного дерева.
class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

То алгоритм может выглядеть так:
void DeleteNodeFromBinary(BinaryTreeNode * node, int value)
{
    if (node == NULL)
        return;

    if (value < node->value)
        return DeleteNodeFromBinary(node->leftChild, value);
    else if(value > node->value)
        return DeleteNodeFromBinary(node->rightChild, value);
    else  {
        if(node->leftChild == NULL && node->rightChild == NULL) {
            if (node->parent->leftChild == node) 
                node->parent->leftChild = NULL;
            else      
                node->parent->rightChild = NULL;
            delete node;
        } else {
            BinaryTreeNode * newnode = NULL;
            if(node->leftChild != NULL) {
                newnode = Rightmost(node->leftChild);
            } else                    
                newnode = Leftmost(node->rightChild);

            if (node->parent->leftChild == node) 
                node->parent->leftChild = newnode;
            else      
                node->parent->rightChild = newnode;

            newnode->parent = node->parent;
            newnode->rightChild = node->rightChild;
            newnode->leftChild = node->leftChild;

            delete node; 
        }
    }
}
BinaryTreeNode * Leftmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->leftChild != NULL) {
        return Leftmost(node->leftChild);
    }
    return node;
}
BinaryTreeNode * Rightmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->rightChild != NULL) {
        return Rightmost(node->rightChild);
    }
    return node;
}

Копия дерева на С++

#дерево #c #бинарное_дерево #алгоритм #cpp

В работе появилась простая, и в тоже время интересная задачка. Необходимо написать
функцию, которая будет копировать дерево. Язык С или С++, лучше на С++.
    

Ответы

Ответ 1

Если считать, что дерево бинарное, то можно предложить следующее:
Объявление класса
class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Функция копирования возвращает указатель на корень нового дерева.
BinaryTreeNode * CopyTree(BinaryTreeNode * node)
{
    if (node == NULL)
        return NULL;

    BinaryTreeNode * newnode = new BinaryTreeNode(node->value);
    newnode->leftChild = CopyTree(node->leftChild);
    newnode->rightChild = CopyTree(node->rightChild);

    return newnode;
}


Ответ 2

Если считать что дерево immutable и ссылки на родительскую вершину не нужны, то можно
скопировать дерево за O(1), достаточно скопировать только корень

Вернуть самый дальний лист бинарного дерева поиска

#cpp #алгоритм #бинарное_дерево

Есть дерево BST заданное как 

struct treeNode {
    int info;
    treeNode *left //левый
    treeNode *right; // правый
    treeNode *parent; // предыдущий
};


Нужно запилить метод, который возвращал бы указатель на самый дальний листик этого
дерева(конец самого длинного пути). Если таких несколько, то на любой из них.

Нужно достать именно указатель на листик, потому что от него дальше я пойду назад
до корня зеркально разворачивать дерево относительно этого пути вот так: 

void mirror (treeNode *farthestLeaf) {
    treeNode *tmp = NULL;
    while (farthestLeaf->parent != NULL) {
        tmp = farthestLeaf->parent->left;
        farthestLeaf->parent->left = farthestLeaf->parent->right;
        farthestLeaf->parent->right = tmp;
        farthestLeaf = farthestLeaf->parent;
    }
}


Есть ли у вас какие-нибудь идеи?
    

Ответы

Ответ 1

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

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

const struct treeNode* findDeapest(const struct treeNode* cur, int *deapth) {
  const struct treeNode *rv = cur;
  int curDeapth=*deapth;

  if (cur->left) {
    (*deapth)++;
    rv = findDeapest (cur->left, deapth);
  }
  if (cur->right) {
    int rightDeapth=curDeapth+1;
    const struct treeNode *rightDeapest = findDeapest (cur->right, &rightDeapth);
    if (rightDeapth>*deapth) {
      *deapth = rightDeapth;
      rv = rightDeapest;
    }
  }
  return rv;
}

//вызов
int deapth = 0;
struct treeNode* deapest = findDeapest (myTreeRooteNode, &deapth);

Прохождение бинарного дерева (post-order)

#cpp #c #алгоритм #бинарное_дерево

Здравствуйте, как на с/с++ написать нерекурсивный обход бинарного дерева через стек
методом post-order (сначала листья, потом корень)? 
    

Ответы

Ответ 1

Т.к. рекурсию использовать нельзя, мы вместо неё будем использовать два стэка. Вот
весь алгоритм, в результате его будут распечатаны все вершины бинарного дерева в post-order
порядке (можно вместо распечатки делать какое-то полезное действие):


Добавить корень в первый стэк.
Пока первый стэк не пуст выполнять следующие два подпункта:

2.1. Извлечь узел из вершины первого стэка, добавить его во второй стэк.

2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк.
Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка
и печатать.


Замечание: в конце порядок распечатки для поддеревьев будет тот же что и при помещении
в 1й стэк, т.е. мы помещали в 1й стэк левого а затем правого ребёнка, при распечатке
в итоге будет раньше распечатано левое поддерево, затем правое, а затем родитель. Если
нужно в распечатке иметь вначале правое поддерево а затем левое тогда нужно в 1й стэк
помещать вначале правого ребёнка затем левого.

Какие существуют виды деревьев или классификация деревьев в теории графов?

#дерево #графы #бинарное_дерево

Пишу работу по деревьям в теории графов и немного запутался в понятиях. Мне нужно
написать, какие существуют виды деревьев или классификацию деревьев. Я нашел что существует:
ориентированное/неориентированное дерево, остовное, лес, бинарное, n-мерное, упорядоченное
дерево. Но это всё больше похоже на свойства деревьев нежели на виды (кроме бинарного
и n-мерного). 

Что из этого (если я правильно нашел и ничего не пропустил) действительно будет являться
отдельным видом дерева? Также, есть например частный случай бинарного дерева - дерево
поиска. Будет ли такое дерево относиться к теории графов или это больше структура данных
в программировании? Тот же вопрос с деревом синтаксического анализа. И последний вопрос:
относится ли обход дерева к операциям с деревьями как графами или это алгоритм для
структуры данных - дерево?
    

Ответы

Ответ 1

Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить
материал.

Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.

Я бы на вашем месте сделал классификацию по признакам:

По направленности - ориентированное (однонаправленное, двунаправленное), неориентированное

По степени вершины (бинарное, n-арное, и т.п.)

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

Поскольку дерево является графом, то к нему применимы классические алгоритмы обхода
любого графа, но помимо этого существуют специфичные алгоритмы именно для деревьев.

Если вы студент, и это какая-то работа для университета, то чем больше вы напишете,
при условии что разобрались в сути происходящего - тем лучше. Писать что-то не разобравшись
не нужно, может вылезти боком потом.

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

#бинарное_дерево #cpp

По заданию требуется реализовать бинарное дерево для хранения и операций с данными
вида: Деталь, Количество, Поставщик(С++). Я составила фрагмент программы нахождения
имени поставщика , который поставляет наибольшее количество деталей
    struct Ttree *Ttree_max (struct Ttree *temp)
    {
        if (temp==NULL)
        return NULL;
        while (temp->right!= NULL) 
        temp= temp-> right;
        return temp;
    }

Однако такой вариант не подходит, необходимо это сделать методом рекурсии, составить
функцию, проверяющую всех поставщиков (Name) методом обхода всего дерева с вызовом
функции подсчета количества деталей (Const) по каждому поставщику(Name). В процессе
подсчета запомнить элемент с наибольшим количеством, а в конце вывести его на экран(Name).
Помогите разобраться.
Вот часть кода программы:
    #include 
    #include 
    #include 
    using namespace std;

    struct Ttree 
{   int Const;      
    char Name[30];      
    char Detal[30];      
    struct Ttree *left;   
    struct Ttree *right;

};
    struct Ttree* add
    (
     Ttree *beg, int Const, char Name[30], char Detal[30]
    )

   {
      if (!beg) 
        {               
           struct Ttree *temp = new Ttree;
          temp->Const = Const;
          strcpy_s(temp->Name, 30, Name);
          strcpy_s(temp->Detal, 30, Detal);

          temp->left = 0;
          temp->right = 0;
          return temp;
        }
     else if ((Const)>(beg->Const)) 
        {                 
          beg->right = add(beg->right, Const, Name, Detal);
          return beg;
        }
     else 
        {        
          beg->left = add(beg->left, Const, Name, Detal);
          return beg;
        }
    }

___....____
    struct Ttree *Ttree_max (struct Ttree *temp)
    {
        if (temp==NULL)
        return NULL;
        while (temp->right!= NULL) 
        temp= temp-> right;
        return temp;
    }
    

Ответы

Ответ 1

Чтобы найти Name поставщика с максимальным количеством деталей, необходимо запомнить
текущий максимум и пройтись по всему дереву, заменяя максимум при нахождении большего
количества. Это делается примерно так:
#include 

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

#бинарное_дерево

Требуется реализовать бинарное дерево, НО:
Обязательное ли условие, чтобы правая крайняя сторона с корня увеличивалась до максимума,
а левая крайняя сторона уменьшалась до минимума?(см. на приложенное изображение) Интернет
перерыл, но прямым текстом это нигде не написано, но на одних визуализациях это условие
выполняется, а на других нет.  

Обновлено:
Можно ли данную реализацию считать бинарным деревом?

    

Ответы

Ответ 1

Определения

Определение бинарного дерева:(1)


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


Определение бинарного дерева поиска:(2)


  Будем называть бинарное дерево деревом поиска, если для любой вершины
  ключ этой вершины не меньше ключа любой вершины левого поддерева и
  строго меньше ключа любой вершины правого поддерева


Ссылки:


  (1) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и
  программирование, Схемы хранения данных (Москва, 2006 г.) стр 67
  
  (2) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и
  программирование, Схемы хранения данных (Москва, 2006 г.) стр 74




Изображение на рисунке терминала является бинарным деревом, но не бинарном деревом
поиска, так как нет алфавитного или какого-нибудь другого, заранее обговорённого, порядка

Визуализация бинарного дерева

#c_sharp #бинарное_дерево

Преподаватель задал реализовать визуализацию дерева, однако мою визуализацию он таки
не принял. Вопрос: Что не так с этим деревом?

using System;
using System.Collections;
using System.Linq;
using System.Text;

namespace tree
{
class Program
{
    static void Main(string[] args)
    {
        char[] arrayS;
        int n, m;
        Console.WriteLine("Введите строку");
        arrayS = Console.ReadLine().ToArray();
        arrayS = SortArray(arrayS);
        n = getN(arrayS.Length);
        m = (int)Math.Pow(2, n - 1) * 2 + 1;
        char[,] tree = new char[n, m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                tree[i, j] = ' ';
            }
        }
        tree[0, m / 2] = arrayS[0];
        int position = 1;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (tree[i, j] != ' ' && tree[i, j] != '_')
                {
                    if (position < arrayS.Length)
                    {
                        tree[i + 1, j - (int)Math.Pow(2, n - 2 - i)] = arrayS[position++];
                        for (int k = j - (int)Math.Pow(2, n - 2 - i); k < j; k++)
                            tree[i, k] = '_';
                    }
                    if(position arr[j])
                {
                    min = arr[j];
                    arr[j] = arr[i];
                    arr[i] = min;
                }
            }
        }

        char[] array = new char[arr.Length];
        int position = arr.Length / 2-1;
        for (int i = 1; i < arr.Length; i+=2, position--)
        {
            array[i] = arr[position];
        }
        position = arr.Length / 2;
        for (int i = 0; i < arr.Length; i+=2, position++)
        {
            array[i] = arr[position];
        }
        return array;
    }


}

}

    

Ответы

Ответ 1

У вас как в левом так и в правом поддереве есть значения, как больше так и меньше
N. Дерево предполагает, что с одной стороны на любую глубину все значения меньше чем
на вершине, а справа больше.


Ответ 2

public static int Print(Node node, int x, int y)
    {
        Console.SetCursorPosition(x, y);
        Console.Write(node.Value);

        var loc = y;

        if (node.Right != null)
        {
            Console.SetCursorPosition(x + 2, y);
            Console.Write("--");
            y = Print(node.Right, x + 4, y);
        }

        if (node.Left != null)
        {
            while (loc <= y)
            {
                Console.SetCursorPosition(x, loc + 1);
                Console.Write(" |");
                loc++;
            }
            y = Print(node.Left, x, y + 2);
        }

        return y;
    }

Бинарное дерево поиска на C/C++

#c #алгоритм #бинарное_дерево #дерево #cpp

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево
бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются
временная и пространственная сложность алгоритма, а так же универсальность подхода.    

Ответы

Ответ 1

UPD: моя неправда, исправляю.
Предположим, что дерево определено так:
struct BinaryTreeNode {
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}

    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Тогда алгоритм проверки будет следующим:
bool isBST(BinaryTreeNode * root)
{
    return isBST_(root, 0, 0);
}

bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent)
{
    if (minParent && minParent->value >= node->value)
        return false;
    if (maxParent && maxParent->value <= node->value)
        return false;
    if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node))
        return false;
    if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent))
        return false;
    return true;    
}

Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность
O(h), где h — глубина дерева.


Ответ 2

http://www.structur.h1.ru/derevo.htm - тут написанна структура дерева
по сути ваша задача хорошо решается рекурсией рекурсивно идете вниз по дереву если
при проверке оказывается что это не дерево - throw SomeError; если все нормально -
то никаких исключений кидать не надо рекурсия развернется свернется и говорите что все ОК


Ответ 3

Обходим дерево по правилу ЛКП, по дороге проверяем, получается ли возрастающая последовательность
(или убывающая, можно определить по первым двум неравным значениям). Если не получается
- то не дерево поиска. Как то так.

Почти полное бинарное дерево

#дерево #бинарное_дерево #cpp

Подскажите, пожалуйста, как сделать так, чтобы функция проходилась к примеру по всей
левой части дерева? 

Я сделал функцию проверки дерева на то, является ли оно почти полным, но при входе
в левое поддерево, функция проверяет не всех потомков.. аналогичная проблема в правом
поддереве

bool PBDPP1 (TNode* ptree, int &cnt)
{
    if (ptree != NULL)
    {   cnt++;
        if(ptree->right != 0 && ptree->left == 0)            
            return false;
        PBDPP1(ptree->left, cnt);
        PBDPP1(ptree->right, cnt);
    }
    else return true;
}

bool PPBD(TNode *rootTree)
{
    int cnt1 = 0, cnt2 = 0;
    if(rootTree != NULL)
    {
       if(PBDPP1(rootTree->left, cnt2))
       {
          if(PBDPP1(rootTree->right, cnt1))
          {
              int res = cnt2 - cnt1;
              if(res >= 0)
                  return true;
              else
                  return false;
          }
       }
   }
   else return false;
}


Напомню, почти полным двоичным деревом называется двоичное дерево, для которого существует
такое целое число h ≥ 0, что: 


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

    

Ответы

Ответ 1

Решение взято от сюда. 

Предлагается обходить дерево в ширину и на каждом шаге проверять условия:


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


В коде вот так примерно:

bool IsAlmostComplete(TNode * root)
{
    std::queue nodes;
    nodes.push(root);

    bool leaf_found = false;
    while(!nodes.empty())
    {
         TNode * node = nodes.front(); 
         nodes.pop();

         if(leaf_found && (node->left || !node->right))
             return false;          // у автора true, думаю он ошибся

         if(!node->left && !node->right)
             leaf_found = true;

         if(node->left && !node->right)
             return false;

         if(node->left)
             nodes.push(node->left);

         if(node->right)
             nodes.push(node->right);
    }
    return true;
}

Как найти суммы последовательных узлов в бинарном дереве?

Дано: бинарное дерево (алгоритм дерева написан вручную). Число S. Нужно найти последовательность узлов (только с вверху вниз или наоборот) в бинарном дереве, сумма которых равна S
Например: есть бинарное дерево, а число S = 9.
Решение: 3+6, 4+5, 9.
п.с. желательно, что бы это был отдельный класс, который имел доступ к классу binTree
#pragma once class binTree { protected: struct Node { int Value; Node * pLeft; Node * pRight; Node * pParent; Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) {} }; Node * m_pRoot; void InoderTreeWalk(Node * x); Node * TreeSuccessor(Node *x); Node * TreeMin(Node * x); public: binTree(); ~binTree(); virtual void TreeInsert(int k); Node * TreeSearch(Node * X, int k); void ShowTree(); int Root(); };

Ответ

Задача тянет на олимпиадную, пишу идею.
Решение будет сделано с помощью динамики по дереву.
Для каждого узла в дереве заведём список значений. Инициализация - в листах {0, Value}. Пересчёт снизу вверху. Значение для узла пересчитывается примерно так (текущая вершина U):
for (auto left : U->left->list) U->list.add(left + U->Value); for (auto right: U->left->right) U->list.add(right+ U->Value); U->add(U->Value); U->list->unique();
Я специально пишу псевдокодом, т.к. там может быть любая структура от специфики задачи (list vector set bitset) и т.д.
Для каждой вершины, где в списке есть S будет последовательность ответ, которая заканчивается в ней. Её можно восстановить примерно так. Последовательность однозначно задаётся начальным и конченым элементом. Я верну только начальные.
list fun(Tree *U, int S){ S -= U->Value;
list tmp; if (S == 0) tmp.add(U);
if (U->left->list.contains(S)) tmp.add(fun(U->left,S); if (U->rigth->list.contains(S)) tmp.add(fun(U->rigth,S); return tmp; }
Сложно что-то порядка O(N^2 log N). Оптимизировать можно, но если выводить все последовательности то их может быть примерно столько же. Дальнейшие реализации/оптимизации вам виднее.

Удаление элемента из дерева, С++

Написал алгоритм удаления элемента из бинарного дерева поиска. Алгоритм не рекурсивный. Так как это академическая задачка, требуют рекурсивный. Рекурсивный метод у меня не выходит. Код выкладывать смысла нет. Если у кого есть простой и понятный рекурсивный алгоритм удаления элемента из бинарного дерева поиска, буду благодарен.

Ответ

Если взять такое определение бинарного дерева. class BinaryTreeNode { public: BinaryTreeNode() : leftChild(NULL), rightChild(NULL), parent(NULL), value(-1) {} BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), parent(NULL), value(val) {} public: static int getDepth(BinaryTreeNode * node) { int left = 0, right = 0; left = getDepth(node->leftChild); return 0; } public: BinaryTreeNode * leftChild; BinaryTreeNode * rightChild; BinaryTreeNode * parent; int value; }; То алгоритм может выглядеть так: void DeleteNodeFromBinary(BinaryTreeNode * node, int value) { if (node == NULL) return;
if (value < node->value) return DeleteNodeFromBinary(node->leftChild, value); else if(value > node->value) return DeleteNodeFromBinary(node->rightChild, value); else { if(node->leftChild == NULL && node->rightChild == NULL) { if (node->parent->leftChild == node) node->parent->leftChild = NULL; else node->parent->rightChild = NULL; delete node; } else { BinaryTreeNode * newnode = NULL; if(node->leftChild != NULL) { newnode = Rightmost(node->leftChild); } else newnode = Leftmost(node->rightChild);
if (node->parent->leftChild == node) node->parent->leftChild = newnode; else node->parent->rightChild = newnode;
newnode->parent = node->parent; newnode->rightChild = node->rightChild; newnode->leftChild = node->leftChild;
delete node; } } } BinaryTreeNode * Leftmost(BinaryTreeNode * node) { if (node == NULL) return NULL; if (node->leftChild != NULL) { return Leftmost(node->leftChild); } return node; } BinaryTreeNode * Rightmost(BinaryTreeNode * node) { if (node == NULL) return NULL; if (node->rightChild != NULL) { return Rightmost(node->rightChild); } return node; }

Прохождение бинарного дерева (post-order)

Здравствуйте, как на с/с++ написать нерекурсивный обход бинарного дерева через стек методом post-order (сначала листья, потом корень)?

Ответ

Т.к. рекурсию использовать нельзя, мы вместо неё будем использовать два стэка. Вот весь алгоритм, в результате его будут распечатаны все вершины бинарного дерева в post-order порядке (можно вместо распечатки делать какое-то полезное действие):
Добавить корень в первый стэк. Пока первый стэк не пуст выполнять следующие два подпункта:
2.1. Извлечь узел из вершины первого стэка, добавить его во второй стэк.
2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк. Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка и печатать.
Замечание: в конце порядок распечатки для поддеревьев будет тот же что и при помещении в 1й стэк, т.е. мы помещали в 1й стэк левого а затем правого ребёнка, при распечатке в итоге будет раньше распечатано левое поддерево, затем правое, а затем родитель. Если нужно в распечатке иметь вначале правое поддерево а затем левое тогда нужно в 1й стэк помещать вначале правого ребёнка затем левого.

Какие существуют виды деревьев или классификация деревьев в теории графов?

Пишу работу по деревьям в теории графов и немного запутался в понятиях. Мне нужно написать, какие существуют виды деревьев или классификацию деревьев. Я нашел что существует: ориентированное/неориентированное дерево, остовное, лес, бинарное, n-мерное, упорядоченное дерево. Но это всё больше похоже на свойства деревьев нежели на виды (кроме бинарного и n-мерного).
Что из этого (если я правильно нашел и ничего не пропустил) действительно будет являться отдельным видом дерева? Также, есть например частный случай бинарного дерева - дерево поиска. Будет ли такое дерево относиться к теории графов или это больше структура данных в программировании? Тот же вопрос с деревом синтаксического анализа. И последний вопрос: относится ли обход дерева к операциям с деревьями как графами или это алгоритм для структуры данных - дерево?

Ответ

Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить материал.
Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.
Я бы на вашем месте сделал классификацию по признакам:
По направленности - ориентированное (однонаправленное, двунаправленное), неориентированное
По степени вершины (бинарное, n-арное, и т.п.)
По частным случаям - тоже неплохо описать было бы, чего как. Дерево бинарного поиска можно вложить в классификацию по степеням вершины и описать чем оно выделяется. Дерево синтаксического анализа более специфичная вещь, но если сможете описать - отлично.
Поскольку дерево является графом, то к нему применимы классические алгоритмы обхода любого графа, но помимо этого существуют специфичные алгоритмы именно для деревьев.
Если вы студент, и это какая-то работа для университета, то чем больше вы напишете, при условии что разобрались в сути происходящего - тем лучше. Писать что-то не разобравшись не нужно, может вылезти боком потом.

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

Требуется реализовать бинарное дерево, НО: Обязательное ли условие, чтобы правая крайняя сторона с корня увеличивалась до максимума, а левая крайняя сторона уменьшалась до минимума?(см. на приложенное изображение) Интернет перерыл, но прямым текстом это нигде не написано, но на одних визуализациях это условие выполняется, а на других нет.
Обновлено: Можно ли данную реализацию считать бинарным деревом?

Ответ

Определения
Определение бинарного дерева:(1)
Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным, в противном случае будем дерево называть произвольным
Определение бинарного дерева поиска:(2)
Будем называть бинарное дерево деревом поиска, если для любой вершины ключ этой вершины не меньше ключа любой вершины левого поддерева и строго меньше ключа любой вершины правого поддерева
Ссылки:
(1) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и программирование, Схемы хранения данных (Москва, 2006 г.) стр 67 (2) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и программирование, Схемы хранения данных (Москва, 2006 г.) стр 74

Изображение на рисунке терминала является бинарным деревом, но не бинарном деревом поиска, так как нет алфавитного или какого-нибудь другого, заранее обговорённого, порядка

Визуализация бинарного дерева

Преподаватель задал реализовать визуализацию дерева, однако мою визуализацию он таки не принял. Вопрос: Что не так с этим деревом?
using System; using System.Collections; using System.Linq; using System.Text;
namespace tree { class Program { static void Main(string[] args) { char[] arrayS; int n, m; Console.WriteLine("Введите строку"); arrayS = Console.ReadLine().ToArray(); arrayS = SortArray(arrayS); n = getN(arrayS.Length); m = (int)Math.Pow(2, n - 1) * 2 + 1; char[,] tree = new char[n, m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { tree[i, j] = ' '; } } tree[0, m / 2] = arrayS[0]; int position = 1; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { if (tree[i, j] != ' ' && tree[i, j] != '_') { if (position < arrayS.Length) { tree[i + 1, j - (int)Math.Pow(2, n - 2 - i)] = arrayS[position++]; for (int k = j - (int)Math.Pow(2, n - 2 - i); k < j; k++) tree[i, k] = '_'; } if(position } } // 54637 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write(tree[i, j]); } Console.WriteLine(); }
}
private static int getN(int length) { if (length == 1) return 1; else return 1 + getN(length / 2); }
private static char[] SortArray(char[] arr) { char min = arr[0]; for (int i = 0; i < arr.Length; i++) { min = arr[i]; for (int j = i; j < arr.Length; j++) { if (min > arr[j]) { min = arr[j]; arr[j] = arr[i]; arr[i] = min; } } }
char[] array = new char[arr.Length]; int position = arr.Length / 2-1; for (int i = 1; i < arr.Length; i+=2, position--) { array[i] = arr[position]; } position = arr.Length / 2; for (int i = 0; i < arr.Length; i+=2, position++) { array[i] = arr[position]; } return array; }
}
}

Ответ

У вас как в левом так и в правом поддереве есть значения, как больше так и меньше N. Дерево предполагает, что с одной стороны на любую глубину все значения меньше чем на вершине, а справа больше.

Бинарное дерево поиска на C/C++

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются временная и пространственная сложность алгоритма, а так же универсальность подхода.

Ответ

UPD: моя неправда, исправляю. Предположим, что дерево определено так: struct BinaryTreeNode { BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), parent(NULL), value(val) {}
BinaryTreeNode * leftChild; BinaryTreeNode * rightChild; BinaryTreeNode * parent; int value; }; Тогда алгоритм проверки будет следующим: bool isBST(BinaryTreeNode * root) { return isBST_(root, 0, 0); }
bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent) { if (minParent && minParent->value >= node->value) return false; if (maxParent && maxParent->value <= node->value) return false; if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node)) return false; if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent)) return false; return true; } Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность O(h), где h — глубина дерева.