#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include <iostream> using namespace std; //线索化二叉树的算法思想: // //1. 按之前构造二叉链表的方法，构造好叉链表，标志位均为0; // //2. 选择恰当的遍历方法遍历该二叉链表，遍历过程中记录下前一个访问的结点; // //3. 判断当前访问结点的左指针域是否为空，如果为空，则修改指针域指向前一一个访问的结点。同时修改标志位为1。 // //4. 判断前一个访问结点的右指针域是否为空，如果为空则修改指针域指向当前访问的结点。同时修改标志位为1。5.直到遍历完所有结点。 typedef struct BiThrNode{ char data; BiThrNode *lchild; BiThrNode *rchild; int ltag; // 0为孩子，1为前驱 int rtag; // 0为孩子，1为后继 }; // 先序创建二叉树 // 输入AB##C##检验 void CreateBiThreadTree(BiThrNode *& T){ char e; scanf("%c", &e); if (e == '#') T = NULL; else{ if (!(T =(BiThrNode *)malloc(sizeof(BiThrNode)))){ return; } T->data = e; T->ltag = T->rtag = 0; CreateBiThreadTree(T->lchild); CreateBiThreadTree(T->rchild); } } // 中序递归线索化算法 void InThreading(BiThrNode *&T, BiThrNode *&pre){ // 子节点，父节点(pre == NULL) if (T){ InThreading(T->lchild, pre); // 递归左孩子线索化 if (T->lchild == NULL){ // 如果左孩子为空 T->ltag = 1; //左边就是前驱 T->lchild = pre; //左指针指向前驱 } /* 中序遍历中前驱的右孩子如果为空，那么前驱的后继节点就是当前节点 */ if (pre != NULL && pre->rchild == NULL){ // 因为pre一开始为空，为了一开始不执行所以pre!=NULL,然后前驱的右孩子为空 pre->rtag = 1; // 右边就是后继 pre->rchild = T; // 右边指向后继 } pre = T; // 更新 InThreading(T->rchild, pre); //递归右孩子线索化 } } void InorderTraverse(BiThrNode *&T){ // 中序遍历 BiThrNode *p = T; while (p){ while (p->ltag == 0)p = p->lchild; printf("%c", p->data); while (p->rtag == 1 && p->rchild){ // 最后一个节点是指向NULL的，确保遍历到最后一个节点能结束循环 p = p->rchild; printf("%c", p->data); } p = p->rchild; } } int main(void){ BiThrNode *t = NULL; BiThrNode *pre = NULL; CreateBiThreadTree(t); cout << "线索化中序遍历："; InThreading(t, pre); InorderTraverse(t); system("pause"); return 0; }
