目录
线索二叉树概念
——普通二叉树缺点
1、普通二叉树在遍历的时候必须从根节点出发，不能从其中某一点开始遍历。
2、普通二叉树不能快速的找到某个结点的前驱。（可以实现，思路如下）
从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访的结点 ①当 q == p 时，pre为前驱
②当 pre == p 时，q为后继
缺点是找前驱，后继操作不方便：遍历操作必须从根开始
——中序线索二叉树
n个结点的二叉树，有n+1个空链域！可以用来记录n个前驱、后继的信息
指向前驱、后继的指针称为线索
图示说明
代码如下
//二叉树的结点(链式存储) typedef struct BiTNode{ ElemType date; struct BiTNode *lchild, *rchild }BiTNode ,*BiTree; //线索二叉树结点 typedef struct ThreadNode{ ElemType date; struct ThreadNode *lchild *rchild; int ltag,rtag; }ThreadNode,*ThreadTree;
tag == 0 ，表示指针是指向孩子
tag == 1，表示指针是指向“线索”
——先序线索二叉树
和上同理
——后序线索二叉树
和上同理
—— 三种线索二叉树的比较
二叉树的线索化
用土方法找到中序遍历前驱
普通方法代码
//辅助全局变量，用于查找p的前驱 BiTNode *p; //p指向目标结点 BiTNode * pre = NULL; //指向当前访问结点的前驱 BiTNode * fina = NULL; //用于记录最终结果 void InOrder(BITree T){ if(T != NULL){ InOrder(T->lchild); //递归遍历左子树 visit(T); // 访问根结点 InOrder(T->rchild); // 递归遍历右子树 } } // 访问结点q void visit(BoTNode *q){ if(q == p) //当前访问的结点刚好是p final = pre; //找到p的前驱 else pre = q; //pre指向当前访问的结点 }
中序线索化代码
当ltag = 0，rtag = 0 的时候,表示没有被线索化
//全局变量，pre指向当前访问结点的前驱 ThreadNode *pre = NULL; //线索二叉树结点 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; //中序遍历二叉树，一边遍历一边线索化 void InThread(ThreadTree T){ if(T!=NULL){ InThread(T->lchild); //中序遍历左子树 visit(T); //访问根结点 InThread(T->rchild); //中序遍历右子树 } } void visit(ThreadNode *q) { if(q->lnext == NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre != NULL && pre->rchild == NULL){ pre->rchild = q; //建立前驱结点后继线索 pre->rtag = 1; } pre = q; } //中序线索化二叉树 void CreateInThread(ThreadTree T){ pre = NULL; if(T!=NULL){ //非空二叉树才能线索化 InThread(T); //中序线索化二叉树 if(pre->rchild==NULL) pre->rtag = 1; //处理遍历的最后一个结点 } }
先序线索化代码
//全局变量，pre指向当前访问结点的前驱 ThreadNode *pre = NULL; //线索二叉树结点 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; //先序遍历二叉树 void InThread(ThreadTree T){ if(T!=NULL){ visit(T); if(t->ltag == 0) preThread(T->lchild); PreThread(T->rchild); } } void visit(ThreadNode*q) { if(q->lnext == NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre != NULL && pre->rchild == NULL){ pre->rchild = q; //建立前驱结点后继线索 pre->rtag = 1; } pre = q; } //先序线索化二叉树 void CreateInThread(ThreadTree T){ pre = NULL; if(T!=NULL){ //非空二叉树才能线索化 InThread(T); //先序线索化二叉树 if(pre->rchild==NULL) pre->rtag = 1; //处理遍历的最后一个结点 } }
后序线索二叉树代码
//全局变量，pre指向当前访问结点的前驱 ThreadNode *pre = NULL; //线索二叉树结点 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; //后序遍历二叉树，一边遍历一边线索化 void InThread(ThreadTree T){ if(T!=NULL){ InThread(T->lchild); //后序遍历左子树 InThread(T->rchild); //后序遍历右子树 visit(T); } } void visit(ThreadNode *q) { if(q->lnext == NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre != NULL && pre->rchild == NULL){ pre->rchild = q; //建立前驱结点后继线索 pre->rtag = 1; } pre = q; } //中序线索化二叉树 void CreateInThread(ThreadTree T){ pre = NULL; if(T!=NULL){ //非空二叉树才能线索化 InThread(T); //中序线索化二叉树 if(pre->rchild==NULL) pre->rtag = 1; //处理遍历的最后一个结点 } }
