二叉树的线索化及线索化的遍历

2017-05-09 12:32 阅读 612 次 评论 0 条

为什么要线索化二叉树

1> 二叉树是一种非线性的数据结构,遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时,取到一个节点,只能获取节点的左右孩子,却不能直接遍历任意序列的前驱或者后继

2> 还有一个很重要的原因在于:任意一个二叉树中,它的空指针域永远大于非空指针域,n个节点的二叉树中有2n个指针域,却有n+1个空指针域,二叉树的线索化正是利用了这些空指针域来存放当前节点的前驱和后继。

二叉树的线索化

在二叉树中希望很快找到某一节点的前驱或者后继,而不希望每次都把二叉树遍历一遍,因此在创建二叉树的过程中,需要将每个节点的前驱和后继保存记录下来

当某节点的左指针域为空时,令该指针指向按照某种方式遍历二叉树时得到该节点的前驱节点。当某节点的右指针为空时,令该指针指向按照某种方式遍历二叉树时得到该节点的后继指针。

但是仅有指向左右孩子的指针是远远不够的,原因在于: 左指针指向的是左孩子节点还是前驱节点,右孩子指向的是右孩子的结点还是后继结点。

因此:需要增加两个线索标志位来区分这种情况。

上图中,结点中指向前驱结点和后继结点的指针称为线索,二叉树结点加上线索的二叉树称为线索二叉树,对二叉树以某种方式(前序、中序、后序)遍历使其变成线索二叉树的过程称为该遍历方式的二叉树的线索化。

线索二叉树的结点在原先的基础上加入了左右线索的标志:

leftChild
leftThread
data
rightThread
rightChild

线索化就是为了防止递归带来的不便,因此本文三种线索化都采用非递归实现,底层的数据结构借助栈stack来实现。

二叉树的前序线索化

二叉树的前序线索化遍历

二叉树的中序线索化

二叉树的中序线索化遍历

二叉树的后序线索化

二叉树的后序线索化遍历

源代码及测试用例

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:二叉树的线索化及线索化的遍历 | 术与道的分享
分类:编程素养 标签:
1024do.com导航_术与道导航平台

发表评论


表情