线索化
线索化的主要作用是将二叉树的遍历方式从递归改成非递归，让二叉树的遍历方式表现的像个链表一样。
左边空指针 -> 前驱
右边空指针 -> 后继
即如果当前节点没有左节点，那么左节点要前驱指向上一个节点，如果当前节点没有右节点，那么右节点要后继指向下一个节点。如果没有上一个节点或下个节点则指向空，这样就可以形成一个类似链表的结构。
线索化树结构体
//结构体
struct TreeNodeThread
{
int iVal;
//判断左右节点是否是线索， TRUE 是
BOOL bLeftThread;
BOOL bRightThread;
TreeNodeThread* left;
TreeNodeThread* right;
};
结构体添加了两个用来判断两个TreeNodeThread是否是线索和节点的标志位。.
创建和清空树
//创建一个节点
TreeNodeThread* CreatTreeNodeThread(int iVal)
{
TreeNodeThread* pTreeNode = new TreeNodeThread;
pTreeNode->iVal = iVal;
pTreeNode->left = NULL;
pTreeNode->right = NULL;
pTreeNode->bLeftThread = FALSE;
pTreeNode->bRightThread = FALSE;
return pTreeNode;
}
//清空树
void ClearTreeNodeThread(TreeNodeThread* root)
{
if (root == NULL)
{
return;
}
if (!root->bLeftThread) //判断不是线索再清空
{
ClearTreeNodeThread(root->left); //左子树
}
if (!root->bRightThread)
{
ClearTreeNodeThread(root->right); //右子树
}
delete root;
}
主要就是判断是节点还是线索。
线索化的中序遍历
//中序遍历线索版，接受一个根节点，保存上一个节点，返回一个节点的起始位置
void __InOrderTreeThread(TreeNodeThread* root, TreeNodeThread* pLastNode, TreeNodeThread* pLastNodeFirst)
{
if (root == NULL)
{
return;
}
//左节点
if (root->bLeftThread)
{
__InOrderTreeThread(root->left, pLastNode, pLastNodeFirst);
}
//中序遍历遍历出来的是一个链表， 左 根 右，所以链表第一个节点一定是左子树最左边的节点
if (pLastNodeFirst == NULL)
{
pLastNodeFirst = root;
}
//根节点
if (root->left == NULL)
{
//添加线索，左几点要前驱
root->left = pLastNode;
root->bLeftThread = TRUE; //标志是个线索
}
if (pLastNode != NULL && pLastNode->right == NULL) //上一个节点天机后继
{
pLastNode->right = root;
pLastNode->bRightThread = TRUE; //标志是个线索
}
pLastNode = root;
//右节点
if (root->bRightThread)
{
__InOrderTreeThread(root->right, pLastNode, pLastNodeFirst);
}
}
因为我们每次都是在当前节点时，对上一个节点添加后继，那么就会导致最后一个节点的后继没人添加，所以封装一下:
void InOrderTreeThread(TreeNodeThread* root, TreeNodeThread* pLastNodeFirst)
{
TreeNodeThread* pLastNode = NULL; //用来保存上一个节点
pLastNodeFirst = NULL; //用来保存中序遍历的第一个节点，即链表头
__InOrderTreeThread(root, pLastNode, pLastNodeFirst);
//此时 pLastNode保存最后一个节点，但是此时右节点没有赋值，即最后一个节点的后继
pLastNode->right = NULL;
pLastNode->bRightThread = TRUE;
}
用来获取下一个节点的函数（要使树像一个链表一样工作添加一个Next函数）：
//获取下一个节点
TreeNodeThread* GetNextNode(TreeNodeThread* root)
{
if (root->bRightThread) //右孩子是个线索，直接指向下一个节点（因为右孩子节点保存的是后继元素）
{
return root->right;
}
//中序遍历 根节点的后继一定是右子树最左边的节点
//右子树不是个线索说明存在左子树，则一直找到最左子树最左面的节点，中序遍历出来的 数组 根节点一定是在中间位置的
root = root->left;
while (root->bLeftThread == FALSE && root->left != NULL)
{
root = root->left;
}
return root;
}
如果右孩子是一个线索那么他直接指向一个后继节点，如果右孩子不是个线索，那么说明存在一个右子树，那么当前节点的后继一定是右子树最左面的节点。（因为右孩子相当于保存的是下一个节点的位置，所以直接判断右孩子，中序遍历根节点的后继一定是右子树最左边的节点）
int main()
{
TreeNodeThread* root; //假设是一个树的根节点
TreeNodeThread* pLastNodeFirst = NULL; //用来保存链表头
//中序遍历，返回一个用来遍历的开始节点
InOrderTreeThread(root, pLastNodeFirst);
//打印结果
while (pLastNodeFirst != NULL)
{
printf("%d ", pLastNodeFirst->iVal);
pLastNodeFirst = GetNextNode(pLastNodeFirst);
}
}
通过添加线索使二叉树的遍历方式变得像一个链表，从而省去了递归的过程。
