第六章树和二叉树old.ppt

第6章 树和二叉树;主要内容;§6.1 树的定义和基本术语(1);§6.1 树的定义和基本术语(2);§6.1 树的定义和基本术语(3);结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根在第L+1层。 树的深度（高度）：结点层次的最大值 有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。 森林：m（m≥0）个树的集合;树的基本操作： 构造空树 InitTree(T); 销毁树 DestroyTree(T); 创建树 CreateTree(T, definition); 清空树 ClearTree(T); 判断空树 TreeEmpty(T); 求树的深度 TreeDepth(T); 求双亲 parent(T, cur_e); 求长子 LeftChild(T, cur_e); 求右邻兄弟 RightSibling(T, cur_e); 插入子树 InsertChild(T, p, i, c); 删除子树 DeleteChild(T, p, i); 遍历树 TraverseTree(T, visite());;§6.2 二叉树;§6.2.1 二叉树的定义(1);§6.2.1 二叉树的定义(2);§6.2.1 二叉树的定义(3);§6.2 二叉树;§6.2.2 二叉树的性质(1);§6.2.2 二叉树的性质(2);§6.2 二叉树;§6.2.3 二叉树的存储结构(1);§6.2.3 二叉树的存储结构(2);§6.2.3 二叉树的存储结构(3);§6.2.3 二叉树的存储结构(4);§6.2.2 二叉树的存储结构(5);§6.3 遍历二叉树;§6.3.1 遍历二叉树(1);§6.3.1 遍历二叉树(2);§6.3 遍历二叉树;§6.3.2 遍历二叉树的递归与非递归算法(1);§6.3.2 遍历二叉树的递归与非递归算法(2);§6.3.2 遍历二叉树的递归与非递归算法(3);§6.3.2 遍历二叉树的递归与非递归算法(4);§6.3.2 遍历二叉树的递归与非递归算法(5);§6.3.2 遍历二叉树的递归与非递归算法(6);§6.3.2 遍历二叉树递归与非递归算法(7);§6.3.2 遍历二叉树递归与非递归算法(8);§6.3 遍历二叉树;§6.3.3 表达式求值;§6.3 遍历二叉树;§6.3.4 二叉树的运算举例(1);计算二叉树中叶子结点的数目 Leafs(…) 思路：叶子数＝左子树叶子数+右子树叶子数;§6.3.4 二叉树的运算举例(3);§6.3 遍历二叉树;§6.3.5 层序遍历二叉树(1);§6.3.5 层序遍历二叉树(2);§6.4 线索二叉树(1);§6.4 线索二叉树(2);§6.4 线索二叉树(3);§6.4 线索二叉树(4);§6.5 树和森林;§6.5.1 树的存储结构(1);§6.5.1 树的存储结构(2);§6.5.1 树的存储结构(1);§6.5 树和森林;§6.5.2 森林和二叉树之间的转换(1);§6.5.2 森林和二叉树之间的转换(2);§6.5 树和森林;§6.5.3 树和森林的遍历(1);§6.5.3 树和森林的遍历(2);§6.5.3 树和森林的遍历(3);§6.6 赫夫曼树及其应用;§6.6.1 最优二叉树（赫夫曼树）(1);§6.6.1 最优二叉树（赫夫曼树）(2);§6.6 赫夫曼树及其应用;§6.6.2 赫夫曼树的构造(1);§6.6.2 赫夫曼树的构造(2);§6.6 赫夫曼树及其应用;§6.6.3 赫夫曼编码(1);§6.6.3 赫夫曼编码(2);§6.6.3 赫夫曼编码(3)