数据结构与算法|详解线索二叉树二叉树|算法|c语言|数据结构

1.了解线索二叉树之前要知道为什么需要线索二叉树

typedef struct BiTNode{ // Node structure ElemType data; // node data struct BiTNode *lchild; // left child struct BiTNode *rchild; // right child }BiTNode, *BiTree; //线索二叉树的定义

普通的链式存储的二叉树只有数据域，左，右孩子指针，仅仅只能体现一种父子关系，不能直接获取在遍历中的前驱和后继。如果需要获取那么需要额外的辅助指针，从头开是遍历，在遍历过程中获取其前驱或者后继，那样的话效率十分低下。
我们发现在二叉链表示的二叉树中有很多的空指针域，如果利用这些空指针域存放遍历中的前驱和后继的相关信息，那么会方便许多二叉树的操作。
所以引入了线索二叉树，来提高查找二叉树前驱和后继的速度。
2.线索二叉树数据结构定义

typedef char ElemType; typedef enum { link,//有左右孩子 thread//标记位，以线索化 }PointTag; typedef struct ThreadNode { ElemType data; struct ThreadNode* lchild, * rchild; PointTag ltag, rtag; //当ltag,rtag为link时表示，lchild, rchild指向左右孩子，为thread时表示为线索，有后继 }ThreadNode, * ThreadBitTree;

3.线索二叉树的构造
构造一棵线索二叉树，其实就是遍历一颗二叉树，只不过在遍历的过程中，检查当前结点左右指针是否为空，如果为空，则需要将其改为指向前驱结点或者后继结点的线索。
如图：

文章图片

代码实现：

//按照中序遍历实现线索化 void CreateInThread(ThreadBitTree T) { if (T) { InOrderThread(T); if (pre->rchild == NULL) {//后序遍历的最后一个结点必为空 pre->rtag = thread; //将其线索化 } printf("线索化完毕！"); } }void InOrderThread(ThreadBitTree T) { if (T) { InOrderThread(T->lchild); VisitT(T); InOrderThread(T->rchild); } }void VisitT(ThreadNode* p) { //建立前驱 if (p->lchild == NULL) { p->lchild = pre; p->ltag = thread; } //建立后继 if (pre != NULL && pre->rchild == NULL) { pre->rchild = p; pre->rtag = thread; } pre = p; }

4.找前驱结点
如图：

文章图片

【数据结构与算法|详解线索二叉树】

//在中序线索二叉树中找到p的前驱结点 ThreadNode *PreNode(ThreadNode *p){ if(p->ltag==1){ p=p->lchild; }else{ p=LastNode(p->lchild); //左孩子的最后右一个结点为其前驱 } return p; }//找到以p为根的子树中，最后一个被中序遍历的结点 ThreadNode *LastNode(ThreadNode *p){ while(p->rtag==0){ p=p->rchild; } return p; }

5.找后继结点
如图：

文章图片

//在中序线索二叉树中找到结点p的后继结点 ThreadNode *NextNode(ThreadNode *p){ if(p->rtag==1){ p=p->rchild; }else{ p=FirstNode(p->rchild); //右孩子的最后一个结点为其后继 } return p; }//找到以p为根的子树中，第一个被中序遍历的结点 ThreadNode *FirstNode(ThreadNode *p){ while(p->ltag==0){//循环找到最左下结点 p=p->lchild; } return p; }

6.线索二叉树的遍历
线索二叉树的遍历总结来说一句话：有线索找线索，没线索找后继。

//线索二叉树中序的遍历算法 void InOrder(ThreadBitTree T) { ThreadNode* p = FirstNode(T); //中序遍历左下角为第一个结点 while (p != NULL) { visit(p); p = NextNode(p); //根据线索化后的二叉树的后继结点 } }//求中序线索二叉树中中序序列下的第一个结点 ThreadNode* FirstNode(ThreadNode* p) { while (p->ltag==link) p = p->lchild; return p; }//求中序线索二叉树中结点p在序列下的后继结点 ThreadNode* NextNode(ThreadNode* p) { if (p->rtag == thread) { return p->rchild; } else return FirstNode(p->rchild); //如果tag位不是线索。则需像找中序序列中第一个结点一样找到其后继结点 }//访问结点 void visit(ThreadNode* p) { printf("%c ", p->data); }