美文网首页数据结构
数据结构重学日记(二十四)线索二叉树

数据结构重学日记(二十四)线索二叉树

作者: 南瓜方糖 | 来源:发表于2019-01-28 22:06 被阅读0次

线索二叉树是不借助栈而借助链表实现的非递归遍历方式。

在之前的操作中,n 个结点的二叉树就有 n + 1 个空指针,这就造成了很大浪费,所以可以将空指针利用起来,存放其他结点的地址,这样更便于索引。

还以这个树为例, 中序遍历的顺序为 D G B A E C F,G 没有左右子树,下一个结点为 B,所以把 G 的右指针存为 B,B 没有右子树,所以把 B 的右指针设置为 A 。A 的右子树不空,所以就不管它。

G 的左子树为空,所以 G 的左指针指向 D。

指向前驱后继的指针称为线索。
加入线索的二叉链表就称为 线索二叉树

二叉树

线索二叉树是为了解决二叉树存储存在大量空指针的问题。也可以加快查询某个结点前驱后继的速度。

相关文章

网友评论

    本文标题:数据结构重学日记(二十四)线索二叉树

    本文链接:https://www.haomeiwen.com/subject/xgjzjqtx.html