chap6第六章 树和二叉树.ppt

第六章 树和二叉树 树的概念和基本术语 二叉树 二叉树遍历 二叉树的计数 树与森林 霍夫曼树 树的基本术语 树的基本操作 性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 二叉树的存储结构 6.3 二叉树的遍历 二叉树遍历应用 遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？ 2. 计算二叉树结点个数(递归算法) 树与森林 用双亲表示实现的树定义 孩子兄弟表示法的树实现的定义 树的遍历 深度优先遍历 先根次序遍历 后根次序遍历 深度优先遍历 当树非空时 访问根结点 依次先根遍历根的各棵 子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 树的后根次序遍历: 当树非空时 依次后根遍历根的各棵 子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 霍夫曼树 (Huffman Tree) 霍夫曼树 带权路径长度达到最小的二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 霍夫曼树的定义 树的孩子链表类型定义 typedef struct CTNode{ int child; struct CTNode * next; }* ChildPtr; //孩子结点 typedef struct{ TElemType data; ChildPtr firstchild; }CTBox; //孩子链表头指针 typedef struct{ CTBox nodes[MAX_TREE_SIZE]; Int n, r; //结点数和根的位置； }CTree; I ∧ H ∧ G ∧ F ∧ E D C B A 0 1 2 3 4 5 6 7 8 …99 结点数和 根的位置 1 3 ∧ 2 4 5 ∧ 8 ∧ 6 ∧ 7 9 0 T.nodes T.n T.r data firstchild 结点的孩子结点链表 结点结构 data firstChild nextSibling A B C D E F G 空链域n+1个 3 孩子兄弟表示法 孩子兄弟表示法用二叉链表作为树的存贮结构 B C D G F E ? ? ? ? ? ? ? A ? B的右兄弟结点 B的第一个孩子结点 typedef char TreeData; typedef struct node { TreeData data; struct node *firstChild, *nextSibling; } TreeNode; typedef TreeNode * Tree; I A C B D H G F E 此二叉链表既是树(a) 的孩子兄弟表示又是二叉树(b)的二叉链表 (a) (b) 由此可将 树与二叉树 对应起来 A I H D G F C E B F I A B D H G C E 树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。 树与二叉树转换方法 树 根 结点X的第一个孩子 结点X紧邻的右兄弟 二叉树 根 结点X的左孩子 结点X的右孩子 I A C B D H G F E F I A B D H G C E 森林 森林：树的集合 将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历； J O P N M L K I A C B D H G F E 包含两棵树的森林 T1 T2 T3 T1 T2 T3 A F H B C D G I J E K A F B C D E G H I K J A B C E D H I K J F G 3 棵树的森林 各棵树的二叉树表示 森林的二叉树表示 森林与二叉树的转换 树的二叉树表示: A B C D E F G A B C E D G F A B C E D G F 树的先根次序遍历 A B C E D G F 路径长度