Вставить узлы в деревья выражений

Question

Вставить узлы в деревья выражений

Я пытаюсь оценить выражение, используя двоичное дерево. Дерево имеет следующие характеристики:

Каждый узел имеет ноль, одного или двух дочерних элементов.
Только узлы, содержащие операторы, могут иметь детей.
Все листовые узлы должно быть номера.
Для простоты допустимы только операторы: * а также +

Что-то вроде тех:
Деревья выражений

Это мой класс дерева:

class ExpressionTree {
struct Node {
std::string data;

Node *leftChild, *rightChild;

Node(std::string d): data(d), leftChild(NULL), rightChild(NULL) {}
} *root;
uint tsize;
public:
ExpressionTree(): root(NULL), tsize(0) {}
Node* treeRoot() { return root; }
void insert(std::string s);
};

И это моя функция вставки:

void insert(std::string s) {
if (root == NULL) {
root = new Node(s);
++tsize;
} else {
Node* current = root;
while (true) {
if (is_operator(current->data)) {
if (current->leftChild == NULL) {
current->leftChild = new Node(s);
++tsize;
return;
} else if (current->rightChild == NULL) {
current->rightChild = new Node(s);
++tsize;
return;
} else {
if (is_operator(current->leftChild->data)) {
current = current->leftChild;
continue;
} else if (is_operator(current->rightChild->data)) {
current = current->rightChild;
continue;
} else {
std::cout << "Error: only nodes who hold operators"<< " can have children." << std::endl;
return;
}
}
}
}
}
}

Проблема в этой функции. Я написал это, начиная с функции для вставки узлов в Двоичное дерево поиска, но это не работает Когда я запускаю простой основной (что, используя insert(), добавляет узлы второго дерева по одному), он падает, не возвращая никакой ошибки, только диалоговое окно Windows 7, которое просит проверить онлайн решение.

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

Я надеюсь, что этот вопрос не слишком конкретен.

Замечания: is_operator() берет строку и возвращает true если это + или же *и ложь в противном случае.

0

c++expression-trees list

Решение

Другие решения

Проблема может быть решена добавлением к классу возможности отслеживать родитель узел для каждого узла. Вот новый класс:

class ExpressionTree {
struct Node {
std::string data;

Node *leftChild, *rightChild;
Node* parent; // +

Node(std::string d, Node* p):
data(d), leftChild(NULL), rightChild(NULL), parent(p) {}
} *root;
uint tsize;
public:
ExpressionTree(): root(NULL), tsize(0) {}
Node* treeRoot() { return root; }
void insert(std::string s);
};

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

Так же insert() Функция нуждается в некоторых модификациях. Вот:

void insert(std::string s) {
if (root == NULL) {
root = new Node(s, NULL);
++tsize;
} else {
Node* current = root;
while (true) {
if (is_operator(current->data)) {
if (current->leftChild == NULL) {
current->leftChild = new Node(s, current);
++tsize;
return;
} else if (current->rightChild == NULL) {
current->rightChild = new Node(s, current);
++tsize;
return;
} else {
if (is_operator(current->leftChild->data)) {
current = current->leftChild;
continue;
} else if (is_operator(current->rightChild->data)) {
current = current->rightChild;
continue;
} else {
current = current->parent->rightChild; // +
continue;
}
}
} else {
std::cout << "Error: only nodes who hold operators "<< "can have children." << std::endl;
return;
}
}
}
}

Отличия от предыдущей версии: добавление else утверждение в основном if внутри while это прерывает цикл в случае, если все конечные узлы являются числами (это означает, что они не могут иметь детей)^[1] и замена (как указано // +) предыдущего с назначением, которое помогает курсор ближе к родительскому узлу текущего.

Кроме того, также конструктор Node() пройти модификацию: каждый раз, когда создается новый узел, он связывается со своим родителем, передавая указатель родителя и второй аргумент.

Просто последнее. Порядок вставки элементов сверху вниз слева направо. Например, следуя первому дереву в вопросе, элементы должны быть вставлены в следующем порядке: *, +, *, 7, 121, 12, +, 9, 3,

^[1] предложенный Dr_Sam.

1

Источник

Accepted Answer

Я думаю, что у меня есть две проблемы.

(А)

Предположим, вы пытаетесь ввести дерево, которое находится справа на вашей картинке. Вы уже вошли в * на вершине и тому * а также + ниже. Вы также вошли в 7 и 121,

Теперь вы хотите ввести 12 и вот где ваш код не работает.

Корень — это оператор, и оба потомка не равны нулю, поэтому вы переходите к предложению «else» и рассматриваете левого потомка в качестве текущего местоположения. НО эта часть уже заполнена! Так что вы не сможете ничего там вставить.

Однако не уверен, что это единственная ошибка, поскольку вы должны увидеть свое сообщение об ошибке.

(В)

Я думаю, что если вы начинаете с номера вашего дерева (не с оператора), вы вводите бесконечный цикл при попытке вставить лист, и вы не видите сообщение отображается (первое, если всегда не удается)

1