线索二叉树，在原始二叉树的基础上对节点进行“扩容”，使之变成了一颗节点信息更加丰富，利用率更高的二叉树。具体来说增加了两个指示标签，ltag和rtag，每个标签有两个值，1和0，0代表存在孩子，指针指向相应孩子，1代表没有对应的孩子，指针表示线索，指向其前驱或后继。这样虽然节点多占用了空间（其实很少，只是两个枚举常量而已），换来的却是让原来结构中存在的大量空指针利用起来，变成线索，指示前驱后继，从而使得空间利用效率大大提高， 并且有了线索以后，对后续的查找等操作提高很多效率。
下面是代码，本来以为只需要修改一下标签就完事的，结果写起来还要考虑许多问题：1，pre指针（指向前一个节点的全局指针），以及它的初始化。2，二叉树建立时仍然采用前序方式，但是对节点线索化时需要用中序遍历，最后遍历打印时，因为有了标签，所以可以采用迭代的方式打印输出，至于可否用递归方式打印，还没有尝试过。
下面是代码，主要思路：前序方式建立二叉树（令其标签默认初始化为link），线索化，pre指针的初始化，利用迭代中序遍历打印二叉树。
难点是后面两个，直接想可能很难写出来，可以参照书本画个图理解一下，二叉树这部分画图理解还是蛮重要的！
#include<iostream> using namespace std; enum Tag{link,thread}; //这里定义一个枚举类型，link（0）表示指向孩子，thread(1)表示指向前驱后继的线索 //定义节点结构 typedef struct BiThreadNode { char data; struct BiThreadNode *lchild,*rchild; Tag ltag,rtag; }BiThreadNode,*BiThreadTree; //定义一个全局变量，始终指向刚刚访问过的节点 BiThreadTree pre; //前序遍历创建二叉树 void createBtTree (BiThreadTree &T) { char c; cin>>c; if(c=='#') { T=NULL; } else { T=new BiThreadNode; T->data=c; T->ltag=T->rtag=link; createBtTree(T->lchild); createBtTree(T->rchild); } } //中序遍历二叉线索树并且对节点进行处理. void midOrderThread(BiThreadTree &T) { if(T) { midOrderThread(T->lchild); //对节点进行处理,即把判断为线索的指针域修改为thread。注意修改前驱后继时分别对pre和T两个指针指向的节点进行处理。 if(!T->lchild) { T->ltag=thread; T->lchild=pre; //当发现左孩子为空时另ltag=thread,同时让lchild指针（本来为空）指向前驱节点pre } if(!pre->rchild) { T->rtag=thread; //当发现pre节点的右孩子为空时，另其rtag=thread,同时让他的rchild指向其后继节点T pre->rchild=T; } pre=T; midOrderThread(T->rchild); } } //由于以上只是处理了动态的过程的代码，初始化时会因为pre指针没有赋值从而出错，需要在建立个函数解决此问题 //建立头结点，并中序线索二叉树 void inOrderThread(BiThreadTree &p,BiThreadTree &t) { p=new BiThreadNode; p->ltag=link; p->rtag=thread; p->rchild=p; if(!t) { p->lchild=p; p->ltag=link; } else { p->lchild=t; pre=p; midOrderThread(t); pre->rchild=p; pre->rtag=thread; p->rchild=pre; } } //非递归方式遍历二叉树并输出 void inOrderVisit(BiThreadTree p) { BiThreadTree T; p->lchild=T; while(T!=p) { while(T->ltag==link) { T=T->lchild; } cout<<T->data; while(T->rtag==thread&&T->rchild!=p) { T=T->rchild; cout<<T->data; } T=T->rchild; } } int main() { BiThreadTree Tree,p; createBtTree(Tree); inOrderThread(p,Tree); inOrderVisit(p); }