树和二叉树

树的定义

定义和术语

树（tree): 树是n(n≥0)个结点的有限集T,

当n=0时，T为空树；
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集T1,T2,…,Tm ,每个Ti(1≤i≤m)也是一棵树,且称为 根的子树

2.结点的度(degree): 结点的子树数目
3.树的度: 树中各结点的度的最大值
4.n度树: 度为n的树
5.叶子(终端结点): 度为0的结点
6.分枝结点(非终端结点,非叶子): 度不为0的结点
7.双亲(父母,parent)和孩子(儿子,child) : 若结点C是结点P的子树的根,称P是C的双亲，C是P的孩子。
8.结点的层(level): 规定树T的根的层为1，其余任一结点的层等于其双亲的层加1。
9.树的深度(depth,高度): 树中各结点的层的最大值。
10.兄弟(sibling): 同一双亲的结点之间互为兄弟。
11.堂兄弟: 同一层号的结点互为堂兄弟
12.祖先: 从树的根到某结点所经分枝上的所有结点为该结点的祖先。
13.子孙: 一个结点的所有子树的结点为该结点的子孙。
14.有序树:若任一结点的各棵子树，规定从左至右是有次序的,即不能互换位置,则称该树为有序树。
15.无序树: 若任一结点的各棵子树，规定从左至右是无次序的,即能互换位置,则称该树为无序树。
16.森林: m(m≥0)棵互不相交的树的集合。
树的其它表示形式
1.广义表树T的广义表=(T的根(T1,T2,…,Tm)) 其中Ti是T的子树，也是广义表。 (1≤i≤m)

2.嵌套集合：
3.凹入表/目录表

二叉树
定义和术语
1. 二叉树的递归定义
  二叉树是有限个结点的集合，它或者为空集；或者是由一个根结点和两棵互不相交的，且分别称为根的左子树和右子树的二叉树所组成。若二叉树为空集，则为空二叉树。
2.二叉树的5种基本形态

3.二叉树与2度树的区别
1、度不同
度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。
二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。

在任意一棵二叉树中，叶子结点总是比度为2的结点多一个。

2、分支不同

度为2的树有两个分支，但分支没有左右之分；
一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。

3、次序不同

度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

4.三个结点不同形态的二叉树(5种)

5.三个结点不同形态的树(2种)

二叉树的性质和特殊二叉树

1.二叉树的第i(i≥1)层最多有2^i - 1个结点(性质1)

2.深度为k的二叉树最多有2^k - 1个结点(性质2）

3.叶子的数目=度为2的结点数目+1（性质3）
n0 = n2 + 1

二叉树中，有多少个空指针？ n个结点，2n个指针除根结点外，都需要一个指针链接，用了n-个指针因此：空指针m=2n-(n-1)=n+1

满二叉树（full binary tree)

—- 深度为k且有2 k-1个结点的二叉树

(1) n个结点的满二叉树的深度=log2(n+1)（性质4）设深度为k

(2)顺序编号的满二叉树（性质5）

完全二叉树（full binary tree)

深度为k的有n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树（其它教材称为“顺序二叉树”）。

二叉树的存储结构

1.顺序结构

(1) n个结点的完全二叉树，使用一维数组

(2) 一般二叉树

(3)右单枝树

2.链式存储结构

二叉树的遍历

前中后序遍历二叉树是十分重要的，这一块一定要多加理解，因为对各个节点进行操作相当于通常是使用某一种顺序遍历，而这顺序通常是前中后序中的某一种

前中后序遍历二叉树，理解递归思想后由于比较简单，后续有时间在补充，这里先介绍中序遍历非递归的解决方法

非递归算法思想：设置一个栈S存放所经过的根结点（指针）信息；

（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；
（2）第一次访问到根结点并不访问，而是入栈；
（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后（中序）遍历它的右子树。
（4）当需要退栈时，如果栈为空则结束
ps：个人感觉用了栈操作其实和递归差不多同一个思想了

树的存储结构

1.双亲表示法/数组表示法/顺序表示法

结构体数组中结构体有个值专门用来存储双亲节点

2.孩子表示法/链接表表示法

(1)固定大小的结点格式，设树T的度为n

(2)非固定大小的结点格式

3.孩子兄弟表示法/二叉树表示法/二叉链表

4.孩子链表表示法/单链表表示法

5.带双亲的孩子链表表示法

树与二叉树的转换

1.在兄弟之间加连线
2.保留根与最左孩之间的连线删除与其它孩子之间的连线
3.以根为轴心顺时针方向旋转45度

线索二叉树

遍历二叉树是按某种规则将非线性结构的二叉树结点线性化。
二叉树结点中没有相应前驱和后继的信息。每次遍历时需按规则动态产生。
n个结点的二叉树，有： n*2 个指针域
使用: n-1 个指针，除根以外，每个结点被一个指针指向空指针域，空指针域数： n*2-(n-1)=n+1
当对某二叉树经常按某种规则遍历访问时，可利用空指针域。 n 将空的左指针域指向直接前驱，空的右指针域指向直接后继，非空指针不需要改变。称该处理过程称为二叉树线索化。
由此可分别得到：前序线索二叉树，中序线索二叉树，后序线索二叉树

三种线索二叉树

1.先序线索二叉树: 线索指向先序遍历中前趋、后继的线索二叉树

2.中序线索二叉树: 线索指向中序遍历中前趋、后继的线索二叉树。

3.后序线索二叉树: 线索指向后序遍历中前趋、后继的线索二叉树。

线索二叉树的存储结构

线索二叉树的遍历

(1)先序线索二叉树的遍历

(2)中序线索二叉树的遍历：

哈夫曼（Huffman)树

1.路径长度: 路径上分枝的数目(连线的数目)
2.树T的路径长度: 从树T的根到其余每个结点的路径长度之和,记作PL(T)

当n个结点的二叉树为完全二叉树时,PL(T)具有最小值

当n个结点的二叉树为单枝树时,PL(T)具有最大值
PL(T)=0+1+2+…+(n-1) = n(n-1)/2
1. 树T的带权路径长度: 每个叶子的权与根到该叶子的路径长度的乘积之和，记作WPL(T)
4.哈夫曼树/最佳树/最优树的概念在具有n个相同权值叶子的各二叉树中，WPL(T)最小的二叉树
5.哈夫曼算法