《7-1遍历二叉树》由会员分享，可在线阅读，更多相关《7-1遍历二叉树（8页珍藏版）》请在金锄头文库上搜索。
1、6.3 遍历二叉树 (Binary Tree Traversal),遍历二叉树 以某种次序访问二叉树中的每个结点，且每个结点仅被访问 一次 访问 如查询结点数据域的内容、输出结点的数据、修改结点的数 据或是执行对结点的其他操作 设 访问根结点 记作 T 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有: TLR,TRL,LTR, RTL,LRT,RLT 取三种遍历次序 TLR 先根遍历 LTR 中根遍历 LRT 后根遍历,为了便于理解遍历思想，暂时为右图示的二叉树中每个没有子树的结点均补充上相应的空子树，用表示。 设想有一条搜索路线(用虚线表示)，它从根结点的左支开始，自
2、上而下自左至右搜索，最后由根结点右支向上出去。恰好搜索线途经每个有效结点都是三次。,遍历方法,第一次经过时访问的结点是：A、B、D、C 先根遍历 第二次经过才访问的结点是：B、D、A、C 中根遍历 第三次经过才访问的结点是：D、B、C、A 后根遍历,先根遍历二叉树的递归定义为： 若二叉树为空，则空操作； 否则 访问根结点 (T)； 先根遍历左子树 (L)； 先根遍历右子树 (R)。,先根遍历二叉树,遍历结果 A B D E H I J K C F G,(Preorder Traversal),/*算法6.2 先根遍历以bt为根的二叉树 */ void Preorder(BTNode *bt )
3、 if (bt) printf(bt-data); /*访问根结点*/ Preorder(bt-lchild); /*先根遍历左子树*/ Preorder(bt-rchild); /*先根遍历右子树*/ ,说明：算法中访问根结点的操作简化为输出根结点的值，输出格式具体使用时加上，在后面的各种有关算法同样处理。,先根遍历二叉树的递归算法,遍历结果 D B H E J I K A F C G,中根遍历二叉树,(Inorder Traversal),中根遍历二叉树的递归定义为： 若二叉树为空，则空操作； 否则 中根遍历左子树 (L)； 访问根结点 (T)； 中根遍历右子树 (R)。,/*算法5.5
4、中根遍历以bt为根的二叉树 */ void Inorder(BTNode *bt ) if (bt) Inorder(bt-lchild); /*中根遍历左子树*/ printf(bt-data); /* 访问根结点 */ Inorder(bt-rchild); /* 中根遍历右子树*/ ,中根遍历二叉树的递归算法,遍历结果 D H J K I E B F G C A,后根遍历二叉树,(Postorder Traversal),后根遍历二叉树的递归定义为： 若二叉树为空，则空操作； 否则 后根遍历左子树 (L)； 后跟遍历右子树(R)； 访问根结点 (T)。,问题 请同学们写上后根遍历的递归算法,后根遍历二叉树的递归算法,
