十分钟搞懂线索二叉树
一、线索二叉树是什么？
在一个有n个节点的二叉树中，必定有n+1个空指针域，n-1个非空指针域。这样就会非常浪费空间，而且对于这种普通的二叉树我们采用的遍历算法都是递归算法，由于递归是一个不断入栈、出栈的过程，所以相对来说就会浪费系统的资源。那么有没有一种结构可以帮助我们解决这两个问题呢？线索二叉树就是为此而生的哈，线索二叉树中每一个节点都有一个前驱节点和一个后继节点， 它充分的将二叉树中的空指针域利用了起来，在遍历树的时候，我们也不用使用递归算法了，可以直接访问当前节点的前驱节点和后继节点即可。
二、前驱、后继节点
下面我们采用中序遍历为例子分析每个节点的前驱、后继节点。比如下面一棵二叉树采用中序遍历输出的结果为：DBAECF
在这个例子中，B的直接前驱节点就是D，直接后继节点就是A。F的直接前驱节点是C，直接后继节点为None。
将上面的二叉树线索化就得到下面的结构，图中黄色的线指向的是该节点的直接前驱节点，红色的线指向的是该节点的直接后继节点。最后我们就通过节点之间的前驱与后继关系对树进行遍历。
三、线索二叉树节点的结构
对于二叉树中的节点，如果节点有左孩子，那么它的left_Child指向左孩子，否则指向它的直接前驱节点；如果节点有右孩子，那么它的right_Child指向右孩子，否则指向它的直接后继节点。它的节点结构如下所示：
- 如果该节点的 left_Thread = False，代表该节点的 left_Child 指针域指向的是其左孩子；如果 left_Thread = True ，代表该节点的 left_Child 指针域指向的是它的直接前驱节点。
- 如果该节点的 right_Thread = False，代表该节点的 right_Child 指针域指向的是其右孩子；如果 right_Thread = True ，代表该节点的 right_Child 指针域指向的是它的直接后继节点。
节点结构代码如下：
class Node:
def __init__(self,data):
self.data = data
self.left_Child = None
self.right_Child = None
self.left_Thread = False
self.right_Thread = False
四、线索化二叉树
线索化就是要找到二叉树中每个节点的前驱节点和后继节点。与二叉树的遍历一样，二叉树的线索化也有前序、中序、后序3种方式，下面我以中序遍历为例，分析如何进行二叉树的线索化。
我们在二叉树的中序遍历中用到了下面这段代码：
def middle_node(self,node):
if node != None:
self.middle_node(node.left)
print(node.data,end=' ')
self.middle_node(node.right)
采用中序遍历线索化二叉树时使用的也是上面的那段代码，只不过我们需要做一点小小的改动。由于在遍历过程中，我们需要获取当前访问的节点的前驱节点，并且将当前节点的 left_Child 指向前驱节点，所以我们设置一个 prev 变量，它时刻指向当前访问节点的前一个节点 。代码如下：
def middle_order_Thread_Tree(self,node):
if(node != None):
# 递归线索化左子树
self.middle_order_Thread_Tree(node.left_Child)
# 当前节点没有左孩子
if(node.left_Child == None):
node.left_Thread = True
node.left_Child = self.prev
# 前驱节点没有右孩子
if(self.prev != None and self.prev.right_Child == None):
self.prev.right_Thread = True
self.prev.right_Child = node
self.prev = node
# 递归线索化右子树
self.middle_order_Thread_Tree(node.right_Child)
五、非递归遍历线索二叉树
前面我们说过线索化二叉树可以充分利用树中节点的空指针域，并且可以使用非递归方法对树进行遍历，那么如何使用非递归方法进行遍历呢？我们仍以中序遍历为例。
中序遍历线索二叉树步骤：
- 找到当前节点左子树中最左边的节点
- 打印输出节点数据
- 只要当前节点的 right_Thread = True，找到其直接后继节点，当前节点指向其直接后继节点、并打印输出当前节点数据
- 当前节点指向其右孩子，循环遍历
重复上述过程，直到当前节点为空。在遍历的时候，一定要记住我们是从左往右走的，从树最左边的节点一直向树最右边的节点推进，和中序遍历的思想一样。
代码如下：
def middle_order_Print(self,p):
while(p != None):
# 一直找左孩子，直到第一个中序输出的节点
while(p.left_Thread == False):
p = p.left_Child
print(p.data,end=' ') # 打印节点数据
# 如果 p.right_Thread = True，找到其后继节点
while(p.right_Thread == True and p.right_Child != None):
p = p.right_Child
print(p.data,end=' ')
# 往右推进，循环遍历
p = p.right_Child
六、完整代码示例
'''
function: 线索二叉树
author: lemon
'''
class Node:
def __init__(self,data):
self.data = data
self.left_Child = None
self.right_Child = None
self.left_Thread = False
self.right_Thread = False
class Thread_Tree:
def __init__(self):
self.root = None
self.prev = None
# 构建二叉树
def build_Tree(self, data):
new_node = Node(data)
if self.root == None:
self.root = new_node
else:
current = self.root
# 确定新节点应该哪一个节点的下一层
while current != None:
father_node = current
if current.data > new_node.data:
current = current.left_Child
else:
current = current.right_Child
# 确定新节点应该为当前节点的左节点还是右节点
if father_node.data > new_node.data:
father_node.left_Child = new_node
else:
father_node.right_Child = new_node
# 中序遍历线索化二叉树
def middle_order_Thread_Tree(self,node):
if(node != None):
# 递归线索化左子树
self.middle_order_Thread_Tree(node.left_Child)
# 当前节点没有左孩子
if(node.left_Child == None):
node.left_Thread = True
node.left_Child = self.prev
# 前驱节点没有右孩子
if(self.prev != None and self.prev.right_Child == None):
self.prev.right_Thread = True
self.prev.right_Child = node
self.prev = node
# 递归线索化右子树
self.middle_order_Thread_Tree(node.right_Child)
# 中序遍历该线索化二叉树
def middle_order_Print(self,p):
while(p != None):
# 一直找左孩子，直到第一个中序输出的节点
while(p.left_Thread == False):
p = p.left_Child
print(p.data,end=' ') # 打印节点数据
# 如果 p.right_Thread = True，找到其后继节点
while(p.right_Thread == True and p.right_Child != None):
p = p.right_Child
print(p.data,end=' ')
# 往右推进，循环遍历
p = p.right_Child
def main():
thread_tree = Thread_Tree()
array = [7,4,1,5,16,8,11,12,15,9,2]
for data in array:
thread_tree.build_Tree(data)
thread_tree.middle_order_Thread_Tree(thread_tree.root)
thread_tree.middle_order_Print(thread_tree.root)
if __name__ == '__main__':
main()
中序遍历结果：
1 2 4 5 7 8 9 11 12 15 16
总结
在学习线索二叉树的时候，一定要记住我们的最终目的是充分利用树中节点的空指针域，不使用递归算法就可以完成对树的遍历。为了达到这个目的，我们就需要充分利用树中节点的空指针域，并找到其前驱节点和后继节点，从而建立一种链接关系。在最后遍历的时候，我们就可以使用这种链接关系在不使用递归算法的情况下，完成对树的遍历。