二叉树

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

Vinci-Ma

二叉树遍历Java的代码实现

二叉树