vlambda博客
学习文章列表

每日一例 | 二叉树数据结构了解下?

前言

数据结构是任何编程语言的基础,可以这样说,如果你熟练掌握了各种数据结构,那你就离写出优秀代码不远了。为什么?因为所有的业务逻辑都是基于编程语言构建的模型实现的,而模型又是基于数据结构实现的,数据结构本身是脱离于编程语言的。

之前看到一位大佬分享了他对编程的看法,他觉得一切编程都是建模,网上购物就是对我们传统购物流程建模,社交聊天就是对我们传统的交流方式建模,业务的契合程度,取决于你的建模粒度,你的建模粒度越细化,越贴合实际业务,但同时也越复杂。

废话有点多,简单来说,其实比编程能力更重要的是建模能力,模型建的好,系统效率才能高。

好了,我们回到今天的内容,今天要分享的内容是二叉树的实现,以及二叉树的常用方法实现,算是对数据结构的初探。我们常用的数据结构有表、栈、队列、树、散列、堆等,我们常用的集合都是通过这些实现的,有些会复杂一点,会用到两种数据结构。

二叉树

树的基本数据结构

最基本的树是这样的,它可以有多个节点:

每日一例 | 二叉树数据结构了解下?

代码实现是这样的:

class TreeNode {
    Object element;
    TreeNode firstChild;
    TreeNode nextSibling;
}

二叉树结构

二叉树是最多只能有两个子节点的树,左边的子节点叫left节点,右边的子节点叫right节点:

每日一例 | 二叉树数据结构了解下?

代码实现:

class BinaryNode<T{
        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;

        public BinaryNode() {
        }

        public BinaryNode(T element) {
            this.element = element;
        }

        public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "BinaryNode{" +
                    "element=" + element +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

二叉树遍历

二叉树的遍历方式有三种,分别叫先序遍历、中序遍历和后序遍历。

先序遍历就是从上到下,从左到右遍历,即先打印父节点,再打印左节点,再打印右节点。

中序遍历是有左节点先打印左节点,然后依次从左到右遍历,左后打印右节点。

后序遍历是先打印子节点,再打印父节点,顺序也是从左到右。

以下图为例:

每日一例 | 二叉树数据结构了解下?

中序遍历是这样的:

(a + (b * C)) + (((d * e) + f) * g)

后序遍历是这样的:

a b c * + d e * f + g * +

先序遍历是这样的:

+ + a * b c * + * d e f g

这里分享下中序遍历的实现,这里用到了递归算法,其他的遍历由于时间关系就先不写了

 private void printTree(BinaryNode<T> t) {
       if (t != null) {
           printTree(t.left);
           System.out.println(t.element);
           printTree(t.right);
       }
    }

总结

二叉树是算法题中经常要用到的一种数据结构,我还依稀记得去年有一次面试的时候,面试官让我实现一个二叉树的算法,我愣是没写出来,压根就没概念,但是一直到现在,对二叉树也是知之甚少,所以从那时候我就觉得得好好补下数据结构这块的知识了。毕竟欠下的债,终究是要还的,像我们这些非科班出身的小伙伴,更是要好好努力呀,特别是数据结构这一块。没伞的孩子,要努力奔跑呀!每日一例 | 二叉树数据结构了解下?

每天早上的时间都很紧张,所以能分享的内容也就不会太多,但是如果你真正去思考每天分享的知识点,应该还是有收获的,至少我感觉是这样的,这种潜移默化的学习和进步,一定会让你越来越优秀,加油吧!

- END -
云中志
双非本科,跨专业转行的非典型码农,爱技术,爱分享,爱生活,爱学习,让我们一起Hello World,拥抱希望,拥抱改变,共同成长!
116篇原创内容
Official Account