《树的三种搜索(人工智能).ppt》由会员分享,可在线阅读,更多相关《树的三种搜索(人工智能).ppt(8页珍藏版)》请在三一办公上搜索。
1、二叉树遍历(Binary Tree Traversal),所谓树的遍历,就是按某种次序访问树中的结点,要求每个结点访问一次且仅访问一次。设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,中序遍历二叉树算法的框架是:若二叉树为空,则空操作;否则中序遍历左子树(L);访问根结点(V);中序遍历右子树(R)。遍历结果 a+b*c-d-e/f,中序遍历(Inorder Traversal),表达式语法树,二叉树递归的中序遍历算法emplate void BinaryTree:In
2、Order()InOrder(root);template void BinaryTree:InOrder(BinTreeNode*current)if(current!=NULL)InOrder(currentleftChild);cout currentdata;InOrder(currentrightChild);,中序遍历二叉树的递归过程图解,前序遍历(Preorder Traversal),前序遍历二叉树算法的框架是若二叉树为空,则空操作;否则访问根结点(V);前序遍历左子树(L);前序遍历右子树(R)。遍历结果-+a*b-c d/e f,二叉树递归的前序遍历算法template v
3、oid BinaryTree:PreOrder()PreOrder(root);template void BinaryTree:PreOrder(BinTreeNode*current)if(current!=NULL)cout currentdata;PreOrder(currentleftChild);PreOrder(currentrightChild);,后序遍历(Postorder Traversal),后序遍历二叉树算法的框架是若二叉树为空,则空操作;否则后序遍历左子树(L);后序遍历右子树(R);访问根结点(V)。遍历结果a b c d-*+e f/-,二叉树递归的后序遍历算法template void BinaryTree:PostOrder()PostOrder(root);template void BinaryTree:PostOrder(BinTreeNode*current)if(current!=NULL)PostOrder(currentleftChild);PostOrder(currentrightChild);cout currentdata;,