PS：本文为转载文章，原文可读性会更好。,1前序遍历搜索1,2中序遍历搜索1,3后序遍历搜索1,二叉树结点搜索1,1前序遍历搜索Java版中的数据结构和算法(4)在这篇文章中，我们在学习了二叉树的前序遍历、中序遍历和后序遍历之后，有了前面的基础，我们再来说说前序遍历搜索、中序遍历搜索和后序遍历-这篇文章中二叉树的顺序遍历搜索，这样看来这篇文章会相对容易理解很多。这里先说一下前序遍历的搜索思路：（1）先判断当前节点的值是否与要搜索的节点的值相等，如果相等，则返回当前节点;如果不是，则判断当前节点左边的子节点是否为空。(2)如果当前节点的左子节点不为空，则递归查找左子节点的前序。(3)如果左子节点的递归前序搜索能找到该节点，则返回；如果不是，则继续判断当前节点的右子节点是否为空，如果不是，则继续向右递归前序查找；if如果仍未找到整棵树，则返回null。看到这里，可能有读者会说，我还是一头雾水，没关系，这里举个例子，上面前序遍历的搜索思路会更清晰；我们先画一棵二叉树，如图1所示：图片首先，我们在图1中画的二叉树是有规则的。可以看到父节点的序号小于子节点的序号，同父节点的左子节点小于右子节点；好吧，假设我们要找到序号为5的字符，我们来列举一下查找步骤：(1)开始时，比较待查找节点的序号和根节点的序号，找到即1不等于5，所以对根节点的左子节点进行递归前序查找。(2)将根节点的左子节点的序号（序号为2）与要查找的节点的序号进行比较，发现2不等于5，所以左子节点的序号为2（序号为4）的节点递归前序搜索。(3)将节点序号(序号4)与待查找节点序号进行比较，发现4不等于5，则发现序号为4的节点为叶子节点，所以结束序号为4阶的节点的递归遍历。(4)至此，序号为2的节点的左子节点的递归前序查找已经结束，所以对序号为2的节点的右子节点进行递归前序查找（序号为5)找到了，序号为2的节点的右子节点的序号等于要查找的节点的序号，最后序号为2的节点的右子节点为返回，搜索结束。假设我们要在前序中查找一个不存在的字符？例如对于序号为8的人，其查找思路与查找序号为5的节点是一样的，只是查找序号为5的节点不需要遍历图中的整棵树1来查找，但是查找序号为8的节点需要遍历图1中的整棵树来查找，这里就不列出序号为8的字符的前序遍历查找思路了。好吧，我们这里用代码来实现一下，使用前序遍历来查找序号为5和序号为8的字符；(1)写一个节点类FigureNode:publicclassFigureNode{privateintno;私有字符串名称；私有FigureNode离开；私有FigureNode权；publicFigureNode(intno,Stringname){super();this.no=no;this.name=name;}publicStringgetName(){returnname;}publicintgetNo(){returnno;}publicFigureNodegetLeft(){向左返回；}publicvoidsetLeft(FigureNodeleft){this.left=left;}publicFigureNodegetRight(){向右返回；}publicvoidsetRight(FigureNoderight){this.right=right;}}(2)编写测试类Test:publicclassTest{privateFigureNoderoot;publicstaticvoidmain(String[]args){Testtest=newTest();test.createBinaryTree();test.preOrderSeach(5);System.out.println("******************");test.preOrderSeach(8);}//创建二叉树privatevoidcreateBinaryTree(){FigureNodefigureNode=newFigureNode(1,"如来佛");FigureNodefigureNode2=newFigureNode(2,"观音菩萨");FigureNodefigureNode3=newFigureNode(3,"牛魔王");FigureNodefigureNode4=newFigureNode(4,"孙悟空");FigureNodefigureNode5=newFigureNode(5,"猪八戒");FigureNodefigureNode6=newFigureNode(6,"红Boy");FigureNodefigureNode7=newFigureNode(7,"铁扇公主");root=figureNode;//根节点的图形为如来佛祖root.setLeft(figureNode2);//根的左子节点node是序号为2的节点root.setRight(figureNode3);//根节点的右子节点是序号为3的节点figureNode2.setLeft(figureNode4);//序号为2的左子节点是序号为4的节点figureNode2.setRight(figureNode5);//序号为2的右子节点为序号为5的节点figureNode3.setLeft(figureNode6);//序号为3的左子节点为序号为6的节点figureNode3.setRight(figureNode7);//序号为3右子节点为序号为7的节点}//前序遍历查找，以根节点为当前节点查找privatevoidpreOrderSeach(intno){if(root!=null){System.out.println("预序遍历搜索");FigureNoderesult=preOrderSeach(root,no);if(result==null){System.out.println("没有序号为"+no+"的图");}else{系统输出。println("我找到了序号为"+no+"的人，他(她)是"+result.getNa我（））;}}else{System.out.println("Thisisanemptybinarytree");}}//前序遍历寻找privateFigureNodepreOrderSeach(FigureNodenode,intno){if(node.getNo()==no){//比较当前节点returnnode;}FigureNoderes=null;//判断当前节点的左子节点是否为空if(node.getLeft()!=null){//左递归前res=preOrderSeach(node.getLeft(),no);//递归前序搜索}//如果不为空，则表示在“左递归前序搜索”时找到了该节点if(res!=null){returnres;}//当前节点的右子节点是否为空if(node.getRight()!=null){//右递归前序搜索res=preOrderSeach(node.getRight(),no);}//如果是不为空，则表示在“右递归前序搜索”时找到了节点returnres;}}程序运行结果如下：图1、2中序遍历找到的搜索思路前序遍历：（1）判断当前节点（假设A节点）的左子节点是否为空，如果不为空则进行递归中序查找（2）如果当前节点的左子节点递归中序（假设A节点）如果搜索到，返回；如果没有找到，则与当前节点（假设为A节点）进行比较，如果是则返回当前节点，否则判断当前节点（假设为A节点）的右子节点是否为空。(3)如果当前节点(假设A节点)的右子节点不为空，则对当前节点(假设A节点)的右子节点进行递归中序查找；if当前节点的右孩子（假设为A节点）如果已经找到该节点的递归中序搜索则返回；如果仍未找到整棵树，则返回null。这里举个例子，利用图1中的二叉树进行中序遍历查找。假设我要找序号为7的字符和序号为8的字符，这里我只写序号为7的字符的搜索思路，序号为8的字符的搜索思路是与查找序号为7的字符相同。有兴趣的读者可以自行分析查找序号为8的字符的思路。好了，我们现在开始分析和查找序列号。字符7的思路：（1）一开始，看到序号为1的根节点，发现根节点的左子节点不为空，然后进行一次中序遍历到根节点（序号为2）的左子节点找到。(2)发现序号为2的节点左子节点不为空，对序号为2的节点左子节点进行中序遍历查找（序号为4).(3)如果发现序号为4的节点是叶子节点，则将叶子节点的序号与待查找节点的序号进行比较。4不等于7，所以序号为2的节点的左子节点的递归顺序遍历已经结束。(4)此时将序号为2的节点的序号与要查找的节点的序号进行比较，2不等于7，则判断序号为2的节点的右子节点是否为number为2为空，不为空则重新进行序号递归中序遍历查找2的右子节点（编号为5）。(5)如果发现序号为5的节点是叶子节点，则将序号为5的节点的序号与待查找节点的序号进行比较，5不等于7，而序号为2的节点的右子节点的递归中序遍历搜索结束，根节点（序号为2）的左子节点的递归中序遍历搜索也结束。(6)此时比较根节点的序号和待查找节点的序号。1不等于7，所以判断根节点的右孩子节点是否为空，如果不为空，则再次检查根节点的右孩子节点。递归中序遍历搜索子节点（编号3）。(7)发现序号为3的节点的左子节点不为空，然后递归中序遍历查找序号为3的节点的左子节点（序号为6).(8)发现序号为6的节点是叶子节点，于是比较叶子节点的序号和要查找的节点的序号，6不等于7，此时，序号为3的节点的左子节点的递归中序遍历搜索结束，然后将序号为3的节点的序号与待搜索节点的序号进行比较，3不等于7。(9)此时判断序号为3的节点的右子节点是否为空，发现不为空，对右进行递归中序遍历查找序号为3（序号为7）的节点的子节点。(10)发现序号为7的节点是叶子节点，于是将叶子节点的序号与待查找节点的序号进行比较，发现7等于7，返回叶节点，整个搜索过程结束。那么，对于图1中二叉树中序号为7和8的字符的中序遍历查找，我们同样用代码实现一个：(1)我们继续使用上面的节点类FigureNode进行预顺序遍历搜索，这里我们只需要在序号中添加一个测试类Test2即可：publicclassTest2{privateFigureNoderoot;publicstaticvoidmain(String[]args){Test2test=newTest2();test.createBinaryTree();test.infixOrderSearch(7);System.out.println("******************");test.infixOrderSearch(8);}//创建二叉树privatevoidcreateBinaryTree(){FigureNodefigureNode=newFigureNode(1,"如来佛");FigureNodefigureNode2=newFigureNode(2,"观音菩萨");FigureNodefigureNode3=newFigureNode(3,"牛魔王");FigureNodefigureNode4=newFigureNode(4,"孙悟空");FigureNodefigureNode5=newFigureNode(5,"猪八戒");FigureNodefigureNode6=newFigureNode(6,"红孩儿");FigureNodefigureNode7=newFigureNode(7,"铁扇公主");root=figureNode;//根节点的字符为如来佛root.setLeft(figureNode2);//根节点的左子节点为序号为2的节点root.setRight(figureNode3);//右子节点的子节点根节点是序号为3的节点figureNode2.setLeft(figureNode4);//序号为2的左子节点是序号为4的节点figureNode2.setRight(figureNode5);//序号为2的右子节点是序号为5的节点figureNode3.setLeft(figureNode6);//序号为3的左子节点是序号为6的节点figureNode3.setRight(figureNode7);//序号为3的右子节点为序号为7的节点}//中序遍历查找，以根节点为当前节点查找privatevoidinfixOrderSearch(intno){if(root!=null){System.out.println("中序遍历查找");FigureNoderesult=infixOrderSearch(root,no);if(result==null){System.out.println("没有序列号是"+no+"字符");}else{System.out.println("找到序号为"+no+"的角色，他(她)是"+result.getName());}}else{系统输出。println("Thisisanemptybinarytree");}}//中序遍历寻找privateFigureNodeinfixOrderSearch(FigureNodenode,intno){FigureNoderes=null;//判断当前节点的左子节点是否为空if(node.getLeft()!=null){//左递归中序搜索找到一个节点并返回res=infixOrderSearch(node.getLeft(),no);}//如果不为空，则表示“左递归”inordersearch"找到节点if(res!=null){returnres;}if(node.getNo()==no){//比较当前节点returnnode;}//是否为当前的右子节点如果(node.getRight()!=null)节点为空{//右递归中序搜索res=infixOrderSearch(node.getRight(),no);}//如果不为空，则表示在“右递归中序搜索”中找到了节点returnres;}}程序运行结果如下图：图1和图3后序遍历搜索前序遍历的搜索思路：（1）判断当前节点（假设A节点）的左子节点是否为空,如果没有则递归后序查找(2)如果通过递归后序遍历已经找到当前节点（假设为A节点）的左子节点，则返回；如果递归后序遍历没有找到当前节点（假设A节点）的左子节点，则判断当前节点（假设A节点）右子节点是否为空，如果不为空，则递归后序遍历顺序遍历寻找当前节点（假设为A节点）的右子节点，找到则返回。(3)如果通过递归后序遍历仍然没有找到当前节点（假设为A节点）的右子节点，则与当前节点进行比较，找到则返回；如果后序遍历找到了二叉树，还是没有找到，则返回null。好吧，举个例子，用图1的二叉树进行后序遍历查找，假设我要找的是序号为6的字符和序号为8的字符，我就不写了关于序号为8的字符的查找思路，我只写了序号为6的后序遍历查找思路；(1)一开始我们看到根节点（序号为1），先判断根节点的左子节点是否为空，发现不为空，于是进行递归后序遍历查找根节点的左子节点（编号2）。(2)然后判断序号为2的节点的左子节点是否为空，发现不为空，对序号为2的节点的左子节点进行递归后序遍历查找2（序号为4）。(3)发现序号为4的节点是叶子节点，所以比较叶子节点的序号和待查找节点的序号。4不等于6，此时序号为2的节点的左子节点的递归后序遍历查找结束。(4)判断序号为2的节点的右子节点是否为空，发现不为空，则对序号为2的节点的右子节点进行递归后序遍历查找（序号为5）。(5)发现序号为5的节点是叶子节点，于是将叶子节点的序号与待查找节点的序号进行比较，5不等于6。(6)此时序号为2的节点的右子节点的递归后序遍历搜索已经结束，所以将序号为2的节点的序号与该节点的序号进行比较被查找到，2不等于6。(7)此时对根节点的左子节点的递归后序遍历查找已经结束，判断是否是根节点的右子节点为空，且不为空，所以根节点的右子节点（序号为3）递归后序遍历查找。(8)判断序号为3的左子节点是否为空，发现不为空，则对序号为3的节点的左子节点(序号为6)进行递归后序遍历查找.(9)发现序号为6的节点是叶子节点，于是将叶子节点的序号与要查找的序号进行比较，7等于7，然后返回叶子节点，并结束整个递归后序搜索。那么对于图1中二叉树中序号为6和8的字符的后序遍历查找，我们还是用代码来实现：(1)我们继续使用上面的节点类FigureNode进行前序遍历查找，这里我们只是在序号中添加了一个测试类Test3：publicclassTest3{privateFigureNoderoot;publicstaticvoidmain(String[]args){Test3test=newTest3();test.createBinaryTree();test.postOrderSearch(6);System.out.println("*****************");test.postOrderSearch(8);}//创建二叉树privatevoidcreateBinaryTree(){FigureNodefigureNode=newFigureNode(1,"Buddha");FigureNodefigureNode2=newFigureNode(2,"Avalokitesvara");FigureNodefigureNode3=newFigureNode(3,"佛祖");FigureNodefigureNode4=newFigureNode(4,"孙悟空");FigureNodefigureNode5=newFigureNode(5,"猪八戒");FigureNodefigureNode6=newFigureNode(6,"红孩儿");FigureNodefigureNode7=newFigureNode(7,"铁扇公主");root=figureNode;//根节点的字符为佛root.setLeft(figureNode2);//根节点的左子节点为序号为2的节点root.setRight(figureNode3);//的右子节点根节点是序号为3的节点NodefigureNode2.setLeft(figureNode4);//序号为2的左子节点为序号为4的节点figureNode2.setRight(figureNode5);//序号为2的右子节点为序号为5的节点figureNode3.setLeft(figureNode6);//序号为3的左子节点为序号为6的节点figureNode3.setRight(figureNode7);//序号为3的右子节点为序号为7的节点}//后序遍历查找，with根节点作为当前节点进行搜索privatevoidpostOrderSearch(intno){if(root!=null){System.out.println("后序遍历搜索");FigureNoderesult=postOrderSearch(root,no);if(result==null){System.out.println("没有序列号的字符"+no+"");}else{System.out.println("找到序号为"+no+"的字符，他(她)是"+result.getName());}}else{System.out.println("Thisisanemptybinarytree");}}//后序遍历找到privateFigureNodepostOrderSearch(FigureNodenode,intno){FigureNoderes=null;//判断current节点的左子节点是否为空if(node.getLeft()!=null){//左递归后序搜索找到节点并返回res=postOrderSearch(node.getLeft(),no);}//IfnotEmpty表示在“左递归后序查找”时找到该节点if(res!=null){returnres;}//当前节点的右子节点是否为空if(node.getRight()!=null){//右递归后序搜索res=postOrderSearch(node.getRight(),no);}//如果不为空，则表示在“右递归后序搜索”时找到了该节点if(res!=null){returnres;}if(node.getNo()==no){//比较当前节点returnnode;}returnres;}}程序运行结果如下：图片总结：从当前来看，用于post的比较次数-顺序遍历搜索最少，推荐使用后序遍历搜索，有兴趣的读者可以试验一下
