5、3_6_在线索二叉树中找前驱后继.pdf

《5、3_6_在线索二叉树中找前驱后继.pdf》由会员分享，可在线阅读，更多相关《5、3_6_在线索二叉树中找前驱后继.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/13王道考研/1本节内容线索二叉树找前驱/后继王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM知识总览知识总览22020/3/13王道考研/2王道考研/CSKAOYAN.COM中序线索二叉树找中序后继中序线索二叉树找中序后继ABDGECF5312476NULLNULL中序遍历序列：D G B E A F C在中序线索二叉树中找到指定结点*p的中序后继 nextp若 p-rtag=1，则 next = p-rchild若 p-rtag=0p 必有右孩子p中序遍历左根右左根(左 根 右)左根(左 根 右) 根 右)next = p的右子树中最左下结点3王道考研/

2、CSKAOYAN.COM中序线索二叉树找中序后继中序线索二叉树找中序后继在中序线索二叉树中找到指定结点*p的中序后继 next若 p-rtag=1，则 next = p-rchild若 p-rtag=0p 必有右孩子p中序遍历左根右左根(左 根 右)左根(左 根 右) 根 右)next = p的右子树中最左下结点空间复杂度O(1)42020/3/13王道考研/3王道考研/CSKAOYAN.COM中序线索二叉树找中序前驱中序线索二叉树找中序前驱ABDGECF5312476NULLNULL中序遍历序列：D G B E A F C在中序线索二叉树中找到指定结点*p的中序前驱 prep若 p-ltag

3、=1，则 pre = p-lchild若 p-ltag=0p 必有左孩子p中序遍历左根右(左 根 右)根右pre = p的左子树中最右下结点(左 根(左 根 右) )根右5王道考研/CSKAOYAN.COM中序线索二叉树找中序前驱中序线索二叉树找中序前驱在中序线索二叉树中找到指定结点*p的中序前驱 pre若 p-ltag=1，则 pre = p-lchild若 p-ltag=0p 必有左孩子p中序遍历左根右(左 根 右)根右pre = p的左子树中最右下结点(左 根(左 根 右) )根右62020/3/13王道考研/4王道考研/CSKAOYAN.COM先序线索二叉树找先序后继先序线索二叉树找先

4、序后继在先序线索二叉树中找到指定结点*p的先序后继 next若 p-rtag=1，则 next = p-rchild若 p-rtag=0p 必有右孩子p先序遍历 根左右ABDGECF1234567NULL先序遍历序列：A B D G E C F假设有左孩子根 (根 左 右) 右先序遍历 根右根 (根 左 右)假设没有左孩子若p有左孩子，则先序后继为左孩子若p没有左孩子，则先序后继为右孩子7王道考研/CSKAOYAN.COM先序线索二叉树找先序前驱先序线索二叉树找先序前驱在先序线索二叉树中找到指定结点*p的先序前驱 pre若 p-ltag=1，则 next = p-lchild若 p-ltag=

5、0p 必有左孩子p先序遍历 根左右ABDGECF1234567NULL先序遍历序列：A B D G E C F先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱除非用土办法从头开始先序遍历82020/3/13王道考研/5王道考研/CSKAOYAN.COM先序线索二叉树找先序前驱先序线索二叉树找先序前驱如果能找到 p 的父节点，且p是左孩子p先序遍历 根左右p的父节点即为其前驱根(根 左 右)右如果能找到 p 的父节点，且p是右孩子，其左兄弟为空p先序遍历 根 右如果能找到 p 的父节点，且p是右孩子，其左兄弟非空p根左右根(根 左 右)p的父节点即为其前驱如果p是根节点，则p没有先序前

6、驱p的前驱为 左兄弟子树中最后一个被先序遍历的结点改用三叉链表可以找到父节点错误！如果最右下的9王道考研/CSKAOYAN.COM后序线索二叉树找后序前驱后序线索二叉树找后序前驱在后序线索二叉树中找到指定结点*p的后序前驱 pre若 p-ltag=1，则 pre = p-lchild若 p-ltag=0p 必有左孩子p后序遍历左右根ABDGECF7421365NULL后序遍历序列：G D E B F C A假设有右孩子假设没有右孩子若p有右孩子，则后序前驱为右孩子若p没有右孩子，则后序前驱为左孩子左(左 右 根)根后序遍历左根(左 右 根)根102020/3/13王道考研/6王道考研/CSKA

7、OYAN.COM后序线索二叉树找后序后继后序线索二叉树找后序后继在后序线索二叉树中找到指定结点*p的后序后继 next若 p-rtag=1，则 next = p-rchild若 p-rtag=0p 必有右孩子p后序遍历左右根ABDGECF7421365NULL后序遍历序列：G D E B F C A后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继除非用土办法从头开始先序遍历11王道考研/CSKAOYAN.COM如果能找到 p 的父节点，且p是右孩子p后序遍历左 右 根p的父节点即为其后继左 (左 右 根) 根如果能找到 p 的父节点，且p是左孩子，其右兄弟为空后序遍历左 根如果能找到

8、 p 的父节点，且p是左孩子，其右兄弟非空p(左 右 根) 根p的父节点即为其后继如果p是根节点，则p没有后序后继p的后继为 右兄弟子树中第一个被后序遍历的结点改用三叉链表可以找到父节点后序线索二叉树找后序后继后序线索二叉树找后序后继p左 右 根错误！如果最左下的结点有右孩子就不对122020/3/13王道考研/7王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点13王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点中序线索二叉树中序线索二叉树先序线索二叉树先序线索二叉树后序线索二叉树后序线索二叉树找前驱找后继除非用三叉链表，或者用土办法从根开始遍历寻找14