什么是线索二叉树,为什么要使用线索二叉树
发布网友
发布时间：2022-03-31 18:17
共2个回答
懂视网
时间：2022-03-31 22:38
引入线索二叉树的目的是找一个节点的前驱后继的时候，比非二叉线索树方便快捷。按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。
当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
热心网友
时间：2022-03-31 19:46
在有n个结点的二叉链表中必定存在n+1个空指针域，因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树被称为线索二叉树，相当于一个双向链表
相比二叉树而言可以更好的找到某个节点的前驱和后继
