Question

线索二叉树是一种_____结构？

Answer 1

物理结构。包括线性存储和非线性存储其中，线性存储结构有顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）4种结构。非线性存储结构有：树形存储结构、图形存储结构。
1.
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针。
2.
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。