线索二叉树是一种逻辑结构,是在二叉树的基础上做出的改进,方便查找
这么说吧,对于具有n个节点的二叉树,采用二叉链存储结构时,每个节点有2个指针域,总共有2n个指针域,但是使用的只有(n-1)个,有(n+1)个被浪费掉了。线索二叉树就是利用这些空链域存放节点的直接前驱和直接后继节点的指针,这样指向该线性序列中的“直接前驱”和“直接后继”的指针称作线索
线索二叉树是逻辑结构,实现线索二叉树的树形链表是物理结构。
因为线索二叉树在计算机内部的一种存储结构,所以是物理结构。
相对的,二叉树是一种逻辑结构。
看下数据结构高分笔记上的这个题目:以下哪一个术语与数据的存储结构无关?(
)。A.栈
B.哈希表
C.线索树
D.双向链表
E.循环队列答案:A
本题考查基本数据结构。A项,栈是逻辑结构。
从1.3.1节第7个讲解中可以知道。B项,线索树是在链式存储结构的基础上对树进行线索,与链式存储结构有关。C项,双向链表也是说明线性表是以链式结构存储。D项,哈希是算法,哈希存储方法本质上是顺序存储方法的扩展。哈希表本质上是顺序表的扩展。
E项,循环队列是建立在顺序存储结构上的。说明:这种题目还有一种比较直观的解法,要判断是否与数据的存储结构无关,只需看看这种结构到底有没有具体到使用顺序存储还是链式存储,如果已经具体到了那就一定是和数据的存储结构有关,比如A选项中的栈并没有说明是用顺序栈还是用链栈来实现,所以是逻辑结构。B选项中的线索树很明显是要用链式来实现(现在不清楚没关系,等学完树那一章就理解了),故与数据的存储结构有关,以此类推。
线索二叉树是一种物理结构!