Дерево двоичных выражений — Binary expression tree
Бинарное дерево выражения представляет собой специфический вид из двоичного дерева , используемого для представления выражений . Двумя распространенными типами выражений, которые может представлять дерево двоичных выражений, являются алгебраические и логические . Эти деревья могут представлять выражения, содержащие как унарные, так и бинарные операторы.
Каждый узел двоичного дерева и, следовательно, дерева двоичного выражения имеет ноль, один или два потомка. Эта ограниченная структура упрощает обработку деревьев выражений.
Обзор
Листья дерева двоичного выражения — это операнды, такие как константы или имена переменных, а другие узлы содержат операторы. Эти конкретные деревья оказываются двоичными, потому что все операции являются двоичными, и, хотя это самый простой случай, у узлов может быть более двух дочерних элементов. У узла также может быть только один дочерний элемент, как в случае с унарным оператором минус. Дерево выражения T можно оценить, применив оператор в корне к значениям, полученным рекурсивным вычислением левого и правого поддеревьев.
Обход
Алгебраическое выражение может быть получено из дерева двоичных выражений путем рекурсивного создания заключенного в скобки левого выражения, затем распечатки оператора в корне и, наконец, рекурсивного создания заключенного в скобки правого выражения. Эта общая стратегия (влево, узел, вправо) известна как обход по порядку . Альтернативная стратегия обхода — рекурсивно распечатать левое поддерево, правое поддерево, а затем оператор. Эта стратегия обхода обычно известна как обход после заказа . Третья стратегия — сначала распечатать оператор, а затем рекурсивно распечатать левое и правое поддерево, известное как обход предварительного заказа.
Эти три стандартных обхода в глубину представляют собой три различных формата выражений: инфиксный, постфиксный и префиксный. Инфиксное выражение создается обходом в порядке, постфиксное выражение создается обходом после порядка, а префиксное выражение создается обходом перед порядком.
Обход инфиксов
Когда печатается инфиксное выражение, открывающая и закрывающая круглые скобки должны быть добавлены в начале и в конце каждого выражения. Поскольку каждое поддерево представляет собой подвыражение, открывающая скобка печатается в его начале, а закрывающая скобка печатается после обработки всех его дочерних элементов.
Algorithm infix (tree) /*Print the infix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the infix expression has been printed*/ if (tree not empty) if (tree token is operator) print (open parenthesis) end if infix (tree left subtree) print (tree token) infix (tree right subtree) if (tree token is operator) print (close parenthesis) end if end if end infix
Постфиксный обход
Постфикса выражение формируется основной postorder обхода любого двоичного дерева. Скобки не требуются.
Algorithm postfix (tree) /*Print the postfix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the postfix expression has been printed*/ if (tree not empty) postfix (tree left subtree) postfix (tree right subtree) print (tree token) end if end postfix
Префиксный обход
Algorithm prefix (tree) /*Print the prefix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the prefix expression has been printed*/ if (tree not empty) print (tree token) prefix (tree left subtree) prefix (tree right subtree) end if end prefix
Построение дерева выражений
Построение дерева происходит путем чтения постфиксного выражения по одному символу за раз. Если символ является операндом, создается одноузловое дерево, и его указатель помещается в стек . Если символ является оператором, указатели на два дерева T1 и T2 извлекаются из стека и формируется новое дерево, корнем которого является оператор, а левый и правый дочерние элементы которого указывают на T2 и T1 соответственно. Затем указатель на это новое дерево помещается в стек.
пример
Ввод в постфиксной нотации: ab + cde + * * Поскольку первые два символа являются операндами, создаются одноузловые деревья, и указатели на них помещаются в стек. Для удобства стек будет расти слева направо.
Следующий символ — «+». Он выталкивает два указателя на деревья, формируется новое дерево, и указатель на него помещается в стек.
Затем считываются c, d и e. Для каждого создается одноузловое дерево, и указатель на соответствующее дерево помещается в стек.
Далее читается знак «+», и последние два дерева объединяются.
Теперь читается «*». Выскакивают два последних указателя на дерево, и формируется новое дерево со знаком «*» в качестве корня.
Наконец, читается последний символ. Два дерева объединяются, и указатель на последнее дерево остается в стеке.
Источник
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .
Способ представления бинарного дерева:
Корень дерева расположен на уровне с минимальным значением.
Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.
Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
- Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
- Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
- Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
struct tnode <
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
При этом обход дерева в префиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
cout field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в инфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в постфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout field; //Отображаем корень дерева
>
>
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) <
if (tree == NULL ) < // Если дерева нет, то формируем корень
tree = new tnode; // память под узел
tree->field = x; // поле данных
tree->left = NULL ;
tree->right = NULL ; // ветви инициализируем пустотой
> else if (x < tree->field) // условие добавление левого потомка
tree->left = addnode(x,tree->left);
else // условие добавление правого потомка
tree->right = addnode(x,tree->right);
return (tree);
>
Удаление поддерева
void freemem(tnode *tree) <
if (tree!= NULL ) <
freemem(tree->left);
freemem(tree->right);
delete tree;
>
>
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
- указатель на текст слова;
- счетчик числа встречаемости;
- указатель на левого потомка;
- указатель на правого потомка.
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид
#include
#include
#include
#include
//#include
#define MAX WORD 100
struct tnode < // узел дерева
char * word; // указатель на строку (слово)
int count; // число вхождений
struct tnode* left; // левый потомок
struct tnode* right; // правый потомок
>;
// Функция добавления узла к дереву
struct tnode* addtree( struct tnode* p, char * w) int cond;
if (p == NULL ) p = ( struct tnode*)malloc( sizeof ( struct tnode));
p->word = _strdup(w);
p->count = 1;
p->left = p->right = NULL ;
>
else if ((cond = strcmp(w, p->word)) == 0)
p->count++;
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
>
// Функция удаления поддерева
void freemem(tnode* tree) if (tree != NULL ) freemem(tree->left);
freemem(tree->right);
free(tree->word);
free(tree);
>
>
// Функция вывода дерева
void treeprint( struct tnode* p) if (p != NULL ) treeprint(p->left);
printf( «%d %s\n» , p->count, p->word);
treeprint(p->right);
>
>
int main() struct tnode* root;
char word[MAX WORD ];
root = NULL ;
do scanf_s( «%s» , word, MAX WORD );
if (isalpha(word[0]))
root = addtree(root, word);
> while (word[0] != ‘0’ ); // условие выхода – ввод символа ‘0’
treeprint(root);
freemem(root);
getchar();
getchar();
return 0;
>
Результат выполнения
Комментариев к записи: 19
Источник