数据结构-树的遍历和基本操作(Java实现)_java遍历树形数据

一. 二叉树的遍历

二叉树的遍历分为以下三种: 

前序遍历: 访问顺序为  根节点---->左子树---->右子树

中序遍历: 访问顺序为  左子树---->根节点---->右子树

后序遍历: 访问顺序为  左子树---->右子树---->根节点

接下来针对这3种遍历方式进行详细介绍:

        (1) 前序遍历

上图前序遍历顺序为 1 2 3 4 5 6

        (2) 中序遍历

上图中序遍历顺序为3 2 1 5 4 6 

        (3) 后序遍历

上图后序遍历顺序为 3 2 5 6 4 1

        (4) 层序遍历原理

        除了前序遍历,中序遍历,后序遍历外,还可以对二叉树进行层序遍历. 设二叉树的根节点所在层数为1, 层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树的根节点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历. 

上图的层序遍历为 1 2 4 3 5 6

 二. 二叉树的基本操作

2.1 二叉树的创建

二叉树的存储结构分为: 顺序存储结构和类似于链表的链式存储。二叉树的链式存储是通过一个一个的结点引用起来的，常见的表示方式有二叉和三叉表示方式。在这里我们主要是使用二叉表示法来创建二叉树。

    static class TreeNode {  //定义好三个属性
        public char val;
        public TreeNode left;  //左节点
        public TreeNode right;  //右节点
 
        public TreeNode(char val) {  //提供一个结点的构造方法  new一个新结点的时候是不知道左右子树的,所以不用构造
            this.val = val;
        }
    }

2.2 二叉树的创建代码实现

以下图二叉树为例创建

    //以穷举的方式创建一棵二叉树出来
    public TreeNode creatTree() {  //要返回树的根节点,所以返回类型是 TreeNode
        TreeNode A = new TreeNode('A');  //创建一个结点赋值
        TreeNode B = new TreeNode('B');  //创建一个结点赋值
        TreeNode C = new TreeNode('C');  //创建一个结点赋值
        TreeNode D = new TreeNode('D');  //创建一个结点赋值
        TreeNode E = new TreeNode('E');  //创建一个结点赋值
        TreeNode F = new TreeNode('F');  //创建一个结点赋值
        TreeNode G = new TreeNode('G');  //创建一个结点赋值
        TreeNode H = new TreeNode('H');  //创建一个结点赋值
 
        A.left = B;
        A.right = C;
 
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
 
        E.right = H;
 
        return A;  //返回根节点
 
    }

2.3 二叉树的基本操作（Java实现）

2.3.1 前序遍历代码实现（递归方式）

 由于二叉树是递归定义的，所以二叉树的遍历一般也是采用递归的形式，当然二叉树也可以用非递归方式遍历。这里文章用递归方式介绍。前序遍历即采用先访问根节点，再访问左子树，最后访问右子树的顺序。前序遍历也是按照类似的方式递归遍历，具体操作如下：
① 如果当前节点值为空，返回；
②如果当前节点值不为空，打印当前节点值；递归遍历左子树；递归遍历右子树。

    // 前序遍历
    void preOrder(TreeNode root) {
        if (root == null) {
            return;  //空树是不需要遍历的
        }
        System.out.print(root.val + " ");
        preOrder(root.left);  //递归
        preOrder(root.right);
 
    }

 2.3.2 中序遍历代码实现

①如果当前节点值为空，返回；
②递归遍历左子树；打印当前节点的值；递归遍历右子树。

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
 
    }

2.3.3 后序遍历代码实现

①如果当前节点值为空，返回；
②递归遍历左子树；递归遍历右子树；打印当前节点的值。

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
 
    }

2.3.4 获取树中结点的个数

    public static int nodeSize;  //默认为0
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        nodeSize++;
        size(root.left);  //遍历左子树
        size(root.right);  //遍历右子树
        return nodeSize;
    }

子问题思路： 

    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        //左子树的个数加上右子树的结点个数加上根结点
        int tmp = size2(root.left)+size2(root.right)+1;  
        return tmp;
    }

2.3.5 获取叶子结点的个数

    //获取叶子结点个数
    public static int leafSize;
    public void getLeafNodeCount(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){  
            //如果没有左右子树就说明是叶子节点
            leafSize++;
        }
        getLeafNodeCount(root.left);  //递归遍历左子树
        getLeafNodeCount(root.right);  //递归遍历右子树
    }

 子问题思路： root这棵树有多少个叶子结点 = 左子树的叶子结点 + 右子树的叶子结点

    public int getLeafNodeCount2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

2.3.6 获取第K层结点的个数

    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }else{
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }
    }

2.3.7 获取树的高度

    //获取树的高度
    //整棵树的高度 = 左子树的高度和右子树的高度的最大值 + 1
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int hl = getHeight(root.left);  //获取左子树的高度
        int hr = getHeight(root.right);  //获取右子树的高度
        int max = hl>hr?hl:hr;
        return max+1;
    }

2.3.8 检测value的值是否存在

    //寻找树指定的元素
    public TreeNode find(TreeNode root,int val){
        if(root ==null){
            return null;
        }
        if(root.val == val){  //先判断根节点是不是我们要找的数据
            return root;
        }
        TreeNode leftVal = find(root.left,val);  //左子树去找
        if(leftVal != null){  //返回值不等于空说明找到了
            return leftVal;
        }
        TreeNode rightVal = find(root.right,val);  //右子树去找
        if(rightVal != null){  //返回值不等于空说明找到了
            return rightVal;
        }
        //左右都走完没找到返回空
        return null;
    }