二叉树基础

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

首先，我们来讲讲什么是树：

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

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

image.png

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

image.png

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

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

1.1树的一些概念

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

image.png

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

• 一棵树至少会有一个节点(根节点)
• 树由节点组成，每个节点的数据结构是这样的： image.png

• 因此，我们定义树的时候往往是->定义节点->节点连接起来就成了树，而节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)

作者：Java3y
链接：https://juejin.im/post/5ab5a01d518825555c1d9a24