数据结构与算法—赵玉兰树与叉树.pptVIP

4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2.4 二叉树的实现 二叉树的实现方式： 顺序存储实现 适用场合有限：满二叉树、完全二叉树。 一般二叉树浪费空间，且有上限限制。 链式存储实现 无上限限制。 可以描述任意类型的二叉树。 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 递归算法在执行的过程中会使用到栈结构——隐式栈。 栈结构由系统自动开辟。 递归算法转成非递归算法时，也需要使用到栈结构——显式栈。 栈结构需要手动开辟。 二叉树遍历的非递归实现需要手动开辟栈结构，完成遍历过程。 算法分析 三种遍历算法（前序、中序、后序） 时间复杂度：O(n) 空间复杂度：引入栈，O(n) 层次遍历算法 时间复杂度：O(n) 空间复杂度：引入队列，O(n) 4.2 二叉树 4.2.1 二叉树的ADT描述 4.2.2 二叉树的遍历 4.2.3 二叉树的性质 4.2.4 二叉树的实现 4.2.5 二叉树遍历的非递归实现 4.2.6 线索二叉树 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 二叉树结点之间的前驱和后继关系只有在某种次序（前序、中序、后序）的遍历过程中才能确定。 如果能事先知道二叉树结点之间在某种遍历次序（前序、中序、后序）下的前驱和后继关系，那么根据这些前驱和后继即可获得该次序（前序、中序、后序）下的遍历结果。 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 二叉树结点之间的前驱和后继关系只有在某种次序（前序、中序、后序）的遍历过程中才能确定。 在二叉树中如何记录（保存）结点之间的前驱和后继关系？ 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 二叉树结点之间的前驱和后继关系只有在某种次序（前序、中序、后序）的遍历过程中才能确定。 在二叉树中如何记录（保存）结点之间的前驱和后继关系？ 简单方法：为二叉树的每个结点增加两个指针域：Pre和Succ，分别指向该结点在某种次序下遍历时的前驱和后继。 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 二叉树结点之间的前驱和后继关系只有在某种次序（前序、中序、后序）的遍历过程中才能确定。 在二叉树中如何记录（保存）结点之间的前驱和后继关系？ 缺点：浪费存储空间。 4.2.6 线索二叉树 二叉树遍历的实质： 非线性结构(树形结构) ? 线性结构(前驱, 后继) 二叉树结点之间的前驱和后继关系只有在某种次序（前序、中序、后序）的遍历过程中才能确定。 在二叉树中如何记录（保存）结点之间的前驱和后继关系？ 4.2.6 线索二叉树 为了能够结点中利用空闲的leftChild或rightChild来指向前驱或后继，需要区分leftChild或rightChild指向的是左子女或者右子女还是前驱或后继。 解决方法：为结点增加两个标志域。 lTag rTag 4.2.6 线索二叉树 线索：用于存放结点前驱和后继信息的空指针。 线索二叉树 (Threaded Binary Tree) ：加上线索的二叉树。 4.2.6 线索二叉树 线索链表：加上了线索的二叉链表。 线索化：给二叉树添加线索的过程。 4.2.6 线索二叉树 线索化的方式： 前序方式：按照前序遍历序列为二叉树添加线索可得到“前序线索二叉树”。