引导（起源？）

经过一次非法观察，我发现了对于有n个子叶的二叉树，它总有2n个用来存放指针的空间。这是一个令人震惊的世纪大发现，因为我们知道这n个子叶只需要n-1个节点就够用了（根节点是程序猿另外保存的），所以可以用n+1个空节点保存各子叶的位置，将整棵树串成一条线！多么令人兴奋！！但不幸的是，课本上已经写了这些东西并起名叫线索二叉树。不过不用安慰我，上头一大部分内容都是我编的。

好了我们回到正题，把这些树穿起来之后，就可以视为一个链表甚至线性表进行处理，还行很方便的。但问题是咱们要先遍历一遍才能把线穿上。为了解决问题，在定义的时候加一点点东西，用来分清这片子叶上的地址是子树还是线索。假设增加量LTag和RTag两个int变量，仅仅用0和非0作为区分。为0时表示左右孩子，为1式表示前驱或者后继。

//实际上代码和递归遍历极其相似，仅仅是在操作部分略有修改。

Void dgbl( TNode* tree )

{

If(tree)   //这里的意思是如果tree已经到头了，没有子树，就直接返回

{

Dglt ( tree->lchild );

If(tree->lchild == NULL)

{

Tree->LTag = 1;

Tree->lchild = pre

}

If(pre!=NULL && pre->rchild == NULL)

{

Pre->LTag=1;

Pre->rchild=tree;

}

TNode* pre = tree;

Dgbl( tree->rchild );

}

}

代码就扔着吧，倒也是挺好理解的。只有访问到下一个的时候，才能知道下一个是谁，因为当访问下一个的时候，下一个是T，让pre的rchild指向T就好

 

再之后想要遍历，无脑访问右孩子就行