【数据结构】10.线索二叉树
一、线索二叉树的产生
采用先序、中序、后序三种方法遍历二叉树后都可以得到一个线性序列，序列上的每一个结点（除了第一个和最后一个）都有一个前驱和一个后继，但是，这个线性序列只是逻辑的概念，不是物理结构。
二叉链体现的是父子关系，不一定是结点在遍历序列中的前驱和后继。
在有n个结点的二叉链表中，有n+1个空指针 。那么能否利用这些空指针来存放前驱和后继结点的地址呢？然后可以像遍历链表一样方便的遍历二叉树序列呢？
这也就是线索二叉树产生的背景。线索二叉树可以解决部分的上述问题，加快在序列中查找前驱和后继节点的速度，但同样的也增加了在树中插入和删除节点的难度。
二、二叉树线索化
二叉树线索化是将二叉链表中的空指针改为指向前驱或后继结点。而前驱结点和后继结点只要在遍历时才能拿到，所有二叉树线索化分为先序线索二叉树、中序线索二叉树和后序线索二叉树。
如果当前节点没有左子树，那么该节点的左指针指向遍历序列中它的前驱结点。
如果当前节点没有右子树，那么该节点的右指针指向遍历序列中它的后继结点。
2.1 线索二叉树的定义
typedef int ThreadedBinaryTreeDataType;
typedef struct ThreadedBinaryTree
{
ThreadedBinaryTreeDataType _data;
struct ThreadedBinaryTree* _left;
struct ThreadedBinaryTree* _right;
int _LeftFlag, _RightFlag;//左右指针类型：0表示非线索指针，1表示线索指针
}TBT,*pTBT;
2.2 先序线索二叉树
将二叉树进行先序遍历得到的序列就是先序序列，我们需要将他们进行连接。很显然，我们需要找到每一个结点的后继结点。
如果当前结点的右指针存放的是线索，右指针指向的结点即为后续节点。
如果当前结点的右指针存放的是结点，取左子结点，如果左子结点为空，取右子结点。
void _ThreadedPrevOrder(TBT* root)
{
if (root == NULL)
return;
if (root->left == NULL)
{
root->left = prev;
root->LeftFlag = 1;
}
if (prev && prev->right == NULL)
{
prev->right = root;
prev->RightFlag = 1;
}
prev = root;
if(root->LeftFlag==0)
_ThreadedPrevOrder(root->left);
if(root->RightFlag==0)
_ThreadedPrevOrder(root->right);
}
void ThreadedPrevOrder(TBT* root)
{
if (root == NULL)
return;
_ThreadedPrevOrder(root);
prev->right = NULL;
prev->RightFlag = 1;
}
2.3 后序线索二叉树
同样的，将二叉树进行后序遍历得到的序列就是后序序列，我们需要将他们进行连接。很显然，我们需要找到每一个结点的前驱结点。
如果当前结点的左指针存放的是线索，左指针指向的结点即为前驱节点。
如果当前结点的左指针存放的是结点，取右子结点，如果右子结点为空，取左子结点。
void _ThreadedPostOrder(TBT* root)
{
if (root == NULL)
return;
_ThreadedPostOrder(root->left);
_ThreadedPostOrder(root->right);
if (root->left == NULL)
{
root->left = prev;
root->LeftFlag = 1;
}
if (prev && prev->right == NULL)
{
prev->right = root;
prev->RightFlag = 1;
}
prev = root;
}
void ThreadedPostOrder(TBT* root)
{
if (root == NULL)
return;
_ThreadedPostOrder(root);
}
2.4 中序线索二叉树
将二叉树进行中序遍历得到的序列就是中序序列，我们需要将他们进行连接。很显然，我们需要找到每一个结点的前驱结点和后续结点。
如果当前结点的右指针存放的是线索，右指针指向的结点即为后续节点。
如果当前结点的右指针存放的是结点，右子树中序遍历序列的第一个结点（最左）就是后续节点。
如果当前结点的左指针存放的是线索，左指针指向的结点即为前驱节点。
如果当前结点的左指针存放的是结点，左子树中序遍历序列的最后一个结点（最右）就是后续节点。
void _ThreadedInOrder(TBT* root)
{
if (root == NULL)
return;
_ThreadedInOrder(root->left);
if (root->left == NULL)
{
root->left = prev;
root->LeftFlag = 1;
}
if (prev && prev->right == NULL)
{
prev->right = root;
prev->RightFlag = 1;
}
prev = root;
_ThreadedInOrder(root->right);
}
void ThreadedInOrder(TBT* root)
{
if (root == NULL)
return;
_ThreadedInOrder(root);
prev->right = NULL;
prev->RightFlag = 1;
}
三、遍历线索二叉树
3.1 遍历中序线索二叉树
void inOrderTraverseThTree(TBT* root)
{
//找到初始节点
TBT* head = root;
while (head->left)
head = head->left;
while (head)
{
printf("%d ", head->data);
//找下一个访问的结点
if (head->right && head->RightFlag == 1)
head = head->right;
else if (head->right)
{
head = head->right;
while (head->left && head->LeftFlag == 0)
head = head->left;
}
else if (head->right == NULL)
break;
}
}
3.2 遍历先序线索二叉树
void PrevOrderTraverseThTree(TBT* root)
{
TBT* head = root;
while (head)
{
printf("%d ", head->data);
if (head->LeftFlag == 0)
head = head->left;
else
head = head->right;
}
}
3.3 遍历后序线索二叉树
对于后序线索二叉树的遍历是要复杂一点的，对于根节点的后继结点是不好定位的，最好使用到三叉链，当然也可以迭代找到，这里就不演示了
原文地址：https://blog.csdn.net/2301_80258336/article/details/143725045
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！