526互联

线索二叉树

发布时间 2023-05-07 11:32:43作者: harper886

线索二叉树

为什么要研究线索二叉树?

image-20230507104544552

如何解决上面的问题?

我们使用第三种方法

image-20230507105042290

二叉链表当中右很多空的指针域

image-20230507105129628

线索二叉树定义

image-20230507105300867

例子

线索二叉树

image-20230507110504339

增设了这些指针之后,会难以区分是指向孩子的指针还是指向前驱结点或者后继结点的指针

所以要加上两个标志域

image-20230507110755324

线索二叉树的结点结构

image-20230507110916608

先序线索二叉树

image-20230507111258266

中序线索二叉树

image-20230507111645977

后序线索二叉树

image-20230507111717689

练习

image-20230507112151288

线索二叉树还是有指针会悬空,怎么解决?

可以增加一个头结点

让头结点的左指针指向根结点,头结点的右指针指向二叉树遍历顺序的最后结点

image-20230507112705028