构造二叉树
所构造的二叉树如图所示：
前中序概念
定义是根据输出父节点的顺序而定的：
前序：先输出父节点，接着输出左节点，最后输出右节点。
中序：先输出左节点，接着输出父节点，最后输出右节点。
后序：先输出左节点，接着输出右节点，最后输出父节点。
前序遍历-查找-图示
输出：
代码：
public void listTreeByPre(HeroNode node) {
if (null == node) {
return;
}
System.out.print(node.getName() + "->");
if (null != node.leftNode) {
listTreeByPre(node.leftNode);
}
if (null != node.rightNode) {
listTreeByPre(node.rightNode);
}
}
中序遍历-查找 图示
输出：
代码：
public void listTreeByInfix(HeroNode node) {
if (null == node) {
return;
}
if (null != node.leftNode) {
listTreeByInfix(node.leftNode);
}
System.out.print(node.getName() + "->");
if (null != node.rightNode) {
listTreeByInfix(node.rightNode);
}
}
后序遍历-查找 图示
输出：
代码；
public void listTreeByPost(HeroNode node) {
if (null == node) {
return;
}
if (null != node.leftNode) {
listTreeByPost(node.leftNode);
}
if (null != node.rightNode) {
listTreeByPost(node.rightNode);
}
System.out.print(node.getName() + "->");
}
层次遍历
安树层输出
输出：
代码：
public void listTreeByLevel(HeroNode node) {
if (null != node) {
LinkedList<HeroNode> list = new LinkedList<HeroNode>();
list.add(node);
HeroNode currentNode;
while (!list.isEmpty()) {
currentNode = list.poll();
System.out.print(currentNode.getName() + "->");
if (null != currentNode.leftNode) {
list.add(currentNode.leftNode);
}
if (null != currentNode.rightNode) {
list.add(currentNode.rightNode);
}
}
}
}
全部代码：
BinaryTree.java
package com.dove.tree;
import java.util.LinkedList;
/**
* 二叉树
* date: 2021年7月15日10:52:14
*/
public class BinaryTree {
public HeroNode creatTree() {
HeroNode heroNode1 = new HeroNode(1, "A");
HeroNode heroNode2 = new HeroNode(2, "B");
HeroNode heroNode3 = new HeroNode(3, "C");
HeroNode heroNode4 = new HeroNode(4, "D");
HeroNode heroNode5 = new HeroNode(5, "E");
HeroNode heroNode6 = new HeroNode(6, "F");
HeroNode heroNode7 = new HeroNode(7, "G");
HeroNode heroNode8 = new HeroNode(8, "H");
HeroNode heroNode9 = new HeroNode(9, "I");
HeroNode heroNode10 = new HeroNode(10, "J");
HeroNode heroNode11 = new HeroNode(11, "K");
heroNode1.leftNode = heroNode2;
heroNode1.rightNode = heroNode3;
heroNode2.leftNode = heroNode4;
heroNode2.rightNode = heroNode5;
heroNode3.leftNode = heroNode6;
heroNode3.rightNode = heroNode7;
heroNode4.leftNode = heroNode8;
heroNode5.rightNode = heroNode9;
heroNode6.leftNode = heroNode10;
heroNode7.rightNode = heroNode11;
HeroNode rootNode = heroNode1;
return rootNode;
}
/**
* 前序遍历
*
* @param node
*/
public void listTreeByPre(HeroNode node) {
if (null == node) {
return;
}
System.out.print(node.getName() + "->");
if (null != node.leftNode) {
listTreeByPre(node.leftNode);
}
if (null != node.rightNode) {
listTreeByPre(node.rightNode);
}
}
/**
* 遍历树，中序
*
* @param node
*/
public void listTreeByInfix(HeroNode node) {
if (null == node) {
return;
}
if (null != node.leftNode) {
listTreeByInfix(node.leftNode);
}
System.out.print(node.getName() + "->");
if (null != node.rightNode) {
listTreeByInfix(node.rightNode);
}
}
/**
* 后序编列
*
* @param node
*/
public void listTreeByPost(HeroNode node) {
if (null == node) {
return;
}
if (null != node.leftNode) {
listTreeByPost(node.leftNode);
}
if (null != node.rightNode) {
listTreeByPost(node.rightNode);
}
System.out.print(node.getName() + "->");
}
/**
* 层次遍历
*/
public void listTreeByLevel(HeroNode node) {
if (null != node) {
LinkedList<HeroNode> list = new LinkedList<HeroNode>();
list.add(node);
HeroNode currentNode;
while (!list.isEmpty()) {
currentNode = list.poll();
System.out.print(currentNode.getName() + "->");
if (null != currentNode.leftNode) {
list.add(currentNode.leftNode);
}
if (null != currentNode.rightNode) {
list.add(currentNode.rightNode);
}
}
}
}
/**
* 前序查找 根据ID
*
* @param node
* @param aimID
* @return
*/
public HeroNode findByIDByPre(HeroNode node, int aimID) {
if (null == node) {
return null;
}
HeroNode resNode = null;
if (node.getId() == aimID) {
return node;
}
if (null != node.leftNode) {
resNode = findByIDByPre(node.leftNode, aimID);
}
if (null != resNode) {
return resNode;
}
if (null != node.rightNode) {
resNode = findByIDByPre(node.rightNode, aimID);
}
return resNode;
}
/**
* 中序查找，根据ID
*
* @param node
* @param aimID
* @return
*/
public HeroNode findByIDByInfix(HeroNode node, int aimID) {
if (null == node) {
return null;
}
HeroNode resNode = null;
if (null != node.leftNode) {
resNode = findByIDByInfix(node.leftNode, aimID);
}
if (null != resNode) {
return resNode;
}
if (node.getId() == aimID) {
return node;
}
if (null != node.rightNode) {
resNode = findByIDByInfix(node.rightNode, aimID);
}
return resNode;
}
/**
* 后序查找，根据ID
*
* @param node
* @param aimID
* @return
*/
public HeroNode findByIDByPost(HeroNode node, int aimID) {
if (null == node) {
return null;
}
HeroNode resNode = null;
if (null != node.leftNode) {
resNode = findByIDByPost(node.leftNode, aimID);
}
if (null != resNode) {
return resNode;
}
if (null != node.rightNode) {
resNode = findByIDByPost(node.rightNode, aimID);
}
if (null != resNode) {
return resNode;
}
if (node.getId() == aimID) {
return node;
}
return resNode;
}
}
class HeroNode {
private int id;
private String name;
public HeroNode leftNode;
public HeroNode rightNode;
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 HeroNode() {
}
public HeroNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "[id:" + this.id + "---name:" + this.name + "]";
}
}
BinaryTreeTest.java
package com.dove.tree;
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
HeroNode rootNode = binaryTree.creatTree();
System.out.println("前序遍历：");
binaryTree.listTreeByPre(rootNode);
System.out.println();
System.out.println("中序遍历:");
binaryTree.listTreeByInfix(rootNode);
System.out.println();
System.out.println("后序遍历:");
binaryTree.listTreeByPost(rootNode);
System.out.println();
System.out.println("层次遍历:");
binaryTree.listTreeByLevel(rootNode);
System.out.println();
System.out.println("前序查找");
HeroNode resNode = binaryTree.findByIDByPre(rootNode, 4);
if (null != resNode){
System.out.println(resNode.toString());
}else {
System.out.println("resNode is null");
}
System.out.println("中序查找");
resNode = binaryTree.findByIDByInfix(rootNode, 6);
if (null != resNode){
System.out.println(resNode.toString());
}else {
System.out.println("resNode is null");
}
System.out.println("后序查找");
resNode = binaryTree.findByIDByPost(rootNode, 11);
if (null != resNode){
System.out.println(resNode.toString());
}else {
System.out.println("resNode is null");
}
}
}
输出：
