线索二叉树是利用结点的空指针域存储结点前驱和后续。
由于具有n个结点的二叉链表中,共有2n个指针域,其中只有子结点的有n-1个,空结点有n+1个,故可利用空指针域存放某种遍历次序下的前趋和后继结点的指针,但为了将两种指针进行区分,需要额外的tag参数,用0,1区分该指针是前趋和后继还是子节点指针。
数据结构:
线索二叉树的意义是减少了的空指针域的同时又对每个节点增加了两个标志位。
实际应用意义:
当路由器使用CIDR,选择下一跳的时候,或者转发分组的时候,通常会用最长前缀匹配(最佳匹配)来得到路由表的一行数据,为了更加有效的查找最长前缀匹配,使用了一种层次的数据结构中,通常使用的数据结构为二叉线索。
线索二叉树优势与不足:
一、优势
1、利用线索二叉树进行中序遍历时,不必采用堆栈处理,速度较一般二叉树的遍历速度快,且节约存储空间。
2、任意一个结点都能直接找到它的前驱和后继结点。
二、不足
1、结点的插入和删除麻烦,且速度也较慢。
2、线索子树不能共用。
在有n个结点的二叉链表中必定存在n+1个空指针域,因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针,这种指向前趋和后继结点的指针称为“线索”,加上线索的二叉链表称为线索链表,相应的二叉树被称为线索二叉树,相当于一个双向链表相比二叉树而言可以更好的找到某个节点的前驱和后继