5、3_4_线索二叉树的概念_20200905124538.pdf

《5、3_4_线索二叉树的概念_20200905124538.pdf》由会员分享，可在线阅读，更多相关《5、3_4_线索二叉树的概念_20200905124538.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/7王道考研/1本节内容线索二叉树概念王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM知识总览知识总览22020/3/7王道考研/2王道考研/CSKAOYAN.COM二叉树的中序遍历序列二叉树的中序遍历序列中序遍历序列：D G B E A F CABDGECF5312476p如何找到指定结点p在中序遍历序列中的前驱？qpre思路：从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针 pre 记录上一个被访问的结点当q=p时，pre为前驱当pre=p时，q为后继preNULL如何找到p的中序后继？缺点：找前驱、后继很不方便；遍历操作必须从根开始能否

2、从一个指定结点开始中序遍历？3王道考研/CSKAOYAN.COM中序线索二叉树中序线索二叉树中序遍历序列：D G B E A F CABDGECF5312476线索化ABDGECF5312476NULLNULL图示说明前驱线索（由左孩子指针充当）：后继线索（由右孩子指针充当）：n个结点的二叉树，有n+1个空链域！可用来记录前驱、后继的信息指向前驱、后继的指针称为“线索线索”问题：如何找到G的后继？42020/3/7王道考研/3王道考研/CSKAOYAN.COMABDGECF5312476NULLNULL图示说明前驱线索（由左孩子指针充当）：后继线索（由右孩子指针充当）：线索二叉树的存储结构线索

3、二叉树的存储结构tag=0，表示指针指向孩子tag=1，表示指针是“线索”* lchildltagdatartag* rchild*lchilddata*rchild术语：二叉链表术语：线索链表5王道考研/CSKAOYAN.COM中序线索二叉树的存储中序线索二叉树的存储0A00B00C11D01E11F11G1NULLNULL对应tag位为1时，表示指针是“线索”对应tag位为0时，表示指针指向其孩子62020/3/7王道考研/4王道考研/CSKAOYAN.COM先序线索二叉树先序线索二叉树先序遍历序列：A B D G E C FABDGECF1234567线索化ABDGECF1234567N

4、ULL图示说明前驱线索（由左孩子指针充当）：后继线索（由右孩子指针充当）：按照“先序遍历”进行线索化7王道考研/CSKAOYAN.COM先序线索二叉树的存储先序线索二叉树的存储0A00B00C11D01E11F11G1NULL82020/3/7王道考研/5王道考研/CSKAOYAN.COM后序线索二叉树后序线索二叉树ABDGECF后序遍历序列：G D E B F C A7421365线索化ABDGECF7421365NULL图示说明前驱线索（由左孩子指针充当）：后继线索（由右孩子指针充当）：按照“后序遍历”进行线索化9王道考研/CSKAOYAN.COM后序线索二叉树的存储后序线索二叉树的存储0A00B00C11D01E11F11G1NULL102020/3/7王道考研/6王道考研/CSKAOYAN.COM三种线索二叉树的对比三种线索二叉树的对比中序线索二叉树线索指向中序前驱、中序后继先序线索二叉树线索指向先序前驱、先序后继后序线索二叉树线索指向后序前驱、后序后继11王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点12