二叉树就这么简单

一、二叉树就是这么简单

本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)….

首先,我们来讲讲什么是树:

  • 树是一种非线性的数据结构,相对于线性的数据结构(链表、数组)而言,树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)

在现实生活中,我们一般的树长这个样子的:

但是在编程的世界中,我们一般把树“倒”过来看,这样容易我们分析:

一般的树是有很多很多个分支的,分支下又有很多很多个分支,如果在程序中研究这个会非常麻烦。因为本来树就是非线性的,而我们计算机的内存是线性存储的,太过复杂的话我们无法设计出来的。

因此,我们先来研究简单又经常用的---> 二叉树

1.1树的一些概念

我就拿上面的图来进行画来讲解了:

二叉树的意思就是说:每个节点不能多于有两个儿子,上面的图就是一颗二叉树。

  • 一棵树至少会有一个节点(根节点)
  • 树由节点组成,每个节点的数据结构是这样的:
  • 因此,我们定义树的时候往往是->定义节点->节点连接起来就成了树,而节点的定义就是:一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)

1.2静态创建二叉树

上面说了,树是由若干个节点组成,节点连接起来就成了树,而节点由一个数据、两个指针组成

  • 因此,创建树实际上就是创建节点,然后连接节点

首先,使用Java类定义节点:

public class TreeNode {

    // 左节点(儿子)
    private TreeNode lefTreeNode;

    // 右节点(儿子)
    private TreeNode rightNode;

    // 数据
    private int value;


}

下面我们就拿这个二叉树为例来构建吧:

为了方便构建,我就给了它一个带参数的构造方法和set、get方法了:

    public TreeNode(int value) {

        this.value = value;
    }

那么我们现在就创建了5个节点:

    public static void main(String[] args) {

        //根节点-->10
        TreeNode treeNode1 = new TreeNode(10);

        //左孩子-->9
        TreeNode treeNode2 = new TreeNode(9);

        //右孩子-->20
        TreeNode treeNode3 = new TreeNode(20);

        //20的左孩子-->15
        TreeNode treeNode4 = new TreeNode(15);

        //20的右孩子-->35
        TreeNode treeNode5 = new TreeNode(35)        

    }

它们目前的状态是这样子的:

于是下面我们去把它连起来:

    //根节点的左右孩子
    treeNode1.setLefTreeNode(treeNode2);
    treeNode1.setRightNode(treeNode3);

    //20节点的左右孩子
    treeNode3.setLefTreeNode(treeNode4);
    treeNode3.setRightNode(treeNode5);

连接完之后,那么我们的树就创建完成了。

1.3遍历二叉树

上面说我们的树创建完成了,那怎么证明呢??我们如果可以像数组一样遍历它(看它的数据),那就说明它创建完成了

值得说明的是:二叉树遍历有三种方式

  • 中序遍历
    • 先访问根节点,然后访问左节点,最后访问右节点(根->左->右)
  • 先序遍历
    • 先访问左节点,然后访问根节点,最后访问右节点(左->根->右)
  • 后序遍历
    • 先访问左节点,然后访问右节点,最后访问根节点(左->右->根)

以上面的二叉树为例:

  • 如果是中序遍历10->9->20->15->35
  • 如果是先序遍历9->10->15->20->35
    • 可能需要解释地方:访问完10节点过后,去找的是20节点,但20下还有子节点,因此访问的是20的左儿子15节点。由于15节点没有儿子了。所以就返回20节点,访问20节点。最后访问35节点
  • 如果是后序遍历9->15->35->20->10
    • 可能需要解释地方:先访问9节点,随后应该访问的是20节点,但20下还有子节点,因此访问的是20的左儿子15节点。由于15节点没有儿子了。所以就去访问35节点,由于35节点也没有儿子了,所以返回20节点,最终返回10节点

一句话总结:中序(根->左->右),先序(左->根->右),后序(左->右->根)。如果访问有孩子的节点,先处理孩子的,随后返回

无论先中后遍历,每个节点的遍历如果访问有孩子的节点,先处理孩子的(逻辑是一样的)

  • 因此我们很容易想到递归
  • 递归的出口就是:当没有子节点了,就返回

因此,我们可以写出这样的中序遍历代码

    /**
     * 中序遍历
     * @param rootTreeNode  根节点
     */
    public static void inTraverseBTree(TreeNode rootTreeNode) {

        if (rootTreeNode != null) {

            //访问根节点
            System.out.println(rootTreeNode.getValue());

            //访问左节点
            preTraverseBTree(rootTreeNode.getLefTreeNode());

            //访问右节点
            preTraverseBTree(rootTreeNode.getRightNode());
        }
    }

结果跟我们刚才说的是一样的:

我们再用先序遍历调用一遍吧:

    /**
     * 中序遍历
     * @param rootTreeNode  根节点
     */
    public static void preTraverseBTree(TreeNode rootTreeNode) {

        if (rootTreeNode != null) {

            //访问左节点
            preTraverseBTree(rootTreeNode.getLefTreeNode());

            //访问根节点
            System.out.println(rootTreeNode.getValue());

            //访问右节点
            preTraverseBTree(rootTreeNode.getRightNode());
        }
    }

结果跟我们刚才说的是一样的:

有意思的是:通过先序和中序或者中序和后序我们可以还原出原始的二叉树,但是通过先序和后续是无法还原出原始的二叉树的

  • 也就是说:通过中序和先序或者中序和后序我们就可以确定一颗二叉树了

二、动态创建二叉树

上面我们是手动创建二叉树的,一般地:都是给出一个数组给你,让你将数组变成一个二叉树,此时就需要我们动态创建二叉树了。

二叉树中还有一种特殊的二叉树:二叉查找树(binary search tree)

  • 定义:当前根节点的左边全部比根节点小,当前根节点的右边全部比根节点大
    • 明眼人可以看出,这对我们来找一个数是非常方便快捷的

往往我们动态创建二叉树都是创建二叉查找树

2.1动态创建二叉树体验

假设我们有一个数组:int[] arrays = {3, 2, 1, 4, 5};

那么创建二叉树的步骤是这样的:

  • 首先将3作为根节点
  • 随后2进来了,我们跟3做比较,比3小,那么放在3的左边
  • 随后1进来了,我们跟3做比较,比3小,那么放在3的左边,此时3的左边有2了,因此跟2比,比2小,放在2的左边
  • 随后4进来了,我们跟3做比较,比3大,那么放在3的右边
  • 随后5进来了,我们跟3做比较,比3大,那么放在3的右边,此时3的右边有4了,因此跟4比,比4大,放在4的右边

那么我们的二叉查找树就建立成功了,无论任何一颗子树,左边都比根要小,右边比根要大

2.2代码实现

我们的代码实现也很简单,如果比当前根节点要小,那么放到当前根节点左边,如果比当前根节点要大,那么放到当前根节点右边。

因为是动态创建的,因此我们得用一个类来表示根节点

public class TreeRoot {

    private TreeNode treeRoot;

    public TreeNode getTreeRoot() {
        return treeRoot;
    }

    public void setTreeRoot(TreeNode treeRoot) {
        this.treeRoot = treeRoot;
    }
}

比较与根谁大,大的往右边,小的往左边:

  /**
     * 动态创建二叉查找树
     *
     * @param treeRoot 根节点
     * @param value    节点的值
     */
    public static void createTree(TreeRoot treeRoot, int value) {


        //如果树根为空(第一次访问),将第一个值作为根节点
        if (treeRoot.getTreeRoot() == null) {
            TreeNode treeNode = new TreeNode(value);
            treeRoot.setTreeRoot(treeNode);

        } else  {

            //当前树根
            TreeNode tempRoot = treeRoot.getTreeRoot();

            while (tempRoot != null) {
                //当前值大于根值,往右边走
                if (value > tempRoot.getValue()) {

                    //右边没有树根,那就直接插入
                    if (tempRoot.getRightNode() == null) {
                        tempRoot.setRightNode(new TreeNode(value));
                        return ;
                    } else {
                        //如果右边有树根,到右边的树根去
                        tempRoot = tempRoot.getRightNode();
                    }
                } else {
                    //左没有树根,那就直接插入
                    if (tempRoot.getLefTreeNode() == null) {
                        tempRoot.setLefTreeNode(new TreeNode(value));

                        return;
                    } else {
                        //如果左有树根,到左边的树根去
                        tempRoot = tempRoot.getLefTreeNode();
                    }
                }
            }
        }
    }

测试代码:

    int[] arrays = {2, 3, 1, 4, 5};

    //动态创建树

    TreeRoot root = new TreeRoot();
    for (int value : arrays) {
        createTree(root, value);
    }

    //先序遍历树
    preTraverseBTree(root.getTreeRoot());
    System.out.println("---------------公众号:Java3y");

    //中序遍历树
    inTraverseBTree(root.getTreeRoot());
    System.out.println("---------------公众号:Java3y");

三、查询二叉查找树相关

3.1查询树的深度

查询树的深度我们可以这样想:左边的子树和右边的字数比,谁大就返回谁,那么再接上根节点+1就可以了

    public static int getHeight(TreeNode treeNode) {

        if (treeNode == null) {
            return 0;
        } else {

            //左边的子树深度
            int left = getHeight(treeNode.getLefTreeNode());

            //右边的子树深度
            int right = getHeight(treeNode.getRightNode());


            int max = left;

            if (right > max) {
                max = right;
            }
            return max + 1;
        }
    }

3.1查询树的最大值

从上面先序遍历二叉查找树的时候,细心的同学可能会发现:先序遍历二叉查找树得到的结果是排好顺序的~

那么,如果我们的二叉树不是二叉查找树,我们要怎么查询他的最大值呢

可以这样:

  • 左边找最大值->递归
  • 右边找最大值->递归
    /**
     * 找出树的最大值
     *
     * @param rootTreeNode
     */
    public static int  getMax(TreeNode rootTreeNode) {

        if (rootTreeNode == null) {
            return -1;
        } else {
            //找出左边的最大值
            int left = getMax(rootTreeNode.getLefTreeNode());

            //找出右边的最大值
            int right = getMax(rootTreeNode.getRightNode());

            //与当前根节点比较
            int currentRootValue = rootTreeNode.getValue();

            //假设左边的最大
            int max = left;


            if (right > max) {
                max = right;
            }
            if (currentRootValue > max) {
                max = currentRootValue;
            }

            return max ;


        }
    }

四、最后

无论是在遍历树、查找深度、查找最大值都用到了递归,递归在非线性的数据结构中是用得非常多的

树的应用也非常广泛,此篇简单地说明了树的数据结构,高级的东西我也没弄懂,可能以后用到的时候会继续深入…

原文发布于微信公众号 - Java3y(gh_085b56c42174)

原文发表时间:2018-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9520
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

1.7K10
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

9840
来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

12220
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

35770
来自专栏kevindroid

leetcode538 Convert BST to Greater Tree

17640
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

33280
来自专栏开发与安全

数据结构:线性表之链式存储结构

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)...

204100
来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

23170
来自专栏用户画像

剑指offer 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

8830

扫码关注云+社区

领取腾讯云代金券