848-数据结构与算法.ppt

数据结构与算法 2004.2-5 结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree) 二叉树的表示 数组表示 二叉树遍历 (Binary Tree Traversal) 树的遍历---按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV 中序遍历 (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 / - 应用二叉树遍历的事例 线索化二叉树(Threaded Binary Tree) 堆 ( Heap ) 树与森林 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 霍夫曼树 (Huffman Tree) 树的遍历 树的二叉树表示 深度优先遍历 (1) 树的先根次序遍历的递归算法 template class Type void TreeType:: PreOrder ( ) { if ( !IsEmpty ( ) ) { visit ( ); //访问根结点 TreeNodeType *p = current; //暂存当前结点 int i = FirstChild ( ); //当前结点转到长子 while (i) { PreOrder ( ); i = NextSibling ( ); } //递归先根遍历各棵子树 current = p; //递归完恢复当前结点 } } (2) 树的后根次序遍历的递归算法 template class Type void TreeType:: PostOrder ( ) { if ( !IsEmpty ( ) ) { TreeNodeType *p = current; //暂存当前结点 int i = FirstChild ( ); //当前结点转到长子 while (i) { PostOrder ( ); i = NextSibling ( ); } //递归后根遍历各棵子树 current = p; //递归完恢复当前结点 visit ( ); //访问根结点 } } (3) 按先根次序遍历树的迭代算法 template class Type void TreeType:: NorecPreOrder( ) { StackTreeNodeType* st ( DefaultSize ); TreeNodeType *p = current; do { while ( !IsEmpty ( ) ) { //从根沿长子链向下 visit ( ); st.Push ( curr