如何实现二叉树的线索化

卡拉ok台北 · 2018-4-30 02:32:43

自己理解得方法：
先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。

先序遍历线索二叉树：
首先进行先序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

中序遍历线索二叉树：

首先进行中序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

后序遍历线索二叉树：

首先进行后序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，

如何实现二叉树的线索化

1 个回复