Сложность настройки резьбового BST в C ++ ⇐ C++

[Anonymous]

У меня проблемы с реализацией бинарного дерева поиска с резьбой в C ++. У меня полностью реализовано неточковое дерево (см. Ниже код). То, с чем мне трудно установить потоки, указывать на правильный родительский узел (без явного родительского указателя). (У меня есть две функции - print () и printinorder (), которые отлично работают для нетребованного двоичного дерева, которое мне нужно работать для резьбового.) Я не могу понять, как правильно установить потоки. Я посмотрел на бесчисленные сайты и попробовал, что кажется все, кроме правильного ответа. Я пытался использовать массив, чтобы отслеживать предыдущие узлы, посещаемые и использовать его, чтобы определить правильные левые и правые потоки, но просто не смог заставить его работать правильно. Мне нужны функции конструктора и setleft/setright в классе BSTNODE, чтобы правильно назначить потоки при применимости и установить соответствующий isleft/raverThreated, а затем функции PrintheLp и PrintInOder в классе BST для использования, не соответствуют ли узлам, чтобы пройти дерево.
. Печать и распечатать, если это вообще возможно. Я стремлюсь на какое -то время, который покрывает все дерево. Я хочу, чтобы это полагалось только на текущий узел и узлы, на которые он указывает.using namespace std;

#include
#include // want to avoid needing this
#include

template
class BinNode {};

template
class BSTNode : public BinNode {
public:
E it;
BSTNode* lp;
BSTNode* rp;
bool isLpChildPointer;
bool isRpChildPointer;
bool isLeftThreaded;
bool isRightThreaded;
Key k;
BSTNode() { lp = rp = NULL; }
BSTNode(Key K, E e, BSTNode* l, BSTNode* r) {
k = K;
it = e;
lp = l;
rp = r;
isLpChildPointer = false;
isRpChildPointer = false;
isLeftThreaded = true;
isRightThreaded = true;
}
void setLeft(BinNode* b) {
lp = (BSTNode*)b;
isLpChildPointer = true;
isLeftThreaded = false;
}

void setRight(BinNode* b) {
rp = (BSTNode*)b;
isRpChildPointer = true;
isRightThreaded = false;
}
};

template
class BST {
public:
BSTNode* root;
int nodecount;

BSTNode* inserthelp(BSTNode*, const Key&, const E&,
BSTNode*[], int, int);
void printhelp(BSTNode* root, int level) const {
if (root == NULL) return;
printhelp(root->lp, level + 1);
for (int i = 0; i < level; i++) cout lp;
}
current = stack.top();
cout it rp;
}
}

void insert(const Key& k, const E& e) {
root = inserthelp(k, e, root);
nodecount++;
}

BSTNode* inserthelp(const Key& k, const E& e, BSTNode* node) {
if (node == nullptr) {
return new BSTNode(k, e, NULL, NULL); // what to put here instead of NULL.
// and how to keep track of what higher level nodes this new node should thread to.
} else {
if (k < node->k) {
node->setLeft(inserthelp(k, e, node->lp));
} else {
node->setRight(inserthelp(k, e, node->rp));
}
return node;
}
}
void print() const { printhelp(root, 0); }
};

int main() {
BST tree;

tree.insert(77, "seventy-seven");
tree.insert(70, "seventy");
tree.insert(75, "seventy-five");
tree.insert(66, "sixty-six");
// other inserts...
tree.insert(83, "eighty-three");
tree.insert(87, "eighty-seven");
tree.insert(65, "sixty-five");

tree.print();
tree.printInOrder();
}
< /code>
Опять же, приведенный выше код работает нормально для нетребованного дерева - никаких проблем - не делает именно то, что я хочу, чтобы оно делало. Но мне нужно, чтобы он работал на резьбое дерево. Я работал над этой проблемой большей части четырех или пяти часов назад, а потом просто не мог больше смотреть на него.

Подробнее здесь: https://stackoverflow.com/questions/795 ... d-bst-in-c