Avez-vous remarqué que votre méthode insert() ne gère pas le cas de "collision de clé" (en raison de la branche else manquante pour la dernière if). Cela peut être utilisé pour détecter si une clé doit être insérée dans l'arborescence. Comme il est, ces insertions dupliquées sont simplement ignorées (ce qui est à mon humble avis pas le pire comportement possible).
Dans mon exemple ci-dessous, j'ai opté pour une option différente: soit insert() retourne une valeur booléenne qui rapporte le succès de l'insertion.
Malheureusement, vous n'avez pas fourni de MCVE.
Ainsi, j'ai rempli les lacunes avec le code propre où (pour ma joie personnelle) j'ai impliqué des modèles. J'espère que cela n'entraînera pas trop de confusion.
Cependant, après avoir joué avec vos données d'échantillon, je suis arrivé à la conclusion que votre code ne peut probablement pas le bon –, ce que vous attendiez. Finalement, vous avez une fausse attente. Ou, vous avez résolu correctement le faux problème. J'ai relu votre question plusieurs fois mais je n'ai pas eu d'idée claire à ce sujet ...
J'utilisé votre dernier fichier exemple en entrée (pour construire l'arbre de recherche binaire) et que ma pré-commande de sortie de l'application et afinde:
La sortie inorder fournit une sortie triées selon l'ordre défini de l'arbre – dans ce cas, l'ordre lexicographique des séquences Morse (où - précède . en raison de leurs valeurs ASCII respectifs).
Mais cela n'imprime pas non plus l'arborescence dans l'ordre alphabétique pour le code Morse en pré-commande.
Hmmm. Si vous vous attendiez à un ordre alphabétique, voulez-vous dire un ordre qui considère les caractères alphanumériques (auxquels correspondent les codes Morse)? Si tel est le cas, cela peut difficilement être fait par un tel arbre (car je ne vois pas comment un ordre possible de codes Morse correspond à un ordre possible d'alpha-numériques). C'est à dire. pour obtenir des "codes morse triés par les alpha-numériques associés", la méthode évidente (et à mon humble avis seulement) consiste à construire un arbre pour la cartographie inverse. Vous pouvez facilement créer un autre arbre (par exemple à partir du premier) où les valeurs alphanumériques affectées sont utilisées comme clés à la place. (En fait, vous avez déjà fait d'abord un arbre de recherche binaire pour les caractères alphanumériques.)
Cela me laisse perplexe. Peut-être, je raté quelque chose et n'a pas obtenu votre problème réel ...
Cependant, au-dessous est le résultat de mon violon:
// forward template declaration:
template <typename KEY, typename VALUE, typename COMP>
class BSTreeT;
/* provides a class template for a node in a binary search tree.
*
* KEY ... C++ type of the key values of nodes
* VALUE ... C++ type of the other values of nodes
*/
template <typename KEY, typename VALUE>
class BSTreeNodeT {
/* This friend shall ensure that the corresponding
* BSTreeT template class may access private _pLeft and _pRight.
*/
template <typename KEY_, typename VALUE_, typename COMP_>
friend class BSTreeT;
public:
// the key value of node (used to define an order)
const KEY key;
// other values of node
VALUE value;
private:
// pointers to left and right child nodes
BSTreeNodeT *_pLeft, *_pRight;
public:
// constructor.
BSTreeNodeT(const KEY &key, const VALUE &value):
key(key), value(value), _pLeft(nullptr), _pRight(nullptr)
{ }
// destructor.
~BSTreeNodeT() { delete _pLeft; delete _pRight; }
// disabled:
BSTreeNodeT(const BSTreeNodeT&) = delete;
BSTreeNodeT& operator=(const BSTreeNodeT&) = delete;
public:
// returns pointer to left child node (or nullptr if there is none).
const BSTreeNodeT* getLeft() const { return _pLeft; }
// returns pointer to right child node (or nullptr if there is none).
const BSTreeNodeT* getRight() const { return _pRight; }
};
/* provides a less functor which simply wraps operator < for a certain
* type
*
* VALUE ... C++ type of value to less-compare
*
* Note:
* This is actually, what std::less provides.
* I involved this functor for illustration.
*/
template <typename VALUE>
struct lessFunc {
bool operator()(const VALUE &value1, const VALUE &value2) const
{
return value1 < value2;
}
};
/* provides a class template for a binary search tree.
*
* KEY ... C++ type of the key values of nodes
* VALUE ... C++ type of the other values of nodes
* COMP ... C++ type of the less comparator
* to define an order of tree nodes
*/
template <typename KEY, typename VALUE, typename COMP = lessFunc<KEY> >
class BSTreeT {
public:
const COMP ∁
private:
BSTreeNodeT<KEY, VALUE> *_pRoot;
public:
/* constructor.
*
* comp ... a less comparator to define order of nodes
*/
explicit BSTreeT(const COMP &comp = COMP()):
comp(comp), _pRoot(nullptr)
{ }
// destructor.
~BSTreeT() { delete _pRoot; }
// disabled:
BSTreeT(const BSTreeT&) = delete;
BSTreeT& operator=(const BSTreeT&) = delete;
public:
/* inserts a node.
*
* key ... the key value of node
* value ... the other value of node
* return: true ... key/value inserted
* false ... Error! Possible reasons:
* - duplicated key
* - allocation of node failed.
*/
bool insert(const KEY &key, const VALUE &value)
{
return insert(_pRoot, key, value);
}
/* provides a functor-like type which is applied to every node
* in traverse().
*
* If an instance of this class is provided the traverse() does nothing
* else than the pure traversal.
*/
struct Apply {
// pre-order access to node
virtual void preNode(BSTreeNodeT<KEY, VALUE> &node) { }
// in-order access to node
virtual void inNode(BSTreeNodeT<KEY, VALUE> &node) { }
// post-order access to node
virtual void postNode(BSTreeNodeT<KEY, VALUE> &node) { }
};
/* traverses the tree and applies the provided object to every node.
*
* apply ... the action object applied to every node
*/
void traverse(Apply &apply)
{
if (_pRoot) traverse(_pRoot, apply);
}
private:
// inserts a node.
bool insert(
BSTreeNodeT<KEY, VALUE> *&pTree, const KEY &key, const VALUE &value)
{ /* Every if-branch ends with return.
* Thus, no explict else is needed.
*/
if (!pTree) { /* (!pTree) ... (pTree == nullptr) */
return !!(pTree = new BSTreeNodeT<KEY, VALUE>(key, value));
}
if (comp(key, pTree->key)) return insert(pTree->_pLeft, key, value);
if (comp(pTree->key, key)) return insert(pTree->_pRight, key, value);
return false;
}
// traverses the tree.
void traverse(BSTreeNodeT<KEY, VALUE> *pTree, Apply &apply)
{
apply.preNode(*pTree);
if (pTree->_pLeft) traverse(pTree->_pLeft, apply);
apply.inNode(*pTree);
if (pTree->_pRight) traverse(pTree->_pRight, apply);
apply.postNode(*pTree);
}
};
// sample code:
#include <ctype.h>
#include <iostream>
#include <string>
using namespace std;
// template instances (for convenience)
typedef BSTreeNodeT<string, string> BSTNode;
typedef BSTreeT<string, string> BST;
/* a helper function to split a string into tow at the first occurence of
* (a sequence of) whitespaces.
*
* line ... input
* first ... returns first sub-string (might become empty)
* second ... returns second sub-string (might become empty)
*/
void split(const string &line, string &first, string &second)
{
size_t i0 = 0, n = line.length(), i;
for (i = i0; i < n && !isspace(line[i]); ++i);
first = line.substr(i0, i - i0);
for (i0 = i; i0 < n && isspace(line[i0]); ++i0);
for (i = i0; i < n && !isspace(line[i]); ++i);
second = line.substr(i0, i - i0);
}
/* a derived tree-traversal action
* for graphical (i.e. ASCII-art) output of tree
*/
struct PrintGraph: public BST::Apply {
string indent;
PrintGraph(): indent(" ") { }
virtual void preNode(BSTNode &node)
{
indent.pop_back(); char c = indent.back(); indent.pop_back();
cout << indent << "+-"
<< (node.getLeft() || node.getRight() ? '+' : '-')
<< "- ["
<< node.key << ": " << node.value
<< ']' << endl;
indent += c; indent += ' ';
indent += node.getRight() ? "| " : " ";
}
virtual void inNode(BSTNode &node)
{
indent.pop_back(); indent.pop_back();
indent += " ";
}
virtual void postNode(BSTNode &node)
{
indent.pop_back(); indent.pop_back();
}
};
/* a derived tree-traversal action
* for pre-order output of nodes
*/
struct PrintPreOrder: public BST::Apply {
virtual void preNode(BSTNode &node)
{
cout << node.key << ": " << node.value << endl;
}
};
/* a derived tree-traversal action
* for in-order output of nodes
*/
struct PrintInOrder: public BST::Apply {
virtual void inNode(BSTNode &node)
{
cout << node.key << ": " << node.value << endl;
}
};
/* a derived tree-traversal action
* to fill another tree with key and value of nodes swapped
*/
struct FillRevTree: public BST::Apply {
BST &tree; // destination tree to fill
FillRevTree(BST &tree): tree(tree) { }
virtual void preNode(BSTNode &node)
{
tree.insert(node.value, node.key);
}
};
// main function
int main()
{
BST tree;
// read tree from input
cout << "Read contents from input:" << endl;
for (string line; getline(cin, line);) {
string key, value; split(line, key, value);
if (!tree.insert(key, value)) {
cerr << "Error! Couldn't store the line:" << endl
<< "->" << line << endl;
}
}
cout << "End of input." << endl
<< endl;
// show tree
cout << "The tree:" << endl;
{ PrintGraph print; tree.traverse(print); }
cout << endl;
// print tree by pre-order traversal
cout << "Pre-Order Output:" << endl;
{ PrintPreOrder print; tree.traverse(print); }
cout << endl;
// print tree by in-order traversal
cout << "In-Order Output:" << endl;
{ PrintInOrder print; tree.traverse(print); }
cout << endl;
// re-built tree with keys and values swapped
BST treeRev;
{ FillRevTree fill(treeRev); tree.traverse(fill); }
// show reverse tree
cout << "The Rev. Tree:" << endl;
{ PrintGraph print; treeRev.traverse(print); }
cout << endl;
// print tree by in-order traversal
cout << "In-Order Output of Rev. Tree:" << endl;
{ PrintInOrder print; treeRev.traverse(print); }
cout << endl;
// done
cout << "That's it." << endl;
return 0;
}
Compilez et exécutez:
$ g++ -std=c++11 -o binary-search-tree binary-search-tree.cc
$ ./binary-search-tree <morse.txt
Read contents from input:
End of input.
The tree:
+-+- [-..: D]
+-+- [--.-: Q]
| +-+- [-----: 0]
| | +-+- [--: M]
| | | +--- [-: T]
| | | +--- [---: O]
| | +-+- [---..: 8]
| | +--- [----.: 9]
| | +--- [--.: G]
| +-+- [-.: N]
| +-+- [--..--: ,]
| | +--- [--..: Z]
| | +--- [--...: 7]
| +-+- [-.--: Y]
| +--- [-.-: K]
| +--- [-.-.: C]
+-+- [..: I]
+-+- [.----: 1]
| +-+- [.: E]
| | +-+- [-...: B]
| | | +--- [-..-: X]
| | | +--- [-....: 6]
| | +-+- [.--: W]
| | +--- [.-: A]
| | +--- [.---: J]
| +-+- [.-.-.-: .]
| +-+- [.--.: P]
| | +--- [.-.: R]
| +--- [.-..: L]
+-+- [...--: 3]
+-+- [..--..: ?]
| +-+- [..---: 2]
| | +--- [..-: U]
| +-+- [...: S]
| +--- [..-.: F]
| +--- [...-: V]
+-+- [....-: 4]
+--- [....: H]
+--- [.....: 5]
Pre-Order Output:
-..: D
--.-: Q
-----: 0
--: M
-: T
---: O
---..: 8
----.: 9
--.: G
-.: N
--..--: ,
--..: Z
--...: 7
-.--: Y
-.-: K
-.-.: C
..: I
.----: 1
.: E
-...: B
-..-: X
-....: 6
.--: W
.-: A
.---: J
.-.-.-: .
.--.: P
.-.: R
.-..: L
...--: 3
..--..: ?
..---: 2
..-: U
...: S
..-.: F
...-: V
....-: 4
....: H
.....: 5
In-Order Output:
-: T
--: M
---: O
-----: 0
----.: 9
---..: 8
--.: G
--.-: Q
--..: Z
--..--: ,
--...: 7
-.: N
-.-: K
-.--: Y
-.-.: C
-..: D
-..-: X
-...: B
-....: 6
.: E
.-: A
.--: W
.---: J
.----: 1
.--.: P
.-.: R
.-.-.-: .
.-..: L
..: I
..-: U
..---: 2
..--..: ?
..-.: F
...: S
...-: V
...--: 3
....: H
....-: 4
.....: 5
The Rev. Tree:
+-+- [D: -..]
+-+- [0: -----]
| +-+- [,: --..--]
| | +--- [.: .-.-.-]
| +-+- [8: ---..]
| +-+- [7: --...]
| | +-+- [1: .----]
| | +-+- [6: -....]
| | +-+- [3: ...--]
| | +--- [2: ..---]
| | +-+- [4: ....-]
| | +--- [5: .....]
| +-+- [9: ----.]
| +-+- [C: -.-.]
| +-+- [B: -...]
| +-+- [A: .-]
| +--- [?: ..--..]
+-+- [Q: --.-]
+-+- [M: --]
| +-+- [G: --.]
| | +-+- [E: .]
| | | +--- [F: ..-.]
| | +-+- [K: -.-]
| | +-+- [I: ..]
| | | +--- [H: ....]
| | | +--- [J: .---]
| | +--- [L: .-..]
| +-+- [O: ---]
| +--- [N: -.]
| +--- [P: .--.]
+-+- [T: -]
+-+- [R: .-.]
| +--- [S: ...]
+-+- [Z: --..]
+-+- [Y: -.--]
+-+- [X: -..-]
+-+- [W: .--]
+-+- [U: ..-]
+--- [V: ...-]
In-Order Output of Rev. Tree:
,: --..--
.: .-.-.-
0: -----
1: .----
2: ..---
3: ...--
4: ....-
5: .....
6: -....
7: --...
8: ---..
9: ----.
?: ..--..
A: .-
B: -...
C: -.-.
D: -..
E: .
F: ..-.
G: --.
H: ....
I: ..
J: .---
K: -.-
L: .-..
M: --
N: -.
O: ---
P: .--.
Q: --.-
R: .-.
S: ...
T: -
U: ..-
V: ...-
W: .--
X: -..-
Y: -.--
Z: --..
That's it.
$
Remarque :
Je viens de reconnaître que l'arbre "inversé" n'est plus bien équilibré. Ainsi, la complexité temporelle optimale du pire cas de O (ld (n)) ne peut pas être atteinte.