数据结构基础：树结构的学习笔记

1、树的定义

树是n(n>=0)个节点的有限集合。当n=0时称为空树，当n>0 为非空树，任何非空树中，有且仅有一个根节点；其余节点可分为m(m>=0)个互不相交的有限集合T1、T2 等，其中每一个集合都可以称为一棵树，称为根节点的子树。

2、树的基本概念 

双亲孩子、兄弟：节点的字数的根称为该节点的孩子，该节点称为其子节点的双亲。具有相同双亲的节点互为兄弟节点。如图：A是根节点，B、C、D互为兄弟；B是E、F的父节点（双亲）；E、F 互为兄弟节点。

节点的度：一个节点下的子节点个数称为节点的度。比如 A的度为3，D的度为1。

叶子节点：是指度为0的节点，也被称为终端节点。比如 C、E、F、G都是叶子节点。

内部节点：度不为零的节点称为分支节点或非终端节点。去掉根节点，分支节点称为内部节点。比如：B、D。

节点的层次：根节点A属于第一层，依次类推。B属于第二层，E属于第三层。

树的高度：一棵树的最大层次数称为树的高度或者树的深度。

有序（无序）树：树中的节点的各个子树看成是从左到右有次序的，即不能交换，则称为有序树，否则为无序树。

森林：m(m>=0)棵互补相交的树的集合。

3、二叉树

3.1 二叉树定义

二叉树是n(n>=0)个节点的有限集合，它或者是空树（n=0），或者是由一个根节点及两棵不相交的、分别称为左子树、右子树的二叉树所组成。

3.2 二叉树和普通树的区别

二叉树中节点区分左子树、右子树，即便只有一个子树的情况下也有标明是左子树还是右子树，普通树则不区分；二叉树中节点最大度为2，普通树则没有限制节点的度数。

3.3 二叉树的性质

1、二叉树第i层上最多有  2^(i-1)个节点

2、深度为k的二叉树最多有(2^k)-1个节点

3、对任何一棵二叉树，若其终端节点数为n,度为2的节点数为n2，则n=n2+1

4、具有n个节点的完全二叉树的深度为(log2^n)+1

3.4 二叉树分类

1、满二叉树：深度为k的二叉树有2^(k-1)个节点,是满二叉树

2、完全二叉树:高度为k的二叉树，除了第k层都是满的，称为完全二叉树。满二叉树也是完全二叉树。具有n个节点的完全二叉树高度为 (log2^n) +1

3、非完全二叉树：不满足完全二叉树的称为非完全二叉树。

3.5叉树的存储结构

1、二叉树的顺序存储结构

用一组地址连续的存储单元存储二叉树的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置可以反映出节点之间的逻辑关系

顺序存储适合对完全二叉树的存储方式，既简单又节省空间。对于一般二叉树而言，因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，所以存储方式也必须按照完全二叉树的方式存储，这样会造成空间上的浪费。最坏的情况，一个深度为h且只有h个节点的二叉树（也是单枝树）需要(2^h) -1 存储单元.

2、二叉树的链式存储结构

由于二叉树中节点包含数据、左子树根、右子树根、双亲信息，因此可以用三叉链表或二叉链表来 存储二叉树，链表的头指针指向二叉树的根节点。

3.6  二叉树的遍历

遍历是按某种策略访问树中的每个节点，仅访问一次。对于含有n个节点的二叉树遍历算法的时间复杂度都是O(n).

3.7  哈夫曼树（最优二叉树）

节点的路径：从树的一个节点到另一个节点之前的通路。

该通路的分支数据称为路径长度。

节点的带权路径：节点到树根之间的路径长度*该节点的权重值。

树的带权路径长度为树种所有叶子节点的带权路径长度之和。数值最小的就是哈夫曼树。