小工具知识网

当前位置: 首页 > 行业知识 > 数据结构-树的遍历和基本操作(Java实现)

行业知识

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

2026-11-16 11:50:57 来源:互联网转载

一. 二叉树的遍历

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

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

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

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

接下来针对这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;    }

上一篇:揭秘信访背后的秘密,深度解读与探讨源码真相

下一篇:雷电模拟器游戏下载指南