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