数据结构之树

基础知识：

树是一种非线性结构，其严格的数学定义是：如果一组数据中除了第一个节点（第一个节点称为根节点，没有直接前驱节点）之外，其余任意节点有且仅有一个直接前驱，有零个或多个直接后继，这样的一组数据形成一棵树。这种特性简称为一对多的逻辑关系。

树的基本术语

树是由若干个节点组成的分支，每个节点都可能组成一棵树

1.根(root)：

树的第一个节点，没有直接前驱如上图的A，

2.双亲节点(parent):

某节点的直接前驱称为该节点的双亲节点，或称为父节点，例如上图A 是B的父节点。

3.孩子节点(child):

某节点的直接后继称为该节点的孩子节点，例如上图中的B、C、D均为 A的孩子节点。

4.节点的层次(level):

从树根开始，根为第一层，根的孩子为第二层，树中节点的最大层次 称为树的深度或者高度。比如上图中节点E的层次是3.

5.节点的度(degree):

节点拥有的子树的数量，称为该节点的度，度为0的节点称为叶子节点或者终端节点，度不为0的节点，称为非终端节点或者分支节点，比如上图节点B的度为2。

6.叶子(leaf):

一棵树中度等于0的节点，称为叶子节点，如上图K,L,G,M,I为叶子

二叉树 

二叉树是一种属性结构，他的特性是每个节点最多只有两棵子树，即二叉树中不存在度大于2的节点，并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的形态可以多种多样，但通常有以下几种基本形态：

1. 满二叉树（Full Binary Tree）

2. 完全二叉树（Complete Binary Tree）

3. 平衡二叉树（Balanced Binary Tree）

4. 二叉搜索树（Binary Search Tree, BST）

5. 哈夫曼树（Huffman Tree）

遍历

深度优先遍历

前中后序遍历，都是递归算法。前序遍历为例，当访问完根节点，进而要访问左子树时，由于左子树本身一棵二叉树，因此也需要进行前序遍历，也就是先访问左子树的根节点，然后再依次访问左子树的左孩子和左子树的右孩子。

• 前序遍历 : 根节点 - 左子树 - 右子树（F-BADCE-GIH）
• 中序遍历 : 左子树 - 根节点 -右子树（ABCDE-F-GHI）
• 后序遍历 : 左子树 - 右子树 - 根节点（ACEDB-HIG-F）

广度优先遍历

• 按层遍历：从上到下，从左到右

特点

1. 在二叉树的第i层上最多有2^(i-1)个节点(i>=0)
2. 深度为K的二叉树最多有2^k-1个节点
3. 对任意一颗二叉树T，如果其叶子节点数为n0,度为2的节点为n2，则有n2 = n0-1

存储结构

存储结构：即保存了元素又保存了关系(根据二叉树的信息可以把二叉树还原)

• 顺序存储结构

由于在顺序存储，数据之间的逻辑关系是用物理位置来表达，而二叉树中每一个节点都有一个对应的标号，因此可以使用标号来作为数组的下标，但除非是完全二叉树，否则会浪费存储空间，

• 链式存储结构

链式存储思路与链表类似，使用指针来直接将节点的逻辑关系串联起来

满二叉树

• 一棵深度为k且具备有2^k-1个节点的二叉树，称为满二叉树，在不改变深度的情况下，无法再往这棵树上加节点。

完全二叉树

1. 除去最后一层后为满二叉树
2. 最后一层的节点必须一次从左往右边排(左边不排满，就不要排右边)，完全二叉树的特性是不浪费空间

二叉搜索树（BST）

按照"小-中-大"(或"大-中-小")的规律来存储数据，即对于任意一个节点，都可以明确找到其值大于或等于其左孩子节点，且小于或等于其有孩子节点。

平衡二叉树（AVL）

它或者是一棵空树，或者是具有以下特性的二叉搜索树（BST）

1. 它的左子树或者右子树都是平衡二叉树
2. 左子树和右子树的深度之差的绝对值不超过1(1,-0,-1)

将二叉树上的节点的平衡因子定义为该节点的左子树的深度减去它右子树的深度，当平衡因子的绝对值大于1，则该二叉树不平衡。

不平衡二叉树转变为平衡二叉树

单向右旋平衡处理

 单向左旋平衡处理

 双向旋转(先左后右)平衡处理

 双向旋转(先右后左)平衡处理

 哈夫曼树

又称最优二叉树，是一种特殊的二叉树。

构造

带权路径长度

每层叶子结点*对应层权值之和（6+8+11）*2+（2+5）*3=71