要求:
思路:
前序查找:
中序查找
后续查找
package tree;
public class BinaryTreeDemo {
public static void main(String[] args) {
// 创建二叉树
BinaryTree binaryTree = new BinaryTree();
// 创建需要的节点
Node1 root = new Node1(1,"a1");
Node1 n2 = new Node1(2,"a2");
Node1 n3 = new Node1(3,"a3");
Node1 n4 = new Node1(4,"a4");
// 说明,我们先手动创建二叉树,后面使用递归创建二叉树
root.setLeft(n2);
root.setRight(n3);
n3.setRight(n4);
binaryTree.setRoot(root);
// 测试 遍历
System.out.println("前序遍历:");
binaryTree.preOrder(); // 1 2 3 4
System.out.println("中序遍历 ");
binaryTree.infixOrder(); // 2 1 3 4
System.out.println("后序遍历:");
binaryTree.postOrder(); // 2 4 3 1
// 测试查找
System.out.println("前序查找");// 前序遍历的次数 4
Node1 resNode = binaryTree.preOrderSearch(4);
if (resNode != null){
System.out.println("finded\t"+resNode.getId() + "\t" + resNode.getName());
}else{
System.out.println("Not find");
}
System.out.println("中序查找"); // 中序遍历次数 3
resNode = binaryTree.infixOrderSearch(4);
if (resNode != null){
System.out.println("finded\t"+resNode.getId() + "\t" + resNode.getName());
}else{
System.out.println("Not find");
}
System.out.println("后序查找"); // 后序遍历 2
resNode = binaryTree.postOrderSearch(4);
if (resNode != null){
System.out.println("finded\t"+resNode.getId() + "\t" + resNode.getName());
}else{
System.out.println("Not find");
}
}
}
class BinaryTree{
private Node1 root;
public Node1 getRoot() {
return root;
}
public void setRoot(Node1 root) {
this.root = root;
}
// 前序遍历
public void preOrder(){
if (this.root != null){
this.root.preOrder();
}else{
System.out.println("二叉树为空");
}
}
// 中序遍历
public void infixOrder(){
if (this.root != null){
this.root.infixOrder();
}else{
System.out.println("二叉树为空");
}
}
// 后序遍历
public void postOrder(){
if (this.root != null){
this.root.postOrder();
}else{
System.out.println("二叉树为空");
}
}
// 前序查找
public Node1 preOrderSearch(int id){
if (this.root != null){
return root.preOrdersearch(id);
}else{
return null;
}
}
// 中序查找
public Node1 infixOrderSearch(int id){
if (this.root != null){
return root.infixOrderSearch(id);
}else {
return null;
}
}
// 后序查找
public Node1 postOrderSearch(int id){
if (this.root != null){
return root.postOrderSearch(id);
} else{
return null;
}
}
}
// 先创建节点
class Node1{
private int id;
private String name;
private Node1 left;
private Node1 right;
public Node1(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node1 getLeft() {
return left;
}
public void setLeft(Node1 left) {
this.left = left;
}
public Node1 getRight() {
return right;
}
public void setRight(Node1 right) {
this.right = right;
}
@Override
public String toString() {
return "Node1{" +
"id=" + id +
", name=‘" + name + ‘\‘‘ +
‘}‘;
}
// 编写前序遍历
public void preOrder(){
System.out.println(this); // 先输出当前节点
// 递归向左子树前序遍历
if (this.left != null){
this.left.preOrder();
}
// 递归向右子树前序遍历
if (this.right != null){
this.right.preOrder();
}
}
// 编写中序遍历
public void infixOrder(){
// 递归向左子树中序遍历
if (this.left != null){
this.left.infixOrder();
}
System.out.println(this);
// 嘀咕向右子树中序遍历
if (this.right != null){
this.right.infixOrder();
}
}
// 编写后序遍历
public void postOrder(){
// 左子树后序遍历
if (this.left != null){
this.left.postOrder();
}
// 右子树后序遍历
if (this.right != null){
this.right.postOrder();
}
System.out.println(this);
}
// 前序遍历查找
/**
*
* @param id 要查找的id
* @return 若找到则返回当前Node1,如果没找到则返回null
*/
public Node1 preOrdersearch(int id){
System.out.println("进行前序遍历~~"); // 用来判断比较几次
// 比较当前节点是不是
if (this.id == id){
return this;
}
// 判断当前节点的左子树是否为空
Node1 resNode = null; // 通过res判断找没找到
if (this.left != null){
resNode = this.left.preOrdersearch(id);
}
if (resNode != null){ // 说明我们左子树找到了
return resNode;
}
// 判断当前节点的右子树是否为空
if (this.right != null){
resNode = this.right.preOrdersearch(id);
}
if (resNode != null){
return resNode;
}
return resNode;
}
// 中序查找
public Node1 infixOrderSearch(int id){
Node1 resNode = null;
// 判断左节点是否为空,如果不为空则便利左节点
if (this.left != null){
resNode = this.left.infixOrderSearch(id);
}
if (resNode != null){
return resNode;
}
System.out.println("进行中序遍历~~"); // 用来判断比较几次
// 判断当前节点是否是要找的节点,如果是则返回
if (this.id == id){
return this;
}
// 判断右子树是否为空,如果不为空,则进行右遍历
if (this.right != null){
resNode = this.right.infixOrderSearch(id);
}
if (resNode != null){
return resNode;
}
return resNode;
}
// 逆序查找
public Node1 postOrderSearch(int id){
Node1 resNode = null;
// 判断左子树是否为空,如果不为空,则进行左递归
if (this.left != null){
resNode = this.left.postOrderSearch(id);
}
if (resNode != null){
return resNode;
}
// 判断右子树是否为空,如果不为空,则进行右递归
if (this.right != null){
resNode = this.right.postOrderSearch(id);
}
if (resNode != null){
return resNode;
}
System.out.println("进行后序遍历~~"); // 用来判断比较几次
// 判断当前节点是否是要找的节点,如果是,则直接返回
if (this.id == id){
return this;
}
return resNode;
}
}
原文:https://www.cnblogs.com/sharpenblogs/p/15120469.html