[TOC] ## 概述 树是一种比较高级的基础数据结构 树的定义： 1. 有节点间的层次关系，分为父节点和子节点。 2. 有唯一一个根节点，该根节点没有父节点。 3. 除了根节点，每个节点有且只有一个父节点。 4. 每一个节点本身以及它的后代也是一棵树，是一个递归的结构。 5. 没有后代的节点称为叶子节点，没有节点的树称为空树。 ### 二叉树 * 每个节点最多只有两个子节点的树 ### 满二叉树 * 叶子节点与叶子节点之间的高度差为`0`的二叉树，即整棵树是满的，树呈满三角形结构 ### 完全二叉树 * 完全二叉树是由满二叉树而引出来的，设二叉树的深度为`k`，除第`k`层外，其他各层的节点数都达到最大值，且第`k`层所有的节点都连续集中在最左边 树根据儿子节点的多寡，有二叉树，三叉树，四叉树等 ## 二叉树的实现 数组也可以用来表示二叉树，一般用来表示完全二叉树 ``` // 二叉树 type TreeNode struct { Data string // 节点用来存放数据 Left *TreeNode // 左子树 Right *TreeNode // 右字树 } ```  :-: 一个完全二叉树