⼆叉树的前序、中序和后序遍历介绍及案例
⽂章⽬录
⼀、介绍
前序遍历、中序遍历和后序遍历是⼆叉树的三种遍历⽅式，三者很像，具体的遍历步骤如下：
前序遍历：先输出⽗节点，然后依次遍历左⼦树，右⼦树。
中序遍历：先遍历左⼦树，后输出⽗节点，之后遍历右⼦树。
后序遍历：先遍历左⼦树，后遍历右⼦树，之后输出⽗节点。
⼆、建⽴⼆叉树
1.节点类
class Node{
int num;//数据
Node left;//左节点
Node right;//右节点
public Node(int num){
this.num = num;
}
@Override
public String toString(){
return"Node{"+
"num="+ num +
先序中序后序遍历二叉树'}';
}
}
2.⼆叉树
因为这⾥的⼆叉树是普通的，没有其他特性，不好建⽴⼆叉树类，就在main⽅法⾥⾯直接挂上就⾏了。这⾥我们以下图的⼆叉树为例。
main⽅法⾥⾯的代码：
public static void main(String[] args){
Node root =new Node(1);
Node n2 =new Node(2);
Node n3 =new Node(3);
Node n4 =new Node(4);
Node n5 =new Node(5);
Node n6 =new Node(6);
Node n7 =new Node(7);
Node n8 =new Node(8);
Node n9 =new Node(9);
root.left = n2;
root.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n4.left = n8;
n6.right = n9;
}
三、前序遍历
使⽤递归的⽅法进⾏前序遍历，直接上代码。
public static void preOrder(Node root){
if(root == null){
return;
}
System.out.print(root+" ");
preOrder(root.left);
preOrder(root.right);
}
结果：
Node{num=1} Node{num=2} Node{num=4} Node{num=8} Node{num=5} Node{num=3} Node{num=6} Node{num=9} Node{num=7}
四、中序遍历
public static void infixOrder(Node root){
if(root == null){
return;
}
infixOrder(root.left);
System.out.print(root+" ");
infixOrder(root.right);
}
结果：
Node{num=8} Node{num=4} Node{num=2} Node{num=5} Node{num=1} Node{num=6} Node{num=9} Node{num=3} Node{num=7}
五、后序遍历
public static void postOrder(Node root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root+" ");
}
结果：
Node{num=8} Node{num=4} Node{num=5} Node{num=2} Node{num=9} Node{num=6} Node{num=7} Node{num=3} Node{num=1}
六、完整代码
public class BinaryTreeDemo {
public static void main(String[] args){
Node root =new Node(1);
Node n2 =new Node(2);
Node n3 =new Node(3);
Node n4 =new Node(4);
Node n5 =new Node(5);
Node n6 =new Node(6);
Node n7 =new Node(7);
Node n8 =new Node(8);
Node n9 =new Node(9);
root.left = n2;
root.right = n3;
n2.left = n4;
n2.right = n5;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n4.left = n8;
n6.right = n9;
preOrder(root);
System.out.println();
infixOrder(root);
System.out.println();
postOrder(root);
}
public static void preOrder(Node root){
if(root == null){
return;
}
System.out.print(root+" ");
preOrder(root.left);
preOrder(root.right);
}
public static void infixOrder(Node root){
if(root == null){
return;
}
infixOrder(root.left);
System.out.print(root+" ");
infixOrder(root.right);
}
public static void postOrder(Node root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root+" ");
}
}
/
/节点
class Node{
int num;
Node left;
Node right;
public Node(int num){
this.num = num;
}
@Override
public String toString(){
return"Node{"+
"num="+ num +
'}';
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。