二叉树的前序中序后序遍历、查找的实现（Java代码实现）

旧城等待， 2023-03-12 09:15 4阅读 0赞

在前一篇文章对二叉树进行的部分介绍：[数据结构—— 树（二叉树）详解][Link 1] 在后面当中简介了一下遍历方法，随后对遍历方法实现：  
对一棵二叉树的代码实现，首先对每一个节点定义一个节点类，节点类定义no和name，用于标识节点，以及一个左指针和右指针。这里使用私有变量private，所以需要对这些变了进行getter/setter封装。代码省略。定义构造方法，进行初始化。往下，重写toString方法，用于输出节点信息。最后就是对前序中序后序的方法实现。

class Node { 
    	private int no;
    	private String name;
    	private Node left;
    	private Node right;
    	//构造方法
    	public Node(int no, String name) { 
    		this.no = no;
    		this.name = name;
    	}
    	@Override
    	public String toString() { 
    		return "Node[ no = " + no + ", name =" + name + " ]";
    	}
    	// 前序遍历
    	public void DLR() { 
    		System.out.println(this);// 先输出根节点
    		// 左子树递归
    		if (this.left != null) { 
    			this.left.DLR();
    		}
    		// 右子树递归
    		if (this.right != null) { 
    			this.right.DLR();
    		}
    	}
    
    	// 中序遍历
    	public void LDR() { 
    		// 左子树递归
    		if (this.left != null) { 
    			this.left.LDR();
    		}
    		System.out.println(this);// 先输出根节点
    		// 右子树递归
    		if (this.right != null) { 
    			this.right.LDR();
    		}
    	}
    
    	// 后序遍历
    	public void LRD() { 
    		// 左子树递归
    		if (this.left != null) { 
    			this.left.LRD();
    		}
    		// 右子树递归
    		if (this.right != null) { 
    			this.right.LRD();
    		}
    		System.out.println(this);// 先输出根节点
    	}
    }

节点定义好了之后，需要定义一个二叉树类，用于将节点进行连接起来。以及调用前面的排序方法即可。

class Binarytree { 
    	private Node root;
    
    	public void setRoot(Node root) { 
    		this.root = root;
    	}
    
    	// 前序
    	public void DLR() { 
    		if (this.root != null) { 
    			this.root.DLR();
    		} else { 
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    
    	// 中序
    	public void LDR() { 
    		if (this.root != null) { 
    			this.root.LDR();
    		} else { 
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    
    	// 后序
    	public void LRD() { 
    		if (this.root != null) { 
    			this.root.LRD();
    		} else { 
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    }

定义测试类，其中使用一个二叉树作为测试  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
首先需要实例化一个二叉树类，随后声明节点，把节点和root进行绑定形成二叉树。最后调用方法即可

Binarytree bt = new Binarytree();
    		Node root = new Node(1, "one"); //node1
    		Node node2 = new Node(2, "two");
    		Node node3 = new Node(3, "three");
    		Node node4 = new Node(4, "four");
    		bt.setRoot(root);
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		System.out.println("前序："); //1 2 3 4
    		bt.DLR();
    		System.out.println("中序："); // 2 1 3 4
    		bt.LDR();
    		System.out.println("后序："); // 2 4 3 1
    		bt.LRD();

运行代码如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
查找节点方法

**思路分析**

前序查找思路

1.  先判断当前结点的no是否等于要查找的
2.  如果是相等，则返回当前结点
3.  如果不等，则判断当前结点的左子节点是否为空，如果不为空,则递归前序查找
4.  如果左递归前序查找，找到结点，则返回，否继续判断，当前的结点的右子节点是否为空,如果不空，则继续向右递归前序查找.

中序查找思路

1.  判断当前结点的左子节点是否为空,如果不为空,则递归中序查找
2.  如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点，否则继续进行右递归的中序查找
3.  如果右递归中序查找，找到就返回，否则返回null

后序查找思路

1.  判断当前结点的左子节点是否为空,如果不为空，则递归后序查找
2.  如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空,如果不为空，则右递归进行后序查找，如果找到，就返回
3.  就和当前结点进行，比如，如果是则返回，否则返回ull

在前文的基础上，首先在Node节点类添加查找方法

// 前序查找,根据no编号查找,找到返回节点,反之返回null
    	public Node DLRsearch(int no) { 
    		if (this.no == no) { 
    			return this;
    		}
    		Node resNode = null;
    		if (this.left != null) { 
    			resNode = this.left.DLRsearch(no);
    		}
    		if (resNode != null) { 
    			return resNode;
    		}
    		if (this.right != null) { 
    			resNode = this.right.DLRsearch(no);
    		}
    		return resNode;
    	}
    
    	// 中序遍历查找
    	public Node LDRsearch(int no) { 
    		Node resNode = null;
    		if (this.left != null) { 
    			resNode = this.left.LDRsearch(no);
    		}
    		if (resNode != null) { 
    			return resNode;
    		}
    		if (this.no == no) { 
    			return this;
    		}
    		if (this.right != null) { 
    			resNode = this.right.LDRsearch(no);
    		}
    		return resNode;
    	}
    
    	// 后序遍历查找
    	public Node LRDsearch(int no) { 
    		Node resNode = null;
    		if (this.left != null) { 
    			resNode = this.left.LRDsearch(no);
    		}
    		if (resNode != null) { 
    			return resNode;
    		}
    		if (this.right != null) { 
    			resNode = this.right.LRDsearch(no);
    		}
    		if (resNode != null) { 
    			return resNode;
    		}
    		if (this.no == no) { 
    			return this;
    		}
    		return resNode;
    	}

在Binarytree二叉树类当中定义对应调用的方法

// 前序查找
    	public Node DLRsearch(int no) { 
    		if (root != null) { 
    			return root.DLRsearch(no);
    		} else { 
    			return null;
    		}
    	}
    
    	// 中序查找
    	public Node LDRsearch(int no) { 
    		if (root != null) { 
    			return root.LDRsearch(no);
    		} else { 
    			return null;
    		}
    	}
    
    	// 后序查找
    	public Node LRDsearch(int no) { 
    		if (root != null) { 
    			return root.LRDsearch(no);
    		} else { 
    			return null;
    		}
    	}

最后进行测试：查找节点

System.out.println("前序查找");
    		Node res = bt.DLRsearch(2);
    		if (res != null) { 
    			System.out.println("找到这个节点，no = " + res.getNo() + " , name = " + res.getName());
    		} else { 
    			System.out.println("没有找到这个节点");
    		}
    		System.out.println("中序查找");
    		res = bt.LDRsearch(5);
    		if (res != null) { 
    			System.out.println("找到这个节点，no = " + res.getNo() + " , name = " + res.getName());
    		} else { 
    			System.out.println("没有找到这个节点");
    		}
    		System.out.println("后序查找");
    		res = bt.LRDsearch(4);
    		if (res != null) { 
    			System.out.println("找到这个节点，no = " + res.getNo() + " , name = " + res.getName());
    		} else { 
    			System.out.println("没有找到这个节点");
    		}

运行代码，2和4可以找到，而没有5这个节点，5是找不到的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
删除节点方法

规定

1.  如果删除的节点是叶子节点，则删除该节点
2.  如果删除的节点是非叶子节点，则删除该子树.

**思路分析**  
首先先处理：考虑如果树是空树root,如果只有- -个root结点，则等价将二叉树置空  
然后进行下面步骤

1.  因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点
2.  如果当前结点的左子结点不为空，并且左子结点就是要删除结点,就将this.left=null；并且就返回(结束递归删除)
3.  如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null；并且就返回(结束递归删除)
4.  如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
5.  如果第4步也没有删除结点,则应当向右子树进行递归删除.

**代码实现**

在Node节点类当中添加删除节点的方法

// 删除节点
    	public void delete(int no) { 
    	//从左节点开始判断是不是索要删除的节点。
    		if (this.left != null && this.left.no == no) { 
    			this.left = null;
    			return;
    		}
    	//随后同理,判断有节点是不是要删除的节点
    		if (this.right != null && this.right.no == no) { 
    			this.right = null;
    			return;
    		}
    		// 向左子树进行递归
    		if (this.left != null) { 
    			this.left.delete(no);
    		}
    		// 向右子树递归
    		if (this.right != null) { 
    			this.right.delete(no);
    		}
    	}

再从二叉树类当中定义对应的删除方法

//删除节点
    	public void delete(int no) { 
    		if (root!=null) { 
    			if (root.getNo()==no) { 
    				root=null;
    			}else { 
    				root.delete(no);
    			}
    		}else { 
    			System.out.println("空树，不能删除");
    		}
    	}

进行测试  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]

[Link 1]: https://blog.csdn.net/qq_44973159/article/details/106124973
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/70da453a78d44d6982187a71b9afb201.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230312/fa5fade36b0b4d83adf89d59e39d5d7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: /images/20230312/fa5daeacee6545ba8a368b832e267afd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]: /images/20230312/1aedef6dfbe3440d91786034c8f54686.png