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