二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。
而线索二叉树利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息
结点信息如下
计算
安全
数据库
网络和加速
企业服务
enum PointerTag{ THREAD, LINK };
template<class T>
struct BinaryTreeNodeThd
{
T _data; //数据
BinaryTreeNodeThd<T>* _left; //左孩子
BinaryTreeNodeThd<T>* _right; //右孩子
PointerTag _leftTag; //左孩子线索标志
PointerTag _rightTag; //右孩子线索标志
};其前序结构如下
其中序结构如下
程序实现：
#include<iostream>
using namespace std;
enum PointerTag{ THREAD, LINK };
template<class T>
struct BinaryTreeNodeThd
{
T _data; //数据
BinaryTreeNodeThd<T>* _left; //左孩子
BinaryTreeNodeThd<T>* _right; //右孩子
PointerTag _leftTag; //左孩子线索标志
PointerTag _rightTag; //右孩子线索标志
BinaryTreeNodeThd(const T& x)
:_data(x)
, _left(NULL)
, _right(NULL)
, _leftTag(LINK)
, _rightTag(LINK)
{}
};
template<class T>
class BinaryTreeThd
{
typedef BinaryTreeNodeThd<T> Node;
public:
BinaryTreeThd()
:_root(NULL)
{}
BinaryTreeThd(const T*a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreateTree(a, size, index, invalid);
}
void InOrderThreading()//中序线索化
{
Node*prev = NULL;
_InOrderThreading(_root, prev);
}
void PrevOderThreading()//前序线索化
{
Node*prev = NULL;
_PrevOderThreading(_root, prev);
}
void InOrderThd()//中序遍历
{
_InOrderThd(_root);
}
void PrevOrderThd()//前序遍历
{
_PrevOrderThd(_root);
}
protected:
Node* _CreateTree(const T*a, size_t size, size_t& index, const T& invalid)
{
Node* _root = NULL;
if (index < size&&a[index] != invalid)
{
_root = new Node(a[index]);
_root->_left = _CreateTree(a, size, ++index, invalid);
_root->_right = _CreateTree(a, size, ++index, invalid);
}
return _root;
}
void _PrevOderThreading(Node* root, Node*& prev)//前序线索化
{
if (root == NULL)
return;
if (root->_left == NULL)
{
root->_leftTag = THREAD;
root->_left = prev;
}
if (prev&&prev->_right == NULL)
{
prev->_rightTag = THREAD;
prev->_right = root;
}
prev = root;
if (root->_leftTag == LINK)//递归
{
_PrevOderThreading(root->_left,prev);//线索化左子树
}
if (root->_rightTag == LINK)
{
_PrevOderThreading(root->_right,prev);//线索化右子树
}
}
void _PrevOrderThd(Node* root)
{
Node*cur = root;
while (cur)
{
while (cur->_leftTag == LINK)
{
cout << cur->_data << " ";
cur = cur->_left;
}
cout << cur->_data << " ";
cur = cur->_right;
}
}
/*方法二
void _PrevOrderThd(Node* root)
{
Node*cur = root;
while (cur)
{
while (cur->_leftTag==LINK)
{
cout << cur->_data << " ";
cur = cur->_left;
}
cout << cur->_data << " ";
while (cur->_rightTag == THREAD)
{
cur = cur->_right;
cout << cur->_data << " ";
}
if (cur->_leftTag == LINK)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
}*/
void _InOrderThreading(Node* _root, Node* &prev)//中序线索化
{
if (_root == NULL)
{
return;
}
if (_root->_leftTag==LINK)
_InOrderThreading(_root->_left,prev);
//线索化
if (_root->_left == NULL)//左孩子为空
{
_root->_leftTag = THREAD;
_root->_left = prev;
}
if (prev != NULL&&prev->_right == NULL)//前驱的右孩子为空
{
prev->_rightTag = THREAD;
prev->_right = _root;
}
prev = _root;
if (_root->_rightTag==LINK)//线索化右孩子
_InOrderThreading(_root->_right,prev);
}
void _InOrderThd(Node* _root) //中序遍历
{
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;
}
protected:
Node* _root;
};测试
int main()
{
int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTreeThd<int> t1(a1, 10, '#');
cout << endl << "中序遍历：";
t1.InOrderThreading();
t1.InOrderThd();
cout << "前序遍历" << endl;
BinaryTreeThd<int>t2(a1, 10, '#');
t2.PrevOderThreading();
t2.PrevOrderThd();
getchar();
return 0;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
