[数据结构与算法]二叉树前序、中序、后序遍历（java代码实现）

二叉树前序、中序、后序遍历

定义树节点属性

包括信息，左指针和右指针（初始值为null）

class HeroNode {
	private int no;
	private String name;
	private HeroNode left; //默认null
	private HeroNode right; //默认null
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
	
}

定义树节点前序遍历方法

1. 先输出当前接单（调用该方法的结点）
2. 如果左子结点不为空，则左子节点递归继续该方法
3. 左子树遍历结束，如果右子结点不为空，则右子节点递归继续该方法

//编写前序遍历的方法
	public void preOrder() {
		System.out.println(this); //先输出父结点
		//递归向左子树前序遍历
		if(this.left != null) {
			this.left.preOrder();
		}
		//递归向右子树前序遍历
		if(this.right != null) {
			this.right.preOrder();
		}
	}

定义树节点中序遍历方法

1. 如果当前结点的左子节点不为空，则左子节点递归该方法
2. 直到下一个结点没有左节点，依次返回输出遍历过的左结点
3. 左子树遍历结束，现在返回到根节点，如果右子结点不为空，则右子节点递归继续该方法

//中序遍历
	public void infixOrder() {
		
		//递归向左子树中序遍历
		if(this.left != null) {
			this.left.infixOrder();
		}
		//输出父结点
		System.out.println(this);
		//递归向右子树中序遍历
		if(this.right != null) {
			this.right.infixOrder();
		}
	}

定义树节点后序遍历方法

1. 如果当前结点的左子节点不为空，则左子节点递归该方法
2. 如果当前结点的右子节点不为空，则右子节点递归该方法
3. 输出当前结点

//后序遍历
	public void postOrder() {
		if(this.left != null) {
			this.left.postOrder();
		}
		if(this.right != null) {
			this.right.postOrder();
		}
		System.out.println(this);
	}

定义二叉树

1. 先定义一个根节点和设置根节点的方法

2. 定义前序、中序、后序遍历树的方法

   若根节点不为空，根节点调用相应的方法

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode 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("二叉树为空，无法遍历");
		}
	}
}