c语言数据结构 之 树.ppt

第六章 树和二叉树 树的概念和基本术语 二叉树 二叉树遍历 二叉树的计数 树的基本术语 性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 二叉树的存储结构 二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L遍历根的右子树记作 R则可能的遍历次序有前序VLR中序LVR后序LRV中序遍历 (Inorder Traversal) 中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / - 二叉树遍历应用 以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。 2. 计算二叉树结点个数(递归算法) 通过中序遍历建立中序线索化二叉树 template class Type void ThreadTreeType :: InThread ( ThreadNodeType * current,ThreadNodeType * pre ) {if ( current != NULL ) {InThread ( current-leftChild, pre ); //递归, 左子树线索化if ( current-leftChild == NULL ) {current-leftChild = pre;current-leftThread = 1;} //建立当前结点的前驱线索if ( pre != NULL pre-rightChild == NULL ) {pre-rightChild = current;pre-rightThread = 1;} //建立前驱结点的后继线索 pre = current; //前驱跟上当前指针 InThread ( current-rightChild, pre );//递归, 右子树线索化} } 树与森林 用双亲表示实现的树定义 用左子女-右兄弟表示实现的树定义 树的遍历 深度优先遍历 先根次序遍历 后根次序遍历 深度优先遍历 当树非空时 访问根结点 依次先根遍历根的各棵子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 树的后根次序遍历: 当树非空时 依次后根遍历根的各棵 子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 二叉树的计数由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 霍夫曼树 (Huffman Tree) 霍夫曼树 带权路径长度达到最小的二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 霍夫曼树的定义 计算具有 n 个结点的不同二叉树的棵数 最终结果： bi bn-i-1 1 路径长度 (Path Length)两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和 EPL。树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和 IPL。树的路径长度 PL = EPL + IPL 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 树的外部路径长度 EPL = 3*1+2*3 = 9 树的外部路径长度 EPL = 1*1+2*1+3*1+4*1 = 10 1 带权路径长度 (Weighted Path Length, WPL) 二叉树的带权