# go-tree

**Repository Path**: dingjianhui/go-tree

## Basic Information

- **Project Name**: go-tree
- **Description**: go语言练习-二叉树|二叉查找树
- **Primary Language**: Go
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-06-28
- **Last Updated**: 2020-12-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README



## 术语

```

节点的度： 一个节点含有的子树的个数称为节点的度
树的度 ： 一棵树中，最大的节点的度称为树的度
叶节点或终端节点：度为零的节点
非终端节点或分支节点： 度不为零的节点
父亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
兄弟节点： 具有相同父节点的节点互称为兄弟节点
节点的层次： 从根节点开始，根为第一层，根的子节点为第二层，以此类推
深度：对于任意节点n， n的深度为从根到n的唯一路径长，根的深度为0
高度： 对于任意节点n，n的高度为从n到一片树叶的最长路径厂，所有树叶的高度为0
堂兄弟节点：父节点在同一层的节点互称堂兄节点
子孙： 以某节点为根的子树中任一节点都称为该节点的子孙
森林：由m（m>0）颗互不相交的树的集合称为森林
```

```
- 无序树

- 有序树

- 二叉树

- 完全二叉树

- 满二叉树

- 平衡二叉树

- 排序二叉树

- 霍夫曼树

- B树
```

#### 二叉查找树|二叉搜索树|二叉排序树(binary search tree)

```
    1. 动态创建节点
    2. 搜索结点
    3. 搜索父节点
    4. 遍历
        1) 先序 根-左-右
        2) 中序 左-根-右
        3) 后序 左-右-根
    5. 二叉树的深度
    6. 查找最大值和最小值
    7. 删除节点
        1) 删除没有子节点的节点 
        2) 删除有一个子节点的节点 
        3) 删除有两个子节点的节点
        3) 删除根节点
    8. 二叉树的效率
    　　一颗满树，每层节点数大概为2的n-1幂方，那么最底层的节点个数比树的其它节点数多1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。
    　　总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。
    　　在有1000000 个数据项的无序数组和链表中，查找数据项平均会比较500000 次，但是在有1000000个节点的二叉树中，只需要20次或更少的比较即可。
    　　有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要20次或更少比较，在加上很短的时间来连接数据项。
    　　同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他，然后在花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。
    　　所以，树对所有常用数据结构的操作都有很高的效率。
    　　遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。
```




```


```



```


```




```


```