前序线索化:
计算
安全
数据库
网络和加速
企业服务
void _PrevOrderThreading(Node *cur, Node *& prev)
{
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;
_PrevOrderThreading(cur->_left, prev);
_PrevOrderThreading(cur->right, prev);
}前序遍历：
void PrevOrderThd()
{
Node *cur = _root;
while(cur)
{
while(cur->_leftTag == LINK)
{
cout << cur->_data << " ";
cur = cur->_left;
}
cout << cur->_data << " ";
cur = cur->right;
//
// while(cur->_rightTag == THREAD)
// {
// cur = cur->_right;
// cout << cur->_data << " ";
// }
// if(cur->_leftTag == LINK)
// {
// cur = cur->_left;
// }
// else
// {
// cur = cur->_right;
// }
}
}中序线索化：
void _InOrderThreading(Node *cur, Node *& prev)
{
if(cur == NULL)
{
return;
}
_InOrderThreading(cur->_left, prev);
//线索化
if(cur->_left == NULL)
{
cur->_leftTag = THREAD;
cur->_left = prev;
}
if(prev && prev->_right == NULL)
{
prev->_rightTag = THREAD;
prev->_right = cur;
}
prev = cur;
_InOrderThreading(cur->_right, 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;
}
}后序线索化：
void _PostOrderThreading(Node *root, Node *&prev)
{
if (root == NULL)
{
return;
}
_PostOrderThreading(root->_LChild, prev);
_PostOrderThreading(root->_RChild, prev);
if (root->_LChild == NULL)
{
root->_LTag = THREAD;
root->_LChild = prev;
}
if (prev->_RChild == NULL)
{
prev->_RTag = THREAD;
prev->_RChild = root;
}
prev = root;
}后序遍历：
采用三叉链 或写一个查找根节点的方法
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
