树

1.定义

逻辑结构，n个结点的有限集合。n=0为空树
对任意非空树应满足：
1)有且仅有一个特定称为根的结点；
2)当n>1时，其余结点可称为m(m>0)个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根节点的子树。n个结点的树中有n-1条边；

1.1基本术语：

1)祖先结点和子孙结点；
2)双亲结点(父节点)和孩子结点；
3)兄弟结点;
4)度：树中一个结点的子结点的个数称为该结点的度；树中最大度数称为树的度；
5)分支结点与叶子结点：度大于0称为分支结点；度为0称为叶子结点；
6)结点的层次、结点的高度（从树最低开始）、结点的深度（从根结点开始）；树的高度(深度)是树中结点的最大层数；
7)有序树、无序树：从左至右有次序的树叫做有序树；
8)路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，一定是自上而下的
9)路径长度:路径上所经历边的个数；
10)森林：m(m>=0)棵互不相交的树的集合

1.性质

1)树中的结点数等于所有结点的度数+1；
2)度为m的树中第i层上至多有m^(i-1)个结点(i>=1)；
3)高度为h的m叉树至多有（m^h-1）/(m-1)个结点；
4)具有n个结点的m叉树的最小高度为

5-树 - 图1%2B1)%E4%B8%AA%E7%BB%93%E7%82%B9%0A#card=math&code=log_m%28n%28m-1%29%2B1%29%E4%B8%AA%E7%BB%93%E7%82%B9%0A)

2二叉树

2.1定义

1)根结点和左右子树最多只有两个孩子结点；
2)五种形态：①空树②只有根结点③根结点和左子树④根结点和右子树⑤根结点和左右子树
3)满二叉树：高度为h且含有2^h-1个结点的二叉树为满二叉树；编号为i的结点其左孩子结点为2i，右孩子结点为2i+1,其双亲为i/2取下界;
4)完全二叉树：高度为h,含有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时称为完全二叉树；
5)二叉排序树：对任意结点若存在左子树或右子树，则其左子树上所有结点关键字均小于该结点，右子树上所有结点关键字均大于该结点
6)平衡二叉树：树上任意结点的左子树和右子树的深度只差不超过1

2.2性质

1)非空二叉树的叶子结点数等于度为2的结点数加1，即n0=n2+1;
2)非空二叉树上第K层至多有2^（k-1）个结点(k>=1);
3)高度为h的m叉树至多有（2^h -1）个结点
4)结点i所在层次为[log2 i]+1(去下界)；
5)具有n个结点的完全二叉树的高度为[log2 n]+1 (取下界)或[log2(n+1)] (取上界)

2.2顺序存储结构

利用数组方式进行存储；即将完全二叉树上编号为 l 的结点元素存储在一维数组下标为 i - 1 的分量中

2.3链式存储

含有n个结点的二叉链表中，有n+1个空链域；

  1. typedef struct BitNode
  2. {
  3.     /* data */
  4.     int  data;
  5.     struct BitNode *lchild,*rchild;
  6. }BitNote,*BiTree;

2.4二叉树的遍历

按照某条搜索路径访问树中每个结点，树的每个结点均被访问一次，且只访问一次
三种方式：先序遍历、中序遍历、后序遍历
以如下二叉树为例 1->2->4
->5
->3->6

2.4.1先序遍历

若二叉树非空：访问根结点->左子树->右子树
递归算法：时间复杂度O(n)

  1. void PreOrder(BiTree T){
  2.     if(T != NULL){
  3.         visit(T);//访问根结点
  4.         PreOrder(T->lchild);//访问左结点
  5.         PreOrder(T->rchild);//访问右结点
  6.     }
  7. }//124536

2.4.2中序遍历

若二叉树非空：左子树->根结点->右子树
递归算法：时间复杂度O(n)

  1. void InOrder(BiTree T){
  2.     if(T != NULL){
  3.         InOrder(T->lchild);//访问左结点
  4.         visit(T);//访问根结点
  5.         InOrder(T->rchild);//访问右结点
  6.     }
  7. }//425163

2.4.2后序遍历

若二叉树非空：左子树->右子树->根结点
递归算法：时间复杂度O(n)

  1. void PostOrder(BiTree T){
  2.     if(T != NULL){
  3.         PostOrder(T->lchild);//访问左结点
  4.         PostOrder(T->rchild);//访问右结点
  5.         visit(T);//访问根结点
  6.     }
  7. }//452631

2.4.3层次遍历

  1. void levelOrder(BiTree T){
  2.     InitQueue (Q);//初始化队列
  3.     BiTree p;//建立树
  4.     EnQueue(Q,T);//根结点入队
  5.     while (!isEmpty(Q))
  6.     {
  7.         DeQueue (Q,p);//出队操作
  8.         visit(p);
  9.         if (p->lchild!=NULL)
  10.             EnQueue(Q,p->lchild);
  11.         if(p->rchild!=NULL)
  12.             EnQueue(Q,p->rchild);
  13.     }
  14. }

2.4.4 由遍历序列构造二叉树

例：先序遍历序列124536 注意：由单个序列不能确定唯一的二叉树
(后)先序遍历和中序遍历可以确定一颗二叉树，但后序遍历和先序遍历不可确定一颗二叉树

2.4.4线索二叉树

线索化：
若无左子树，则将左指针指向其前驱结点；
若无右子树，则将右指针指向其后继结点；
增加标志位(tag)若为0指向孩子结点，若为1指向后继(前驱)结点

  1. typedef struct ThreaNode
  2. {
  3.     ElemType data;
  4.     struct ThreaNode *lchild,*rchild;
  5.     int ltag,rtag;
  6. }ThreaNode, * ThreadTree;//线索链表//先序、中序、后序

3树与森林

3.1树的存储结构

3.1.1双亲表示法

采用一种连续的存储空间来存储每个结点，同时在每个结点增设一个伪指针，指示双亲结点在数组中的位置。根结点下标为0，其伪指针域为-1；

  1. #define MaxSize 100
  2. typedef struct {
  3.     ElemType data;
  4.     int parent;
  5. }PTNode;
  6. typedef struct{
  7.     PTNode nodes[MaxSize];
  8.     int n;
  9. }PTree;

3.1.2孩子表示法

将每个结点的孩子结点都用单链表连接起来的线性结构

  1. #define MaxSize 100
  2. typedef struct{
  3.     int child;
  4.     struct CNode *next;
  5. }CNode;
  6. typedef struct{
  7.     ElemType data;
  8.     struct CNode *child;
  9. }PNode;
  10. typedef struct{
  11.     PNode nodes[MaxSize];
  12.     int n;
  13. }CTree;

3.1.3孩子兄弟表示法

以二叉链表作为树的存储结构，使得每个结点包括结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针；

  1. typedef struct CSNode{
  2.     ElemType data;
  3.     struct CSNode *firstchild, *nextsibling;
  4. }CSNode, CStree;

3.2 树、森林&二叉树

3.2.1树与二叉树的转换

左孩子右兄弟。即每个结点的左指针指向它的第一个孩子结点，右指针指向它的兄弟结点

3.2.2森林与二叉树的转换

将每一棵树转换为二叉树，将每个二叉树的根依此作为上一棵树的根兄弟结点

3.2.3树的遍历

1.先根遍历

若树非空，先访问根结点，再按从左到右的顺序遍历根结点的每颗子树；
树的先根遍历序列与这棵树对应的二叉树的先序遍历序列相同

2.后根遍历

若树非空，先按从左到右的顺序遍历根结点的每颗子树，再访问根结点；
树的后根遍历序列与这棵树对应的二叉树的中序遍历序列相同

3.层次遍历

参考二叉树的层次遍历

3.2.4森林的遍历

1.先序遍历

若树非空，则①访问森林中第一棵树的根结点②先序遍历第一棵树的子树森林③先序遍历除去第一棵树之后剩余的树构成的子树森林；

2.中序遍历

若树非空，则①中序遍历第一棵树的根结点的子树森林②访问第一棵树的根结点③中序遍历除去第一棵树之后剩余的树构成的子树森林；单棵树参照后序遍历

3.3树的应用

3.3.1并查集

并查集：一种简单的集合表示。通常树的双亲表示法作为并查集的存储结构

  1. #define MaxSize 100
  2. int UFSets[MaxSize];
  3. //初始化
  4. void Initial (int S[]){
  5.     for (int i=0;i<MaxSize;i++)
  6.         s[i]=-1;
  7. }
  8. //查找操作
  9. int Find (int S[],int x){
  10.     while (S[x]>=0)
  11.         x=S[x];
  12.     return x
  13. }
  14. //合并操作
  15. void Union(int S[],int Root1,int Root2){
  16.     S[Root2]=Root1;
  17. }

3.3.2二叉排序树（BST）/二叉查找树

1)若左子树非空，则左子树所有结点关键字均小于根结点关键字；
2)若右子树非空，则右子树所有结点关键字均大于根结点关键字；
3)左、右子树本身也是一棵二叉排序树；
二叉排序树的中序遍历序列是一个递增有序序列

1.查找

二叉树非空，查找根结点，若相等查找成功；小于时查找左子树，大于时查找右子树，当查找到叶子节点仍没查到则查找失败

2.插入

若二叉树为空，则直接插入结点；
二叉树非空，小于时插入左子树，大于时插入右子树，当值等于根结点时不进行插入；

3.3.3 平衡二叉树（AVL）

任意结点的平衡因子的绝对值不超过1.(平衡因子：左子树高度-右子树高度)
高度为h的最下平衡二叉树的结点数N.N(h)=N(h-1)+N(h-2)+1;N0=0;N1=1;
每次调整最小不平衡子树

1.LL平衡旋转(右单旋转)

在结点A的左孩子的左子树上插入了新结点

2.RR平衡旋转(左单旋转)

在结点A的右孩子的右子树上插入了新结点

3.LR平衡旋转(先左后右双旋转)

在结点A的左孩子的右子树上插入了新结点

4.RL平衡旋转(先右后左双旋转)

在结点A的右孩子的左子树上插入了新结点

3.3.4 哈夫曼树（Haffm）

带权路径长度：树中所有叶节点的带权路径长度之和

5-树 - 图2

哈夫曼树也称最优二叉树，是含有N个带权叶子结点带权路径长度最小的二叉树

最小带权路径(WPL)求法，先求最优哈夫曼树，最后计算带权路径的值

1性质：

1)每个初始结点都会成为叶节点，双支结点都会为新生成的结点;
2)权值越大离根结点越近，反之权值越小离根结点越远;
3)哈夫曼树中没有结点的度为1;
4)n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1;

2.应用

编码：固定长度编码、可变长度编码

4.考题

1.含有n个结点的二叉树共有

5-树 - 图3

2.构造m个哈夫曼树的过程中，有n个叶子结点，则非叶子结点有

5-树 - 图4