二叉树的遍历
二叉树的遍历分为三种：前序，后序，后序
1）前序遍历：先输出父节点，在输出左子树和右子树。
2）中序遍历：先输出左子树，再输出父节点，最后输出右子树。
3）后序遍历：先输出左子树，再输出右子树，最后输出父节点。
二叉树的遍历，根据父节点的输出顺序，判断哪种类型的遍历。
遍历二叉树
前序遍历：
1）先输出当前节点（最初为根节点）
2）如果当前节点的左子树不为空的话，递归进入左子树前序遍历
3）如果当前节点的右子树不为空的话，递归进入右子树前序遍历
中序遍历：
1）如果当前节点的左子树不为空的话，递归进入左子树前序遍历
2）先输出当前节点（最初为根节点）
3）如果当前节点的右子树不为空的话，递归进入右子树前序遍历
后序遍历：
1）如果当前节点的左子树不为空的话，递归进入左子树前序遍历
2）如果当前节点的右子树不为空的话，递归进入右子树前序遍历
3）先输出当前节点（最初为根节点）
查找指定节点
前序遍历查找：
1）先判断当前节点是否为要查找的节点。
2）如果是需要查找的节点，则返回当前节点。
3）如果不是需要查找的节点，则判断左子树是否为null，不是的话，递归前序查找。
4）如果左子树找到需要查找的节点，则返回，否则判断右子树是否为null，，如果不为null，递归前序
查找。
删除节点
1）如果当前节点的左子树不为空，并且左子节点就是要删除的节点，此时，this.left=null，并且返回
2）如果当前节点的右子树不为空，并且左子节点就是要删除的节点，此时，this.right=null，并且返回
3）如果前两个步骤都没有找到要删除的节点，此时，向左子树递归删除
4）如果前三个步骤都没有找到要删除的节点，此时，向右子树递归删除
源代码
package cn.xlystar;
public class Solution{
public static void main(String[] args) {
HeroNode root =new HeroNode(1);
HeroNode heroNode =new HeroNode(2);
HeroNode heroNode1 =new HeroNode(3);
HeroNode heroNode2 =new HeroNode(4);
HeroNode heroNode3 =new HeroNode(5);
root.setLeft(heroNode);
root.setRight(heroNode1);
heroNode.setLeft(heroNode2);
heroNode.setRight(heroNode3);
BinTree binTree =new BinTree();
binTree.setRoot(root);
// 前序遍历
binTree.preOrder();
// // 中序遍历
// binTree.infixOrder();
// // 后序遍历
// binTree.postOrder();
// 根据需要搜索相关节点
System.out.println(binTree.postOrderSearch(2));
}
}
class BinTree{
private HeroNoderoot;
public HeroNodegetRoot() {
return 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("此树为空树");
}
}
public HeroNodepreOrderSearch(int no) {
if (this.root !=null) {
return this.root.preOrderSearch(no);
} else {
return null;
}
}
public HeroNodeinfixOrderSearch(int no) {
if (this.root !=null) {
return this.root.infixOrderSearch(no);
} else {
return null;
}
}
public HeroNodepostOrderSearch(int no) {
if (this.root !=null) {
return this.root.postOrderSearch(no);
} else {
return null;
}
}
}
class HeroNode{
private HeroNodeleft;
private HeroNoderight;
private int no;
public HeroNode(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public HeroNodegetLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNodegetRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
// 前序遍历
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);
}
public HeroNodepreOrderSearch(int no) {
if (this.no == no) {
return this;
}
HeroNode anw =null;
if (this.left !=null) {
anw =this.left.preOrderSearch(no);
}
if (anw!=null) {
return anw;
}
if (this.right !=null) {
anw =this.left.preOrderSearch(no);
}
return anw;
}
public HeroNodeinfixOrderSearch(int no) {
HeroNode anw =null;
if (this.left !=null) {
anw =this.left.infixOrderSearch(no);
}
if (anw!=null) {
return anw;
}
if (this.no == no) {
return this;
}
if (this.right !=null) {
anw =this.left.infixOrderSearch(no);
}
return anw;
}
public HeroNodepostOrderSearch(int no) {
HeroNode anw =null;
if (this.left !=null) {
anw =this.left.postOrderSearch(no);
}
if (anw!=null) {
return anw;
}
if (this.right !=null) {
anw =this.left.postOrderSearch(no);
}
if (anw !=null) {
return anw;
}
if (this.no == no) {
return this;
}
return anw;
}
@Override
public StringtoString() {
return "HeroNode{" +
"left=" +left +
", right=" +right +
", no=" +no +
'}';
}
}
