数据结构——线索二叉树

二叉树的遍历顺序

**前序遍历：**1、2、4、5、3、6

**中序遍历：**4、2、5、1、6、3

**后序遍历：**4、5、2、6、3、1

线索二叉树

利用二叉树链表的空指针实现线索二叉树。

线索化：

若无左子树，则将其左指针指向其前驱结点；若无右子树，则将其右指针指向其后继结点；

先序线索二叉树

**前序遍历：**1、2、4、5、3、6

中序线索二叉树（较为常用）

**中序遍历：**4、2、5、1、6、3

中序遍历：第一个结点是最左侧结点，最后一个结点是最右边的结点。

前驱结点：

若左指针为线索，则其指向结点为前驱结点；若左指针为左孩子，则其左子树的最右侧结点为前驱结点。

后继结点：

若右指针为线索，则其指向结点为后驱结点；若右指针为右孩子，则其右子树的最左侧结点为后驱结点。 void CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T!=NULL){ InTread(T,pre); pre->rchild=NULL; pre->rtag=1; } } // 引用类型：需要对其进行修改 void InTread(ThreadTree &p,ThreadTree &pre){ // 传入参数 线索二叉树根结点、对应节点前驱结点 if(p!=NULL){ // 判断根结点是否为空 InThread(p->lchild,pre); // 线索化，递归调用线索化左子树：左子树根结点及前驱结点 if(p->lchikd==NULL){ p->lchild=pre; p->ltag=1; } if(pre!=NULL && pre->rchild==NULL){ pre->rchild=p; pre->rtag=1; } pre=p; InThread(p->rchild,pre); } }

带有头结点的中序线索二叉树：

增加一个头结点

左指针指向根结点；第一个遍历序列（4）左指针指向头结点；头结点的右指针指向最后一个遍历序列（3）;遍历序列的最后一个结点（3）的右指针指向头结点。

后序线索二叉树

**后序遍历：**4、5、2、6、3、1

线索二叉树结点结构——线索链表

增加两个标志位：

$$标志域l(r)tag=\{\begin{array}{ll}0,& \text{l(r)child 域指示结点的左（右）孩子}\\ 1,& \text{l(r)child 域指示结点的前驱（后继）}\end{array}$$

typedef structure ThreadNode{ ElemType data; structure ThreadNode *lchild, *rchild; int ltag,rtag; }ThreadNode,*ThreadTree;

中序线索二叉树遍历

寻找第一个结点：

// 从根结点出发，循环找到最左侧的结点 ThreadNode *Firstnode(ThreadNode *p){ while(p->ltag==0) p=p->lchild; return p; }

找到后继结点：

ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag==0) // tag为0为孩子结点，需要找到它右子树最左侧结点为后继 return Firstnode(p->rchild); else // tag为1为先做点，右指针就是后继结点 return p->rchild; }

循环调用寻找后继节点的函数：

void InOrder(ThreadNode *T){ for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)) visit(p); }