【数据结构】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;elsehead = head->right;}
}

3.3 遍历后序线索二叉树

对于后序线索二叉树的遍历是要复杂一点的，对于根节点的后继结点是不好定位的，最好使用到三叉链，当然也可以迭代找到，这里就不演示了