二叉树遍历——Java代码实现

二叉树遍历——Java的代码实现

• 二叉树
• 二叉树的遍历
• 代码实现
• • 首先创建一个结点类
  • 其次是进行遍历操作的BinaryTree类
  • • 递归实现二叉树遍历方法详述（以中序遍历为例）
  • 主函数
  • 输出结果

二叉树

二叉树是树的一种，每个结点最多可具有两个子树，即结点的度最大为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);
        }
    }
}
           

递归实现二叉树遍历方法详述（以中序遍历为例）

主函数

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);
    }
}
           

输出结果