数据结构之线索二叉树数据结构

Dear 丶 2022-06-06 07:53 366阅读 0赞

首先要谈一谈线索二叉树为什么会产生，很多东西不是无缘无故的突然出现在书本，那么肯定是有他出现的理由，我先举个你们熟悉的案例，比如开始我们是使用单链表进行数据的存储和访问，但是访问方法只能从一端跑到顶，假如我们想要访问最后一个节点元素，我们必须通过首节点开始一一遍历，这个时候循环链双向表就产生了，我们可以快速访问末尾节点，那么线索二叉树也是为了快速访问吗，NO,我们是为了不浪费内存，其实都一样，都是为把数据结构类型设计的更加完美。  
先上图观察一下二叉树浪费的内存。

![这里写图片描述][SouthEast]

我们把节点元素中那么没有孩子节点的指针占的内存都加起来都是浪费的内存。那么我们如果想把这么没有保存节点地址的指针变量保存我们需要的数据是不是非常nice呢，回答是肯定的。

我们如果采用中序遍历输出如下：

![这里写图片描述][SouthEast 1]

按照中序遍历后得到的节点序列如图，我们仔细发现H节点端的指针都是空的，I节点2端的指针也是空的，E也是，刚好是隔一个就有个节点2端刚好都是浪费的。难道我们不能刚好把那2个坑刚好保存当前序列的前后节点地址么，充分利用。因此线索二叉树在进行中序遍历后每个元素节点可以非常快速的访问其序列的前后节点。但是有个问题这2个地址都是保存节点地址，那么我们是如何区分保存的孩子节点还是前后节点呢。我们是通过浪费内存定义2个标志用来当前保存的是孩子节点还是前后节点。

先看图  
![这里写图片描述][SouthEast 2]

我们约定ltag = 0时表示该节点指向做孩子，1就说明是保存的节点的前驱 ltag ===leftTag 左标志  
其他就。。。  
typedef char ElemType;

//线索存储标志位  
//Link(0)表示表示指向左右孩子的指针  
//Thread(1)表示指向前驱后继的线索  
typedef enum \{Link, Thread\} PointerTag;

typedef struct BiThrNode  
\{  
ElemType data;  
struct BiThrNode \*lchild, \*rchild;  
PointerTag ltag;  
PointerTag rtag;  
\} BiThrNode, \*BitThrTree;

待续代码日后贴上

[SouthEast]: /images/20220606/bb6a831df0b343dc84d850a84535a26b.png
[SouthEast 1]: /images/20220606/fdaaaad64d2c40eea06838a3b2a8543d.png
[SouthEast 2]: /images/20220606/476e093964f74f42b8b86b663f6a0c4c.png