通过摩尔斯电码BST进行前序遍历
Preorder traversal through Morse code BST
在 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() 但除此之外它是相同的）
如果我只是错误地处理了这个问题，我可以在正确的方向上使用任何帮助。
您是否注意到您的 insert() 方法无法处理 "key-collision" 的情况（由于最后一个 if 缺少 else 分支）。这可用于检测是否应插入已经在树中的密钥。事实上，这种重复的插入被简单地忽略了（恕我直言，这不是最糟糕的行为）。
在下面的示例中，我决定采用不同的选项：让 insert() return 一个报告插入成功的布尔值。
很遗憾，您没有提供 MCVE。
因此，我用自己的代码填补了空白（为了我个人的乐趣）我涉及模板。希望这不会带来太多混乱。
但是，在研究了您的示例数据之后，我得出的结论是您的代码可能正确——可能不是您所期望的。最终，你会有一个错误的期望。或者，你正确地解决了错误的问题。我多次重新阅读你的问题，但我对此没有清楚的想法...
我使用你的最后一个示例文件作为输入（构建二叉搜索树）并让我的应用程序输出前序和中序：
预购输出对应于您的最后一个文件。
顺序输出对应你的第三个文件。
inorder 输出根据树的定义顺序提供排序输出 - 在本例中为莫尔斯序列的字典顺序（其中 - 在 . 之前，因为它们各自的 ASCII 值） .
But this also does not print out the tree in alphabetical order for Morse code for preorder.
嗯。如果您希望按字母顺序排列，您的意思是考虑字母数字字符（摩尔斯电码映射到的字符）的顺序吗？
如果是这样，这样的树很难做到这一点（因为我看不出摩尔斯电码的可能顺序如何对应于字母数字的可能顺序）。 IE。要实现 "Morse codes sorted by the associated alpha-numerics"，最明显的（也是恕我直言）方法是为反向映射构建一棵树。您可以轻松地构建另一棵树（例如，从第一棵树开始），其中分配的字母数字值用作键。 （实际上，您已经首先为字母数字创建了一个二叉搜索树。）
这让我有些困惑。可能是，我错过了一些东西，没有得到你的实际问题......
然而，下面是我摆弄的结果：
// 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;
}
编译并运行:
$ 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.
$
注：
我刚刚意识到 "reversed" 树不再平衡了。
因此，无法实现 O(ld(n)) 的最佳最坏情况时间复杂度。
在 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() 但除此之外它是相同的）
如果我只是错误地处理了这个问题，我可以在正确的方向上使用任何帮助。
您是否注意到您的 insert() 方法无法处理 "key-collision" 的情况（由于最后一个 if 缺少 else 分支）。这可用于检测是否应插入已经在树中的密钥。事实上，这种重复的插入被简单地忽略了（恕我直言，这不是最糟糕的行为）。
在下面的示例中，我决定采用不同的选项：让 insert() return 一个报告插入成功的布尔值。
很遗憾，您没有提供 MCVE。
因此，我用自己的代码填补了空白（为了我个人的乐趣）我涉及模板。希望这不会带来太多混乱。
但是，在研究了您的示例数据之后，我得出的结论是您的代码可能正确——可能不是您所期望的。最终，你会有一个错误的期望。或者，你正确地解决了错误的问题。我多次重新阅读你的问题，但我对此没有清楚的想法...
我使用你的最后一个示例文件作为输入（构建二叉搜索树）并让我的应用程序输出前序和中序：
预购输出对应于您的最后一个文件。
顺序输出对应你的第三个文件。
inorder 输出根据树的定义顺序提供排序输出 - 在本例中为莫尔斯序列的字典顺序（其中 - 在 . 之前，因为它们各自的 ASCII 值） .
But this also does not print out the tree in alphabetical order for Morse code for preorder.
嗯。如果您希望按字母顺序排列，您的意思是考虑字母数字字符（摩尔斯电码映射到的字符）的顺序吗？
如果是这样，这样的树很难做到这一点（因为我看不出摩尔斯电码的可能顺序如何对应于字母数字的可能顺序）。 IE。要实现 "Morse codes sorted by the associated alpha-numerics"，最明显的（也是恕我直言）方法是为反向映射构建一棵树。您可以轻松地构建另一棵树（例如，从第一棵树开始），其中分配的字母数字值用作键。 （实际上，您已经首先为字母数字创建了一个二叉搜索树。）
这让我有些困惑。可能是，我错过了一些东西，没有得到你的实际问题......
然而，下面是我摆弄的结果：
// 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;
}
编译并运行:
$ 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.
$
注：
我刚刚意识到 "reversed" 树不再平衡了。 因此，无法实现 O(ld(n)) 的最佳最坏情况时间复杂度。