数据结构与算法（c 描述）-k8凯发旗舰

17软件工程《数据结构与算法》 第8周安排

讲解第5章的内容 114-131页

重点

1、二叉树的遍历操作

（由中序遍历和前（后）序遍历推断出一颗唯一的二叉树）

2、二叉树的存储结构和递归算法

（链式存储结构的程序实现）

3、线索二叉树

二叉树遍历是二叉树各种操作的基础，例如线索二叉树也可以看作是二叉树遍历的一种应用，关键在于理解如何解题和编程的步骤

4、二叉树遍历的非递归实现

如何利用栈的特性来实现二叉树

实验内容于10月31日公布

大家可以根据自己的情况进行相应的预习

师说

1. 求两个节点的最近公共祖先；

2. 求二叉树中最远的两个节点的距离；

3. 由前序遍历和中序遍历重建二叉树（如:前序序列:1 2 3 4 5 6 - 中序序列 :3 2 4 1 6 5）；

4. 判断一棵树是否是完全二叉树 ；

5. 将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向；

6.求二叉树的宽度；

7. 判断一棵二叉树是否是平衡二叉树；

8.判断一颗二叉树是否是另一颗树的子树。