二叉树遍历Java的代码实现
二叉树
二叉树是树的一种,每个结点最多可具有两个子树,即结点的度最大为2
二叉树的遍历
先序遍历:先访问根节点,然后访问左节点,最后访问右节点。
【1->2->4->8->9->5->10->3->6->7】
中序遍历:先访问左节点,然后访问根节点,最后访问右节点。
【8->4->9->2->10->5->1->6->3->7】
后序遍历:先访问左节点,然后访问右节点,最后访问根节点。
【8->9->4->10->5->2->6->7->3->1】
代码实现
首先创建一个结点
这个结点包括,一个根结点,一个根所对应的左结点,一个根所对应的右节点
public class Node {
Object data;
Node left = null;
Node right = null;
void Node(Object data,Node left,Node right){
this.data = data;
this.left = left;
this.right = right;
}
}
其次是进行遍历操作的BinaryTree类
用递归的方法实现遍历
public class BinaryTree {
// 先序遍历
void preSearch(Node root){
if (root != null){
System.out.printf("%-4s",root.data);
preSearch(root.left);
preSearch(root.right);
}
}
// 中序遍历
void midSearch(Node root){
if (root != null){
midSearch(root.left);
System.out.printf("%-4s",root.data);
midSearch(root.right);
}
}
// 后序遍历
void bacSearch(Node root){
if (root != null){
bacSearch(root.left);
bacSearch(root.right);
System.out.printf("%-4s",root.data);
}
}
}
能够使用递归的三个条件
- 一个问题可以分解成几个子问题。
- 这个问题与分解过后的子问题,除了数据规模不同(子问题更为简单),求解思路完全一样。
- 存在一个明确的递归终止条件。
在此例中,
- 遍历二叉树的操作可以分解为遍历单个结点的操作。
- 遍历整个二叉树的操作和遍历一个结点的操作相同。
- 存在截止条件,即根节点不为null。
所以,可以使用递归实现二叉树的遍历。
递归实现二叉树遍历方法详述(以中序遍历为例)
主函数
public class E1 {
public static void main(String[] args) {
//构造一个二叉树
Node node10 = new Node();
node10.Node("10",null,null);
Node node9 = new Node();
node9.Node("9",null,null);
Node node8 = new Node();
node8.Node("8",null,null);
Node node7 = new Node();
node7.Node("7",null,null);
Node node6 = new Node();
node6.Node("6",null,null);
Node node5 = new Node();
node5.Node("5",node10,null);
Node node4 = new Node();
node4.Node("4",node8,node9);
Node node3 = new Node();
node3.Node("3",node6,node7);
Node node2 = new Node();
node2.Node("2",node4,node5);
Node node1 = new Node();
node1.Node("1",node2,node3);
BinaryTree b = new BinaryTree();
//对所构造的二叉树遍历输出
System.out.println("前序遍历输出:");
b.preSearch(node1);
System.out.println();
System.out.println("中序遍历输出:");
b.midSearch(node1);
System.out.println();
System.out.println("后序遍历输出:");
b.bacSearch(node1);
}
}
输出结果
