数据结构与算法「线索化二叉树」

题分析：

1. 当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,14,6}
2. 但是6，8，10，14这几个节点的左右指针，并没有完全的利用上。
3. 如果我们希望充分的利用各个节点的左右指针，让各个节点指向自己的前后节点怎么办?
4. 解决方案-线索二叉树

线索二叉树基本介绍

1. n 个节点的二叉链表中含有n+1【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放该节点在某种遍历次序下的前驱和后继点的指针(这种附加的指针称为线索)。
2. 这种加了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索的性质不同，线索二叉树可分为前序线索二叉树、中序线索二叉树、后序线索二叉树三种。
3. 一个节点的前一个节点，称为前驱节点。
4. 一个节点的后一个节点，称为后继节点。

中序线索二叉树图解

序遍历的结果{8,3,10,1,14,6}

说明：当线索化二叉树后，Node节点的属性left和right,有如下情况：

1. left指向的值左子树，也可能是指向的前驱节点，比如①节点left指向的左子树，而⑩节点的left指向的就是前驱节点。
2. right指向的右子树，也可能是指向后继节点，比如①节点right指向的是右子树，而⑩节点的right指向的是后继节点。

（编辑：阜阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!