[数据结构与算法]《数据结构》-线索二叉树

静态数组实现二叉树

二叉链表实现二叉树

三叉链表实现二叉树

线索二叉树

为什么需要线索二叉树

当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

解决方法：

• 通过遍历查找–浪费时间
• 增加前驱，后继指针域–浪费空间
• 利用二叉链表中的空指针域

具有 n 个结点的二叉链表中，一共有 2n 个指针域；因为 n 个结点中有 n-1 个孩子，即 2n 个指针域中，有 n-1 个用来指示结点的左右孩子，其余 n+1 个指针域为空。

线索二叉树的定义

如果某个结点的左孩子为空，则将空的左孩子指针域改为 指向其前驱；如果某结点的右孩子为空，这将空的右孩子指针域改为 指向其后继

这种改变指向的指针称为 线索<

开通VIP 解锁文章