#include<stdio.h>
#include<stdlib.h>
//线索化二叉树
//定义线索二叉树的存储结构
typedef struct ThreadNode{
char data; //存数据
struct ThreadNode* Left; //指针域
struct ThreadNode* Right; //指针域
int Tag_Left,Tag_Right; //标识域
}ThreadNode,*ThreadTreeNode;
ThreadTreeNode pre = NULL; //辅助指针 指向刚访问的树结点 全局变量
//线索二叉树的初始化（建立）先序建立 按顺序插入
ThreadTreeNode InitThreadTree(ThreadTreeNode Tree){
char ch;
printf("请输入数据 (#表示空指针):\n");
ch = getchar();
getchar(); //吃掉enter产生的空格
if(ch == '#') Tree = NULL; //以#代表空
else{
Tree = (ThreadTreeNode)malloc(sizeof(ThreadNode));
Tree->data = ch;
//此时不对标识域进行初始化 遍历的时候才对标识域进行处理
Tree->Left = InitThreadTree(Tree->Left);
Tree->Right = InitThreadTree(Tree->Right);
}
return Tree;
}
//中序线索化 不同遍历顺序 有不同的线索化二叉树
/*每个树结点都考虑两次 如果其左子树为空 则指向前驱
考虑后继的时候要到下一个结点操作 如果pre不空且pre有右子树则成为pre的后继*/
/*TreeRoot为根结点指针 中序线索二叉树(不带头结点)*/
void InThreading(ThreadTreeNode TreeRoot) //TreeRoot为根结点指针
{
if(TreeRoot)
{
InThreading(TreeRoot->Left); /*左子树递归线索化*/
if(TreeRoot->Left == NULL) /*如果没有左子树*/
{
TreeRoot->Tag_Left = 1; /*Tag = 1*/
TreeRoot->Left = pre; /*设置前驱*/
}
else TreeRoot->Tag_Left= 0; /*有左子树 Tag = 0*/
//判断当前节点的前驱节点不为空且其右子树为空，则改其右指针指向当前节点
if(pre != NULL && pre->Right == NULL)
{
pre->Tag_Right = 1; /*设置后继*/
pre->Right = TreeRoot;
}
else pre->Tag_Right = 0;
pre = TreeRoot; /*记录结点 */
InThreading(TreeRoot->Right); /*右子树递归线索化*/
}
}
/*---------带头结点的二叉树的中序线索化--------*/
void HeadNode_InitThreadTree(ThreadTreeNode &HeadNode,ThreadTreeNode TreeRoot)
{
HeadNode = (ThreadTreeNode)malloc(sizeof(ThreadNode)); //头结点
HeadNode->Tag_Left= 0; /*头结点有左孩子，为根结点*/
HeadNode->Tag_Right = 1; /*头结点无右孩子，后继线索为中序遍历的最后一个结点*/
HeadNode->Right = HeadNode; /*初始化时后继为头结点本身*/
if(!TreeRoot) HeadNode->Left = HeadNode; /*若二叉树为空，左孩子也为头结点本身*/
else
{
HeadNode->Left= TreeRoot; /*头结点的作用体现，统一根结点与其他结点的处理方式*/
pre = TreeRoot;
InThreading(TreeRoot); /*对二叉树中序线索化*/
pre->Tag_Right = 1; /*线索化结束后，pre为二叉树的最右结点*/
pre->Left = HeadNode; /*使其右线索指向头结点*/
HeadNode->Right = pre; /*将头结点的后继从它本身改为最右结点*/
}
}
/*----------遍历中序线索二叉树----------*/
void Show(ThreadTreeNode HeadNode)
{/*HeadNode指向线索二叉树的头结点，而头结点的左指针指向二叉树的根结点*/
ThreadTreeNode Woke_Ptrl = HeadNode->Left; /*使p指向根结点*/
while(Woke_Ptrl != HeadNode) /*若线索二叉树不为空或遍历未结束*/
{
while(Woke_Ptrl->Tag_Left == 0) /*沿左孩子往下，定位*/
Woke_Ptrl=Woke_Ptrl->Left;
printf("%c ",Woke_Ptrl->data); /*访问左子树为空的结点*/
/*若有右线索，且右线索不为头结点*/
while(Woke_Ptrl->Tag_Right == 1 && Woke_Ptrl->Right != HeadNode)
{
Woke_Ptrl = Woke_Ptrl->Right;
printf("%c ",Woke_Ptrl->data); /*沿右线索访问后继结点*/
}
Woke_Ptrl = Woke_Ptrl->Right; /*转向p的右子树*/
}
}
int main(){
ThreadTreeNode HeadNode =NULL; //头结点
ThreadTreeNode tree = NULL;
tree = InitThreadTree(tree);
HeadNode_InitThreadTree(HeadNode,tree);
printf("中序线索二叉树的输出:\n");
Show(HeadNode);
}
修改如下，供参考：
#include<stdio.h>
#include<stdlib.h>
//线索化二叉树
//定义线索二叉树的存储结构
typedef struct ThreadNode {
char data; //存数据
struct ThreadNode* Left; //指针域
struct ThreadNode* Right; //指针域
int Tag_Left, Tag_Right; //标识域
}ThreadNode, * ThreadTreeNode;
ThreadTreeNode pre = NULL; //辅助指针 指向刚访问的树结点 全局变量
//线索二叉树的初始化（建立）先序建立 按顺序插入
ThreadTreeNode InitThreadTree(ThreadTreeNode Tree) {
char ch;
printf("请输入数据 (#表示空指针):\n");
ch = getchar();
getchar(); //吃掉enter产生的空格
if (ch == '#') Tree = NULL; //以#代表空
else {
Tree = (ThreadTreeNode)malloc(sizeof(ThreadNode));
Tree->data = ch;
//此时不对标识域进行初始化 遍历的时候才对标识域进行处理
Tree->Left = InitThreadTree(Tree->Left);
Tree->Right = InitThreadTree(Tree->Right);
}
return Tree;
}
//中序线索化 不同遍历顺序 有不同的线索化二叉树
//每个树结点都考虑两次 如果其左子树为空 则指向前驱
//考虑后继的时候要到下一个结点操作 如果pre不空且pre有右子树则成为pre的后继
//TreeRoot为根结点指针 中序线索二叉树(不带头结点)
void InThreading(ThreadTreeNode TreeRoot) //TreeRoot为根结点指针
{
if (TreeRoot)
{
InThreading(TreeRoot->Left); //左子树递归线索化
if (TreeRoot->Left == NULL) //如果没有左子树
{
TreeRoot->Tag_Left = 1; //Tag = 1
TreeRoot->Left = pre; //设置前驱
}
else TreeRoot->Tag_Left = 0; //有左子树 Tag = 0
//判断当前节点的前驱节点不为空且其右子树为空，则改其右指针指向当前节点
if (pre->Right == NULL ) //&& pre->Tag_Right == NULL)//
{
pre->Tag_Right = 1; //设置后继
pre->Right = TreeRoot;
}
else pre->Tag_Right = 0;
pre = TreeRoot; //记录结点
InThreading(TreeRoot->Right); //右子树递归线索化
}
}
//---------带头结点的二叉树的中序线索化--------
void HeadNode_InitThreadTree(ThreadTreeNode& HeadNode, ThreadTreeNode TreeRoot)
{
HeadNode = (ThreadTreeNode)malloc(sizeof(ThreadNode)); //头结点
HeadNode->Tag_Left = 0; //头结点有左孩子，为根结点
HeadNode->Tag_Right = 1; //头结点无右孩子，后继线索为中序遍历的最后一个结点
HeadNode->Right = HeadNode; //初始化时后继为头结点本身
if (!TreeRoot) HeadNode->Left = HeadNode; //若二叉树为空，左孩子也为头结点本身
else
{
HeadNode->Left = TreeRoot; //头结点的作用体现，统一根结点与其他结点的处理方式
pre = HeadNode;//pre = TreeRoot;
InThreading(TreeRoot); //对二叉树中序线索化
pre->Tag_Right = 1; //线索化结束后，pre为二叉树的最右结点
pre->Right = HeadNode;//pre->Left = HeadNode;//使其右线索指向头结
HeadNode->Right = pre; //将头结点的后继从它本身改为最右结点
}
}
//----------遍历中序线索二叉树----------
void Show(ThreadTreeNode HeadNode)
{//HeadNode指向线索二叉树的头结点，而头结点的左指针指向二叉树的根结点
ThreadTreeNode Woke_Ptrl = HeadNode->Left; //使p指向根结点
while (Woke_Ptrl != HeadNode) //若线索二叉树不为空或遍历未结束
{
while (Woke_Ptrl->Tag_Left == 0) //沿左孩子往下，定位
Woke_Ptrl = Woke_Ptrl->Left;
printf("%c ", Woke_Ptrl->data); //访问左子树为空的结点
//若有右线索，且右线索不为头结点
while (Woke_Ptrl->Tag_Right == 1 && Woke_Ptrl->Right != HeadNode)
{
Woke_Ptrl = Woke_Ptrl->Right;
printf("%c ", Woke_Ptrl->data); //沿右线索访问后继结点
}
Woke_Ptrl = Woke_Ptrl->Right; //转向p的右子树
}
}
int main()
{
ThreadTreeNode HeadNode = NULL; //头结点
ThreadTreeNode tree = NULL;
tree = InitThreadTree(tree);
HeadNode_InitThreadTree(HeadNode, tree);
printf("中序线索二叉树的输出:\n");
Show(HeadNode);
return 0;
}