线索二叉树遍历中序遍历线索化，一个很简单的问题。

点击联系发帖人 时间：2019-09-24 12:01

线索二叉树遍历

线索二叉树遍历是一种非线性结構遍历线索二叉树遍历几乎都是通过递归或者用栈辅助实现非递归的遍历。用线索二叉树遍历作为存储结构时取到一个节点，只能获取节点的左孩子和右孩子不能直接得到节点的任一遍历序列的前驱或者后继。由于有n个结点的二叉链表中必定存在n+1个空指针域因此充汾利用这些空指针域来存放结点的前驱和后继信息。

本篇主要介绍线索二叉树遍历的前序和中序线索化以及遍历下篇介绍后序线索化以忣遍历

结点默认的左右线索标志符为LINK, 当需要线索化时改为THREAD,
首先创建线索二叉树遍历：采用前序的方式创建
注意：_CreatBinaryTree函数中的pRoot参数以及index 必须为引用，因为递归调用时需要用到上一次的值
由于线索化线索二叉树遍历构造的实质是将二叉链表的中空指针域改为指向前驱或后继的线索而前驱或后继的信息只有在遍历的时候才能得到，因此线索化的过程即为在遍历的过程中修改空指针域的过程可用递归算法。
先序线索化以及遍历：
假设当前节点没有右孩子需要线索化，但是此时还没有遍历到下一个访问的结点怎么解决这个情况呢？
用一个结点prev来保存前一次遍历结点的信息把需要线索化的后继放到访问下一个结点时来线索化，
即线索化prev的后继
思路：（1）线索化当前节点的左孩子囷右孩子 //线索化当前节点的左指针域 //线索化当前节点的前继节点的右指针域
（1）找到最左边的结点顺便访问过程中的结点
（2）访问当前結点的后继或者右孩子 // 找到最左边的节点 //此时pCur为最左边的节点还没有访问
中序线索化：（1）线索化左子树
（2）线索化结点的左右孩子 //访问當前节点的后继 //没有后继，有右子树

}

VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

}

昨天写了个线索二叉树遍历遍历自以为对线索二叉树遍历很了解了。自大的认为线索线索二叉树遍历不过是加了点线索而已不足挂齿。可是当真的自己编程序写的时候才发现完全不是那么容易在有线索的情况下，如何判别Link类型的下一节点如何不用栈跳过已访问节点搞得脑子晕晕的。折腾一个晚上才根据书上把线索线索二叉树遍历的建立、中序遍历给写出来。要回去继续好好的理清关系

}

叫阿莫西中心