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);
       }
    }

总结

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

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