//二叉树的线索化 #include<stdio.h> #include<stdlib.h> #include<string.h> //定义二叉树线索化节点 typedef struct _TreeNode{ char data; char lefttag;//0表示没有线索化，1表示线索化---每次创建节点都会初始化 所以所有节点默认都是0 char righttag; struct _TreeNode * leftchild; struct _TreeNode * rightchild; }TreeNode, *TreeNodePointer; //定义前驱节点 TreeNodePointer pre = NULL; /* 线索二叉树的定义 普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。 n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。 利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。 备注：二叉树的遍历很复杂，销毁判断也会增加，暂时没看出任何优势所在，虽然花了我2天时间 线索化二叉树并不能通过头节点前驱，后继像链表一样顺序访问，因为原来的双亲节点的后继不是正确的 如图，如果正常的链表 A结点的后继应该是H 结果这里是E 根本无法顺序访问 如果以后有所顿悟 再来修改 */ //创建树 TreeNodePointer CreateTree(){ //定义结构体对象 TreeNodePointer t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL, t5 = NULL, t6 = NULL, t7 = NULL, t8 = NULL, t9 = NULL; t1 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t1 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t1, 0, sizeof(TreeNode)); t2 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t2 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t2, 0, sizeof(TreeNode)); t3 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t3 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t3, 0, sizeof(TreeNode)); t4 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t4 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t4, 0, sizeof(TreeNode)); t5 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t5 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t5, 0, sizeof(TreeNode)); t6 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t6 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t6, 0, sizeof(TreeNode)); t7 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t7 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t7, 0, sizeof(TreeNode)); t8 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t8 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t8, 0, sizeof(TreeNode)); t9 = (TreeNodePointer)malloc(sizeof(TreeNode)); if (t9 == NULL) { printf("分配内存失败！"); return NULL; } //初始化数据 memset(t9, 0, sizeof(TreeNode)); //填充数据域 t1->data = 'A'; t2->data = 'B'; t3->data = 'C'; t4->data = 'D'; t5->data = 'E'; t6->data = 'F'; t7->data = 'G'; t8->data = 'H'; t9->data = 'I'; //建立树之间的关系 t1->leftchild = t2; t1->rightchild = t5; t2->leftchild = NULL; t2->rightchild = t3; t3->leftchild = t4; t3->rightchild = NULL; // t5是t4的左孩子 t4->leftchild = NULL; t4->rightchild = NULL; //t5没有孩子节点 t5->leftchild = NULL; t5->rightchild = t6; t6->leftchild = t7; t6->rightchild = NULL; t7->leftchild = t8; t7->rightchild = t9; t8->leftchild = NULL; t8->rightchild = NULL; t9->leftchild = NULL; t9->rightchild = NULL; return t1; } //销毁树 void Destroy(TreeNodePointer * root){ if (root == NULL) { printf("传入参数不可以为空！ "); return; } TreeNodePointer temptree = *root; //遍历左子树 if (temptree->lefttag == 0) { Destroy(&temptree->leftchild); } //遍历右子树 if (temptree->righttag ==0) { Destroy(&temptree->rightchild); } //访问根节点 if (temptree != NULL) { free(temptree); temptree = NULL; *root = NULL; } } //中序线索化树 void InorderThreading(TreeNodePointer root){ //中序法线索化 if (root != NULL) { //线索化左子树 InorderThreading(root->leftchild); if (!root->leftchild) { //如果该结点的左子树为空，需要线索化 root->lefttag = 1; //该节点的前驱指向前一个节点 root->leftchild = pre; } //前驱节点的后继指向该结点 if (!pre->rightchild) { //如果前驱结点的右子树为空，需要线索化 pre->righttag = 1; pre->rightchild = root; } pre = root; //线索化右子树 InorderThreading(root->rightchild); } } //遍历线索化二叉树 void ForeachTree(TreeNodePointer head){ if (head==NULL) { printf("传入参数不可以为空！ "); return; } //获取根节点 TreeNodePointer root = head->leftchild; while (root != head){ //一直向左遍历 找到最左边的叶子 while (root->lefttag == 0){ root = root->leftchild; } printf("%c", root->data); //判断该节点的右孩子是不是线索 是线索 直接遍历 (遍历所有的右孩子是线索的结点) while (root->righttag == 1 && root->rightchild!=head) { root = root->rightchild; printf("%c", root->data); } //遍历该节点的右孩子 root = root->rightchild; } } void Test(){ //创建头结点 TreeNodePointer head = (TreeNodePointer)malloc(sizeof(TreeNode)); if (head == NULL) { printf("分配内存失败！ "); return; } //初始化 memset(head, 0, sizeof(TreeNode)); //定义树的根节点 TreeNodePointer root = NULL; root = CreateTree(); //根据线索化二叉树定义 //----头结点的前驱指向根节点 线索化标识为0 //----头节点的后继指向中序结果的最后一个元素 线索化标识为1 head->leftchild = root; head->lefttag = 0; //为了防止头结点的后继指向中序的起点 先为头结点的后继赋值 head->rightchild = head; head->righttag = 1; //此时前驱节点指向头结点 pre = head; //线索化树 InorderThreading(root); //此时pre指向的是中序遍历的最后一个节点 pre->rightchild = head; pre->righttag = 1; //头结点的右孩子指向中序遍历的最后一个节点 head->rightchild = pre; //遍历线索化二叉树 ForeachTree(head); //销毁树 Destroy(&root); //释放头节点 if (head!=NULL) { free(head); head = NULL; } } void main(){ Test(); system("pause"); }
