线索化二叉树：
创新互联是一家专业提供息烽企业网站建设,专注与成都做网站、成都网站制作、成都外贸网站建设、H5场景定制、小程序制作等业务。10年已为息烽众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。
| LChild（左孩子） | Ltag（左线索标志） | Data | Rtag（右线索标志） | RChild（右孩子） |
中序（左根右）：
前序（根左右）：
注意：因为++index返回对象 index++返回临时变量 传引用时只能用++index。
前序、中序的线索化及遍历具体实现如下：
#pragma once
enum
{
THREAD,
LINK,
};
typedef int PointerTag;
template
struct BinaryTreeNodeThd
{
T _data; //数据
BinaryTreeNodeThd* _left; //左孩子
BinaryTreeNodeThd* _right; //右孩子
PointerTag _leftTag; //左孩子线索化标志
PointerTag _rightTag; //右孩子线索化标志
BinaryTreeNodeThd(const T& x)
:_data(x)
, _left(NULL)
, _right(NULL)
, _leftTag(LINK)
, _rightTag(LINK)
{}
};
template
class BinaryTreeThd
{
typedef BinaryTreeNodeThd Node;
public:
//构造
BinaryTreeThd()
:_root(NULL)
{}
// a--树的节点前序遍历的数组 size--数组中元素个数 invaild--无效值即节点为空
BinaryTreeThd(const T* a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreateTree(a, size, invalid, index);
}
//析构
~BinaryTreeThd()
{
_Destory(_root);
_root = NULL;
}
//拷贝
BinaryTreeThd(const BinaryTreeThd& t)
{
_root = _Copy(t._root);
}
//赋值重载(传统)
//BinaryTreeThd& operator=(const BinaryTreeThd& t)
//{
// if (this != &t)
// {
// Node* tmp = _Copy(t._root);
// _Destory(_root);
// _root = tmp;
// }
// return *this;
//}
//赋值重载(现代)
BinaryTreeThd& operator=(BinaryTreeThd t)
{
swap(_root, t._root);
return *this;
}
T& operator->()
{
return _root;
}
public:
//线索化
void PrevOrderThread() //前序
{
Node* prev = NULL;
return _PrevOrderThread(_root, prev);
}
void InOrderThread() //中序
{
Node* prev = NULL;
return _InOrderThread(_root, prev);
}
void PostOrderThread() //后序
{
Node* prev = NULL;
return _PostOrderThread(_root, prev);
}
//线索化遍历
void PrevOrderThd() //前序遍历（法一）
{
if(_root == NULL)
return;
Node* cur = _root;
while (cur)
{
//找最左节点
while (cur->_leftTag == LINK)
{
cout << cur->_data << " ";
cur = cur->_left;
}
cout << cur->_data << " ";
//访问右子树
cur = cur->_right;
}
cout << endl;
}
void PrevOrderThd_O() //前序遍历（法二）
{
if(_root == NULL)
return;
Node* cur = _root;
while (cur)
{
cout << cur->_data << " ";
//找最左节点
if (cur->_leftTag == LINK)
{
cur = cur->_left;
}
else //访问右子树
{
cur = cur->_right;
}
}
cout << endl;
}
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 PostOrderThd(); //后序遍历
protected:
//注意 此处index要用引用传参
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
{
Node* root = NULL;
if ((index < size) && (a[index] != invalid))
{
root = new Node(a[index]);
//注意下面只能用++index。因为++index返回对象index++返回临时变量 此处传的是引用
root->_left = _CreateTree(a, size, invalid, ++index);
root->_right = _CreateTree(a, size, invalid, ++index);
}
return root;
}
void _Destory(Node* root)
{
if (root == NULL)
return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
Node* _Copy(Node* root)
{
if (root == NULL)
return NULL;
NOde* newRoot = new Node(root->_data);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}
//前序线索化
void _PrevOrderThread(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;
if (cur->_leftTag == LINK) //线索化左子树
_PrevOrderThread(cur->_left, prev);
if (cur->_rightTag == LINK) //线索化右子树
_PrevOrderThread(cur->_right, prev);
}
//中序线索化
void _InOrderThread(Node* cur, Node* &prev)
{
if (cur == NULL)
return;
_InOrderThread(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;
_InOrderThread(cur->_right, prev);
}
//后序线索化
void _PostThread(Node* cur, Node* &prev);
private:
Node* _root;
}; 测试代码：
void TestInOrder()
{
int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
size_t size = sizeof(a1) / sizeof(int);
BinaryTreeThd t1 = BinaryTreeThd(a1, size, '#');
t1.InOrderThread();
cout << "中序后：";
t1.InOrderThd();
}
void TestPrev()
{
int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#',5, 6 };
size_t size = sizeof(a1) / sizeof(int);
BinaryTreeThd t1 = BinaryTreeThd(a1, size, '#');
t1.PrevOrderThread();
cout << "前序后(1)：";
t1.PrevOrderThd();
cout << "前序后(2)：";
t1.PrevOrderThd_O();
} 另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。