【BigHereo 46】---DataStructure---线索二叉树(四)

电玩女神 2022-06-06 04:07 134阅读 0赞

DataStructure---线索二叉树(四)

## 一,【前言】 ##

在了解线索二叉树之前, 你能回答出来下面几个问吗:

1,为什么要有线索二叉树?

2,线索二叉树有什么?

3,线索二叉树能干什么?

![Center][]

## 二,【问题解答】 ##

1,百科: [https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037?fr=aladdin][https_baike.baidu.com_item_E7_BA_BF_E7_B4_A2_E4_BA_8C_E5_8F_89_E6_A0_91_10810037_fr_aladdin]

![Center 1][]

2, 代码实践: [http://blog.csdn.net/zhouzixin053/article/details/21647019][http_blog.csdn.net_zhouzixin053_article_details_21647019]

3, [数据结构之线索二叉树][Link 1] :[http://blog.chinaunix.net/uid-26548237-id-3476920.html][Link 1]

4, [线索二叉树][Link 2][http://www.cnblogs.com/zhuyf87/archive/2012/11/03/2752722.html][Link 2]

## 三,【总结】 ##

有了线索二叉树后，对它进行遍历时，其实就等于操作一个双向链表结构。

二叉树的二叉线索存储表示（以中序为例）：在线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序串行中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点，这样就创建了一个双向线索链表。这样定义的好处是既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

[Center]: /images/20220606/0f48e1e798b4404cb07828a04301c173.png
[https_baike.baidu.com_item_E7_BA_BF_E7_B4_A2_E4_BA_8C_E5_8F_89_E6_A0_91_10810037_fr_aladdin]: https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037?fr=aladdin
[Center 1]: /images/20220606/4e5ddce3f3404ef8a1b4d8006f291e49.png
[http_blog.csdn.net_zhouzixin053_article_details_21647019]: http://blog.csdn.net/zhouzixin053/article/details/21647019
[Link 1]: http://blog.chinaunix.net/uid-26548237-id-3476920.html
[Link 2]: http://www.cnblogs.com/zhuyf87/archive/2012/11/03/2752722.html