树——前序

树的总结：

• 概念(前序)
  • 树的作用
  • 二叉树
  • 完全二叉树
  • 代码(golang)——实现树结构基本定义
• 二叉排序树(二叉查找/搜索树)
• 平衡二叉树AVL
• 红黑树
• 线索二叉树(了解)
• 赫夫曼树
• B树(数据库)
• B+树(索引)
• 最小生成树

概念：

1、为什么存在树结构

        相比于数组与链表：

                数组的查询速度快O(1)，但是删除等操作慢O(n）

                链表的删除插入等操作快O(1)，但是查询速度慢O(n)

        树结构在一定程度上起到综合作用

                查询时间复杂度(平均)：O(logn)

                删除插入操作(不同树结构不同)

2、二叉树

        数据结构一般树结构，一般指 二叉树     
        根节点：头结点，树最上面的节点
        父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。
        叶子节点：没有任何子节点的节点称为叶子节点。
        兄弟节点：具有相同父节点的节点互称为兄弟节点。
        树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，13的深度是1，30的深度是2，28的深度是3。
        树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3

3、完全二叉树

  二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续，我们称之为全完二叉树。

 4、代码实现树

       二叉树 可以使用链表构成也可以使用数据：此处使用链表

     

// 定义二叉树结构
type LinkNode struct {
	val       int       //二叉树存储的数据
	leftNode  *LinkNode //左节点
	RightNode *LinkNode //右结点
}