共计 8742 个字符，预计需要花费 22 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、二叉树的节点查找
1、1 前序遍历查找
1、2 中序遍历查找
1、3 后序遍历查找
1、二叉树的节点查找
1、1 前序遍历查找
在 Java 版的数据结构和算法（四）这篇文章中，咱们学了二叉树的前序遍历、中序遍历和后序遍历，有了后面的根底，本篇文章咱们就来说说二叉树的前序遍历查找、中序遍历查找和后序遍历查找，那么看起这篇文章来就会绝对好了解很多。
这里咱们先说说前序遍历的查找思路：
（1）先判断以后结点的数值是否等于要查找节点的数值，如果相等，则返回以后结点；如果不相等，则判断以后结点的左子节点是否为空。
（2）如果以后节点的左子节点不为空，则向左子节点递归前序查找。
（3）如果左子节点递归前序查找能找到该结点，则返回；否持续判断，以后的结点的右子节点是否为空，如果不空，则持续向右递归前序查找；如果查找完一整棵树还是没有找到，则返回 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：
public class FigureNode {
private int no;
private String name;
private FigureNode left;
private FigureNode right;
public FigureNode(int no, String name) {
super();
this.no = no;
this.name = name;}
public String getName() {
return name;}
public int getNo() {
return no;}
public FigureNode getLeft() {
return left;}
public void setLeft(FigureNode left) {
this.left = left;}
public FigureNode getRight() {
return right;}
public void setRight(FigureNode right) {
this.right = right;}
}
（2）写一个测试类 Test：
public class Test {
private FigureNode root;
public static void main(String[] args) {
Test test = new Test();
test.createBinaryTree();
test.preOrderSeach(5);
System.out.println("*****************");
test.preOrderSeach(8);}
// 创立一棵二叉树
private void createBinaryTree() {
FigureNode figureNode = new FigureNode(1,"如来佛祖");
FigureNode figureNode2 = new FigureNode(2,"观音菩萨");
FigureNode figureNode3 = new FigureNode(3,"牛魔王");
FigureNode figureNode4 = new FigureNode(4,"孙悟空");
FigureNode figureNode5 = new FigureNode(5,"猪八戒");
FigureNode figureNode6 = new FigureNode(6,"红孩儿");
FigureNode figureNode7 = new FigureNode(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 的节点 }
// 前序遍历查找, 以根节点为以后节点进行查找
private void preOrderSeach(int no) {
if (root != null) {System.out.println("前序遍历查找");
FigureNode result = preOrderSeach(root, no);
if (result == null) {System.out.println("没有序号为" + no + "的人物");
} else {
System.out.println("找到了序号为" + no + "的人物，他（她）是"
+ result.getName());
}
} else {System.out.println("这是一棵空的二叉树");
}}
// 前序遍历查找
private FigureNode preOrderSeach(FigureNode node, int no) {
if (node.getNo() == no) {// 比拟以后节点
return node;
}
FigureNode res = null;
// 判断以后节点的左子节点是否为空
if (node.getLeft() != null) {
// 左递归前序查找 找到节点 则返回
res = preOrderSeach(node.getLeft(), no);// 递归前序查找
}
// 如果不为空阐明进行“左递归前序查找”时查找到了该节点
if (res != null) {return res;}
// 以后的结点的右子节点是否为空
if (node.getRight() != null) {
// 右递归前序查找
res = preOrderSeach(node.getRight(), no);
}
// 如果不为空阐明进行“右递归前序查找”时查找到了该节点
return res;}
}
程序运行后果如下所示：
图片
1、2 中序遍历查找
前序遍历的查找思路：
（1）判断以后结点（假如 A 节点）的左子节点是否为空，如果不为空，则递归中序查找。
（2）如果以后节点（假如 A 节点）的左子节点的递归中序查找曾经找到，则返回；如果没有找到，就和以后节点（假如 A 节点）比拟，如果是则返回以后结点，否则判断以后节点（假如 A 节点）的右子节点是否为空。
（3）如果以后节点（假如 A 节点）的右子节点是不为空，则进行以后节点（假如 A 节点）的右子节点的递归中序查找；如果以后节点（假如 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 的节点右子节点是否为空，发现不为空，又进行序号为 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 即可：
public class Test2 {
private FigureNode root;
public static void main(String[] args) {
Test2 test = new Test2();
test.createBinaryTree();
test.infixOrderSearch(7);
System.out.println("*****************");
test.infixOrderSearch(8);}
// 创立一棵二叉树
private void createBinaryTree() {
FigureNode figureNode = new FigureNode(1,"如来佛祖");
FigureNode figureNode2 = new FigureNode(2,"观音菩萨");
FigureNode figureNode3 = new FigureNode(3,"牛魔王");
FigureNode figureNode4 = new FigureNode(4,"孙悟空");
FigureNode figureNode5 = new FigureNode(5,"猪八戒");
FigureNode figureNode6 = new FigureNode(6,"红孩儿");
FigureNode figureNode7 = new FigureNode(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 的节点 }
// 中序遍历查找, 以根节点为以后节点进行查找
private void infixOrderSearch(int no) {
if (root != null) {System.out.println("中序遍历查找");
FigureNode result = infixOrderSearch(root, no);
if (result == null) {System.out.println("没有序号为" + no + "的人物");
} else {
System.out.println("找到了序号为" + no + "的人物，他（她）是"
+ result.getName());
}
} else {System.out.println("这是一棵空的二叉树");
}}
// 中序遍历查找
private FigureNode infixOrderSearch(FigureNode node, int no) {
FigureNode res = null;
// 判断以后节点的左子节点是否为空
if (node.getLeft() != null) {
// 左递归中序查找 找到节点 则返回
res = infixOrderSearch(node.getLeft(), no);
}
// 如果不为空阐明进行“左递归中序查找”时查找到了该节点
if (res != null) {return res;}
if (node.getNo() == no) {// 比拟以后节点
return node;
}
// 以后的结点的右子节点是否为空
if (node.getRight() != null) {
// 右递归中序查找
res = infixOrderSearch(node.getRight(), no);
}
// 如果不为空阐明进行“右递归中序查找”时查找到了该节点
return res;}
}
程序运行后果如下所示：
图片
1、3 后序遍历查找
前序遍历的查找思路：
（1）判断以后结点（假如 A 节点）的左子节点是否为空，如果不为空，则递归后序查找。
（2）如果递归后序遍历查找以后结点（假如 A 节点）的左子节点曾经找到，就返回；如果递归后序遍历查找以后结点（假如 A 节点）的左子节点没有找到，那么就判断以后结点（假如 A 节点）的右子节点是否为空, 如果不为空，则递归后序遍历查找以后结点（假如 A 节点）的右子节点，如果找到，就返回。
（3）如果递归后序遍历查找以后结点（假如 A 节点）的右子节点还是没有找到，就和以后节点进行比拟，如果找到则返回；如果后序遍历查找完一棵二叉树还是没有找到，则返回 null。
好，咱们也举个例子，用图 1 的二叉树进行后序遍历查找，假如我要找的是序号为 6 的人物和序号为 8 的人物，序号为 8 的人物查找思路我就不写了，我只写序号为 6 的后序遍历查找思路；
（1）一开始咱们看到的是根节点（序号为 1），先判断根节点的左子节点是否为空，发现不为空，于是进行根节点的左子节点（序号为 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 即可：
public class Test3 {
private FigureNode root;
public static void main(String[] args) {
Test3 test = new Test3();
test.createBinaryTree();
test.postOrderSearch(6);
System.out.println("*****************");
test.postOrderSearch(8);}
// 创立一棵二叉树
private void createBinaryTree() {
FigureNode figureNode = new FigureNode(1, "如来佛祖");
FigureNode figureNode2 = new FigureNode(2, "观音菩萨");
FigureNode figureNode3 = new FigureNode(3, "牛魔王");
FigureNode figureNode4 = new FigureNode(4, "孙悟空");
FigureNode figureNode5 = new FigureNode(5, "猪八戒");
FigureNode figureNode6 = new FigureNode(6, "红孩儿");
FigureNode figureNode7 = new FigureNode(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 的节点 }
// 后序遍历查找, 以根节点为以后节点进行查找
private void postOrderSearch(int no) {
if (root != null) {System.out.println("后序遍历查找");
FigureNode result = postOrderSearch(root, no);
if (result == null) {System.out.println("没有序号为" + no + "的人物");
} else {
System.out.println("找到了序号为" + no + "的人物，他（她）是"
+ result.getName());
}
} else {System.out.println("这是一棵空的二叉树");
}}
// 后序遍历查找
private FigureNode postOrderSearch(FigureNode node, int no) {
FigureNode res = null;
// 判断以后节点的左子节点是否为空
if (node.getLeft() != null) {
// 左递归后序查找 找到节点 则返回
res = postOrderSearch(node.getLeft(), no);
}
// 如果不为空阐明进行“左递归后序查找”时查找到了该节点
if (res != null) {return res;}
// 以后的结点的右子节点是否为空
if (node.getRight() != null) {
// 右递归后序查找
res = postOrderSearch(node.getRight(), no);
}
// 如果不为空阐明进行“右递归后序查找”时查找到了该节点
if (res != null) {return res;}
if (node.getNo() == no) {// 比拟以后节点
return node;
}
return res;}
}
程序运行后果如下所示：
图片
小结：从目前来看后序遍历查找所用的比拟次数是起码的，举荐应用后序遍历查找，有趣味的读者能够试验一把。
