C++ 环境codeblocks17 通过
/* 线索二叉树 @CGQ 2018/10/29 */ #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; #define ElemType char typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; int LTag,RTag; // Tag 为0表示指向左右孩子，为1表示指向前驱和后继 }BiTNode, *BiTree; BiTree pre;// 全局变量pre，记录节点前驱，初始时指向线索树的头节点（非树根） void CreateBiTree(BiTree &T) {// 先序创建二叉树 ElemType ch; cin>>ch; if(ch == '#') T = NULL; else { T = new BiTNode; T->data = ch; T->LTag = 0; // 标志位置0，表示指向左右孩子（可以不要，在InThreading()中赋值） T->RTag = 0; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void InThreading(BiTree T) {// 中序线索化 if(T) { InThreading(T->lchild); // 左子树递归线索化 if(!T->lchild) // T的左孩子为空 { T->LTag = 1; // 给T加上左线索 T->lchild = pre; // T的左孩子指向pre（前驱） } else T->LTag = 0; if(!pre->rchild) //pre 的右孩子为空 { pre->RTag = 1; // 给pre加上右线索 pre->rchild = T; // pre的左孩子指向T（后继） } else pre->RTag = 0; pre = T; InThreading(T->rchild); // 右子树递归线索化 } } void InOrderThreading(BiTree &THead, BiTree T) {// //中序遍历二叉树T， 线索化，THead 指向头节点 THead = new BiTNode; // 建立头节点 THead->LTag=0; // 头节点的左孩子指向树根 THead->RTag=1; // 头节点有孩子为线索指针 THead->rchild=THead; // 初始化时右指针指向自己 if(!T) THead->lchild=THead; // 树非空，则左指针也指向自己 else { THead->lchild=T; pre = THead; // 头节点左孩子指向树根，pre指向头节点 InThreading(T); // 中序线索化二叉树 pre->rchild=THead; // 线索化结束后，pre为最右节点，pre的右线索指向头节点 pre->RTag=1; THead->rchild=pre; // 头节点右线索指向最右节点 } } void InOrderTraverse_Thr(BiTree &T) {// 中序遍历二叉树，非递归 BiTree p = T->lchild; // p指根节点 while(p != T) { while(p->LTag==0) // 沿左孩子一直向下 p=p->lchild; cout<<p->data<<" "; //访问左子树为空的节点 while(p->RTag==1&&p->rchild!=T) // 沿着右线索访问后续节点 { p=p->rchild; cout<<p->data<<" "; } p = p->rchild; // 当p没有右线索时，转向p的右子树 } } int main() { BiTree T=NULL,THead; CreateBiTree(T); // 创建 InOrderThreading(THead,T); // 线索化 InOrderTraverse_Thr(THead); // 遍历 return 0; } /* 测试数据： AB#CD###EF##HI##G## A / \ B E \ /\ C F H / /\ D I G ABD##E##CF##G## A / \ B C /\ /\ D E F G HDA##C#B##GF##ER##T## */
