树结构是一种描述非线性层次关系的数据结构

在一个数结构中，有且仅有一个结点没有直接前驱，这个结点就是树的结点。

除根结点外，其余每个结点有且仅有一个直接前驱。

每个结点可以有任意多个直接后继。

根：有且仅有一个无直接前驱结点的结点

结点的度：结点拥有的子数的数量叫做结点的度

树的度：树内结点的度的最大值

结点的层：从根算起。根为第一层，往下则+1层

树的深度：树的最大层数

森林：去掉根结点所得子数的个数

结点最多只有两个儿子，叫做二叉树

第i层上最多有2^(i-1)个结点

深度为k的的二叉树最多有2^k - 1个结点

N0表示叶结点个数，N2表示度为2的非叶结点个数，那么N0=N2+1

顺序存储：一般通过结构数组进行存储

链式存储：存储结构包含结点元素及分别指向左子树和右子树的引用

先序遍历：1.访问根结点 2.访问椰子树 3.访问右子树

中序遍历：1.访问左子树 2.访问根结点 3.访问右子树

后序遍历：1.访问左子树 2.访问右子树 3.访问根结点

层次遍历：从根结点开始，向下一层一层访问，每层从左到右访问每个结点

如何具体实现？首先需要分析，二叉树遍历的核心问题，需要存储结构保存暂时不访问的结点，可以借助其他数据结构完成，如队列、堆栈

二叉树的先、中、后序递归遍历

核心思想：使用堆栈，先进后出

核心思想：使用队列，先进先出，首先根结点入队，当结点出队，访问该结点、将其左右儿子入队

双亲表示法，孩子表示法和兄弟表示法。

这里我们使用指针式的孩子表示法。

前序遍历，后序遍历，层序遍历（二叉树还有中序遍历）

按前序遍历顺序建立一颗树：