二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。
为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。
代码结构如下：
计算
安全
数据库
网络和加速
企业服务
enum PointerTag
{
THREAD,
LINK
};
template<class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
PointerTag _leftTag;//左孩子线索标志
PointerTag _rightTag;//右孩子线索标志
BinaryTreeNode(const T& d)
:_data(d)
, _left(NULL)
, _right(NULL)
{
_leftTag = LINK;
_rightTag = LINK;
}
};
代码实现如下：
void InOrderThreading() //中序线索化
{
Node* prev = NULL;
_InOrderThreading(_root, prev);
}
void PrevOrderThreading() //前序线索化
{
Node* prev = NULL;
_PrevOrderThreading(_root, prev);
}
//void PostOrderThreading() //后序线索化
//{
// Node* prev = NULL;
// _PostOrderThreading(_root, prev);
//}
void InOrderThd() //中序遍历
{
Node* cur = _root;
while (cur)
{
while (cur->_leftTag == LINK)
{
cur = cur->_left;
}
cout << cur->_data << " ";
while (cur->_rightTag == THREAD)
{
cur = cur->_right;
cout << cur->_data << " ";
}
cur = cur->_right;
}
cout << endl;
}
void PrevOrderThd() //前序遍历
{
Node* cur = _root;
while (cur)
{
cout << cur->_data << " ";
while (cur->_leftTag == LINK)
{
cur = cur->_left;
cout << cur->_data << " ";
}
cur = cur->_right;
}
cout << endl;
}
void _InOrderThreading(Node* root, Node*& prev) //
{
if (root == NULL)
{
return;
}
_InOrderThreading(root->_left, prev);
if (root->_left == NULL)
{
root->_leftTag = THREAD;
root->_left = prev;
}
if (prev&&(prev->_right == NULL))
{
prev->_rightTag = THREAD;
prev->_right = root;
}
prev = root;
_InOrderThreading(root->_right, prev);
}
void _PrevOrderThreading(Node* root, Node*& prev)
{
Node* cur = root;
if (cur == NULL)
{
return;
}
if (cur->_left == NULL)
{
cur->_leftTag = THREAD;
cur->_left = prev;
}
if (prev&&prev->_right == NULL)
{
prev->_rightTag = THREAD;
prev->_right = cur;
}
prev = cur;
if (cur->_leftTag == LINK)
{
_PrevOrderThreading(cur->_left, prev);
}
if (cur->_rightTag == LINK)
{
_PrevOrderThreading(cur->_right, prev);
}
}因为后序比较复杂，所以露珠不是很有能力写出来。以后露珠会好好提高自己，然后把后序实现了哈哈哈哈
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
