Schwierigkeiten beim Einrichten von Gewinde BST in C ++ ⇐ C++

[Anonymous]

Ich habe Probleme, einen Thread -Binär -Suchbaum in C ++ zu implementieren. Ich habe einen nicht thread-Baum vollständig implementiert (siehe unten Code). Ich habe Schwierigkeiten mit der Einstellung der Threads, um auf den richtigen übergeordneten Knoten zu verweisen (ohne einen expliziten übergeordneten Zeiger). (Ich habe zwei Funktionen - print () und printInorder (), die beide für einen nicht throchenfarbenen Binärbaum funktionieren, den ich für eine Gewinde arbeiten muss.) < /P>
Mein Problem liegt in der Funktion Inserthelp (). Ich kann nicht herausfinden, wie ich die Threads richtig einstellen kann. Ich habe mir unzählige Websites angesehen und versucht, was sich wie alles außer der richtigen Antwort anfühlt. Ich habe versucht, ein Array zu verwenden, um frühere besuchte Knoten im Auge zu behalten und diese zu verwenden, um die richtigen linken und rechten Threads zu bestimmen, konnte aber einfach nicht richtig funktionieren. Ich benötige die Konstruktor- und Setleft/SetRight -Funktionen in der Bstnode -Klasse, um die Threads zuzuweisen, wenn zutreffend Isleft/Rechtsbereiter entsprechend einstellen, und dann die Printhelp- und Printinorderfunktionen der Klasse BST, um zu verwenden, ob die Knoten mit einem Gewinde den BR/> < -P. in Printinorder und gedruckt, wenn möglich. Ich strebe eine Weile Schleife, die den gesamten Baum abdeckt. Ich möchte, dass sich das nur auf den aktuellen Knoten und die Knoten, auf die er verweistusing 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>
Nochmals funktioniert der obige Code gut für einen Nicht -Thread -Baum - überhaupt keine Probleme - genau das tut, was ich tun möchte. Aber ich brauche es, um für einen Fadenbaum zu arbeiten. Ich habe für den größten Teil von vier oder fünf Stunden zuvor an diesem Problem gearbeitet und konnte es mir dann einfach nicht mehr ansehen.