Предварительный заказ по азбуке Морзе

Question

Предварительный заказ по азбуке Морзе

В C ++ я работаю над двумя деревьями, 1 алфавитный a-z с числами и символами 0-9,. ?

Другое дерево является эквивалентом этих символов в азбуке Морзе. У меня должны быть разные деревья в текстовых файлах, которые уже должны быть в правильном порядке для вставки. В моем обычном алфавите я разработал свой сбалансированный текстовый файл для обхода предварительного заказа выглядит

P
H
D
B
A
C
F
E
G
L
J
I
K
N
M
O
2
X
T
R
Q
S
V
U
W
0
Y
Z
1
9
5
4
3
7
6
8
,
.
?

Этот текстовый файл распечатывает предварительный заказ

,
.
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

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

-    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

применяя ту же формулу для дерева (так что она имеет ту же последовательность, что и алфавит выше, мой текстовый файл выглядит так

-..  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

Но это также не распечатывает дерево в алфавитном порядке для азбуки Морзе для предварительного заказа.

Вот как я вставляю в дерево

void BST::insert(BSTNode *&pTree, string morse)
{
if (pTree == NULL)
{
BSTNode *pMem = new BSTNode(morse);
pTree = pMem;
}
else if (morse < (pTree)->getMorse())
{
insert((pTree)->getLeft(), morse);
}
else if (morse > (pTree)->getMorse())
{
insert((pTree)->getRight(), morse);
}
}

И вот как я распечатываю результаты

void BST::print(BSTNode *&pTree, string id)
{
if (pTree != nullptr)
{
//cout << pTree->getMorse() << endl; // processed
print(pTree->getLeft(), id);
cout << pTree->getMorse() << endl; // processed
print(pTree->getRight(), id);
}

}

(тот же код для алфавита, за исключением того, что он использует chars и getLetter (), но в остальном он идентичен)

Если я просто неправильно подхожу к этому, я могу использовать любую помощь в правильном направлении.

0

binary-search-tree c++morse-code

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Вы заметили, что ваш insert() метод не обрабатывает случай «столкновения клавиш» (из-за отсутствия else ветка для последнего if). Это может использоваться, чтобы определить, должен ли быть вставлен ключ, который уже находится в дереве. Как таковые, такие дублированные вставки просто игнорируются (что, IMHO, не самое плохое поведение).

В моем примере ниже я выбрал другой вариант: пусть insert() вернуть логическое значение, которое сообщает об успешности вставки.

К сожалению, вы не предоставили MCVE.

Таким образом, я заполнил пробелы собственным кодом, где (для моей личной радости) я задействовал шаблоны. Надеюсь, это не принесет слишком много путаницы.

Однако, поэкспериментировав с вашими примерами данных, я пришел к выводу, что ваш код, вероятно, работает правильно — может быть, не так, как вы ожидали. В конце концов, у вас ложное ожидание. Или вы правильно решили ложную проблему. Я перечитал ваш вопрос несколько раз, но не получил четкое представление об этом …

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

Вывод предзаказа соответствует вашему последнему файлу.
Вывод Inorder соответствует вашему 3-му файлу.

Выход по порядку обеспечивает отсортированный вывод по определенному порядку дерева — в этом случае лексикографический порядок последовательностей Морзе (где - предшествует . из-за их соответствующих значений ASCII).

Но это также не распечатывает дерево в алфавитном порядке для азбуки Морзе для предварительного заказа.

Хммм. Если вы ожидали алфавитный порядок, подразумеваете ли вы порядок, который учитывает буквенно-цифровые символы (с которыми сопоставляются азбуки Морзе)?

Если так, это вряд ли может быть сделано таким деревом (поскольку я не могу видеть, как возможный порядок азбуки Морзе соответствует возможному порядку буквенно-цифровых символов). То есть для достижения «азбуки Морзе, отсортированной по связанным буквенно-цифровым цифрам», очевидным (и только IMHO) способом является создание дерева для обратного отображения. Вы можете легко построить другое дерево (например, из первого), в котором вместо него используются назначенные буквенно-цифровые значения. (На самом деле, вы уже сделали сначала двоичное дерево поиска для буквенно-цифровых символов.)

Это оставляет меня как-то озадаченным. Может быть, я что-то пропустил и не понял твою настоящую проблему …

Тем не менее, ниже результат моего возни:

// 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 &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;
}

Скомпилируйте и запустите:

$ 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.

$

Замечания:

Я только что понял, что «перевернутое» дерево больше не сбалансировано.
Таким образом, оптимальная наихудшая временная сложность O (LD (п)) не может быть достигнуто.

0