一.树(Tree)的定义
由n(n>0)个结点构成的有限集合,当n等于零的时候为空树.
对于任意一棵非空树,它都具备这样的性质:
1.树中有一个成为根(root)的的特殊结点,用r表示.
2.其余结点可以分为m(m>0)个互相不相交的有限集合T1.T2.T3…Tm,其中每个集合本身又是一棵树,称为原来树的子树(SubTree).
树也可以这样定义：树是由根节点和若干棵子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。
二.树的一些基本术语:
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
节点的度：一个节点含有的子节点的个数称为该节点的度；
叶节点或终端节点：度为0的节点称为叶节点；
非终端节点或分支节点：度不为0的节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
树的度：一棵树中，最大的节点的度称为树的度；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：双亲在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
森林：由棵互不相交的树的集合称为森林。
三.树的表示方法:
1.双亲表示法
2.孩子表示法
3.孩子兄弟表示法
1.双亲表示法
双亲表示法取一块连续的内存空间，在存储每个结点的同时，各自都附加一个记录其父结点位置的变量。在树结构中，除了树根外，每个结点都只有一个父结点（又叫“双亲结点”）。
优点:容易找到树中的父结点.
缺点:不容易找到树中的子结点.
#define size 100 //定义树中结点的最大数量
typedef struct PTNode
{
int data; //树中结点的数据类型
int parent; //结点的父结点在数组中的位置下标
}PTNode;
typedef struct
{
PTNode nodes[size]; //存放树中所有结点
int r, n; //根的位置下标和结点数
}PTree;
2.孩子表示法
将树中的每个结点的孩子结点排列成一个线性表，用链表存储起来。对于含有 n 个结点的树来说，就会有 n 个单链表，将 n 个单链表的头指针存储在一个线性表中，这样的表示方法就是孩子表示法。
优缺点:使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。这是因为单链表只能查下不能查上的原因.
#define Size 100
typedef struct CTNode
{
int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
struct CTNode *next;
}*ChildPtr;
typedef struct
{
int data; //结点的数据类型
ChildPtr firstchild; //孩子链表的头指针
}CT;
typedef struct
{
CT nodes[Size]; //存储结点的数组
int n, r; //结点数量和树根的位置
}CTree;
3.孩子兄弟表示法
使用链式存储结构存储普通树。其中孩子指针域，表示指向当前结点的第一个孩子结点，兄弟结点表示指向当前结点的下一个兄弟结点。
typedef struct CSNode
{
int data;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
四.二叉树
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分.
1.二叉树的定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树.
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树 [4] 。
完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1
2.二叉树的性质
性质1：二叉树的第i层上至多有2^(i-1)（i≥1）个节点。
性质2：深度为h的二叉树中至多含有2^h-1个节点 。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的完全二叉树深为logx+1（其中x表示不大于n的最大整数)。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点;
当i=1时，该节点为根，它无双亲节点 。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。
3.二叉树的存储方式
3.1顺序存储
3.2链式存储
typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
int Data; /* 结点数据 */
BinTree Left; /* 指向左子树 */
BinTree Right; /* 指向右子树 */
};
4.二叉树的四种遍历
4.1先序遍历
1.访问根节点
2.用先序遍历的方式访问左子树
3.用先序遍历的方式访问右子树
void PreorderTraversal(BinTree BT)
{
if (BT) {
printf("%d ", BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
图解:
1.先访问根结点A
2.根据先序遍历的规则,遵循递归调用,首先访问左子树
故ABD
3.访问到D的时候由于没有左子树,因此回溯到B开始访问右子树
故FE.
4.根结点A的左子树访问完了开始访问右子树,道理同上,访问的顺序为
CGHI
5.故访问的总顺序为A/BDFE/CGHI
4.2中序遍历
1.用中序遍历访问左子树
2.访问根节点
3.用中序遍历访问右子树
void InorderTraversal(BinTree BT)
{
if (BT) {
InorderTraversal(BT->Left);
printf("%d ", BT->Data);
InorderTraversal(BT->Right);
}
}
图解同先序遍历,只是读取数据的时机不同
DBEF/A/GHCI
注意:G和H的顺序由于G没有左子树,所以经过G的时候是两次故G在H的前面.
4.3后序遍历
1.用后序遍历访问左子树
2.用后序遍历访问右子树
3.访问根节点
void PostorderTraversal(BinTree BT)
{
if (BT) {
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
图解同上只是在读取结点数据的时机不同.
DEFB/HGIC/A
4.4前中后序遍历总结
先序,中序,后序遍历的过程:遍历过程中的路线是一样的,只是读取结点上数据的时机不一样.
遍历左子树算一次接触;
遍历右子树算一次接触;
读取结点数据是算一次接触;
**总结:**前序遍历便是第一次接触便读取数据的顺序
中序遍历便是第二次接触便读取数据的顺序
后序遍历便是第三次接触便读取数据的顺序
注意:叶结点第一次经过时算三次接触,只有一个右子结点的父结点第一次经过时算两次接触.只有一个左子结点的父结点第二次经过时算两次接触.
4.5层序遍历
1.根节点入队
2.访问队首元素，左儿子若不为空则左子叶入队，右儿子若不为空则入队
3.队首元素出队
4.重复3 、4步骤，直到队列为空为止
void LevelorderTraversal(BinTree BT)
{
Queue Q;
BinTree T;
if (!BT) return; /* 若是空树则直接返回 */
Q = CreatQueue(); /* 创建空队列Q */
AddQ(Q, BT);
while (!IsEmpty(Q)) {
T = DeleteQ(Q);
printf("%d ", T->Data); /* 访问取出队列的结点 */
if (T->Left) AddQ(Q, T->Left);
if (T->Right) AddQ(Q, T->Right);
}
}
五.二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
5.1二叉搜索树的性质
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树。
5.2二叉排序树的操作主要有
1.查找
BinTree Find(int x,BinTree BST)
{
while(BST)
{
if(X>BST->Data)
BST=BST->Right;
else if(X<BST->Data)
BST=BST->Left;
else
return BST;
}
return NULL;
}
2.插入
BinTree Insert( BinTree BST, int X )
{
if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
BST = (BinTree)malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}
else { /* 开始找要插入元素的位置 */
if( X < BST->Data )
BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/
else if( X > BST->Data )
BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
/* else X已经存在，什么都不做 */
}
return BST;
}
3.删除
（1）叶子节点：直接删除，不影响原树。
（2）仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。
（3）既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。
BinTree Delete( BinTree BST, ElementType X )
{
Position Tmp;
if( !BST )
printf("要删除的元素未找到");
else {
if( X < BST->Data )
BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */
else if( X > BST->Data )
BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
else { /* BST就是要删除的结点 */
/* 如果被删除结点有左右两个子结点 */
if( BST->Left && BST->Right ) {
/* 从右子树中找最小的元素填充删除结点 */
Tmp = FindMin( BST->Right );
BST->Data = Tmp->Data;
/* 从右子树中删除最小元素 */
BST->Right = Delete( BST->Right, BST->Data );
}
else { /* 被删除结点有一个或无子结点 */
Tmp = BST;
if( !BST->Left ) /* 只有右孩子或无子结点 */
BST = BST->Right;
else /* 只有左孩子 */
BST = BST->Left;
free( Tmp );
}
}
}
return BST;
}
六.平衡二叉树
平衡二叉树树指的是，任意节点的子树的高度差都小于等于1.
平衡因子:BF(T)=h左-h右.
6.1平衡二叉树的调整
RR
LL
RL
LR
typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
ElementType Data; /* 结点数据 */
AVLTree Left; /* 指向左子树 */
AVLTree Right; /* 指向右子树 */
int Height; /* 树高 */
};
int Max ( int a, int b )
{
return a > b ? a : b;
}
AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B */
/* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
return B;
}
AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
/* 将A、B与C做两次单旋，返回新的根结点C */
/* 将B与C做右单旋，C被返回 */
A->Left = SingleRightRotation(A->Left);
/* 将A与C做左单旋，C被返回 */
return SingleLeftRotation(A);
}
AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->Data = X;
T->Height = 0;
T->Left = T->Right = NULL;
} /* if (插入空树) 结束 */
else if ( X < T->Data ) {
/* 插入T的左子树 */
T->Left = Insert( T->Left, X);
/* 如果需要左旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
if ( X < T->Left->Data )
T = SingleLeftRotation(T); /* 左单旋 */
else
T = DoubleLeftRightRotation(T); /* 左-右双旋 */
} /* else if (插入左子树) 结束 */
else if ( X > T->Data ) {
/* 插入T的右子树 */
T->Right = Insert( T->Right, X );
/* 如果需要右旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
if ( X > T->Right->Data )
T = SingleRightRotation(T); /* 右单旋 */
else
T = DoubleRightLeftRotation(T); /* 右-左双旋 */
} /* else if (插入右子树) 结束 */
/* else X == T->Data，无须插入 */
/* 别忘了更新树高 */
T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
return T;
}
七.哈夫曼树
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
7.1哈夫曼树的构造
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
7.2堆
用于实现哈夫曼树
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(Ki>K2i且Ki>K2i+1)或者(Ki<K2i且Ki<K2i+1)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
最大堆建立实例,最小堆同理:
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
ElementType *Data; /* 存储元素的数组 */
int Size; /* 堆中当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */
#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
return H;
}
bool IsFull( MaxHeap H )
{
return (H->Size == H->Capacity);
}
bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf("最大堆已满");
return false;
}
i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
for ( ; H->Data[i/2] < X; i/=2 )
H->Data[i] = H->Data[i/2]; /* 上滤X */
H->Data[i] = X; /* 将X插入 */
return true;
}
#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
bool IsEmpty( MaxHeap H )
{
return (H->Size == 0);
}
ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
int Parent, Child;
ElementType MaxItem, X;
if ( IsEmpty(H) ) {
printf("最大堆已为空");
return ERROR;
}
MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
/* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
return MaxItem;
}
/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
X = H->Data[p]; /* 取出根结点存放的值 */
for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
}
void BuildHeap( MaxHeap H )
{ /* 调整H->Data[]中的元素，使满足最大堆的有序性 */
/* 这里假设所有H->Size个元素已经存在H->Data[]中 */
int i;
/* 从最后一个结点的父节点开始，到根结点1 */
for( i = H->Size/2; i>0; i-- )
PercDown( H, i );
}
7.3哈夫曼树的实现
实现哈夫曼编码的方式主要是创建一个二叉树和其节点。这些树的节点可以存储在数组里，数组的大小为符号（symbols）数的大小n，而节点分别是终端节点（叶节点）与非终端节点（内部节点）。
一开始，所有的节点都是终端节点，节点内有三个字段：
1.符号（Symbol）
2.权重（Weight、Probabilities、Frequency）
3.指向父节点的链接（Link to its parent node）
而非终端节点内有四个字段：
1.权重（Weight、Probabilities、Frequency）
2.指向两个子节点的链接（Links to two child node）
3.指向父节点的链接（Link to its parent node）
基本上，我们用’0’与’1’分别代表指向左子节点与右子节点，最后为完成的二叉树共有n个终端节点与n-1个非终端节点，去除了不必要的符号并产生最佳的编码长度。
过程中，每个终端节点都包含着一个权重（Weight、Probabilities、Frequency），两两终端节点结合会产生一个新节点，新节点的权重是由两个权重最小的终端节点权重之总和，并持续进行此过程直到只剩下一个节点为止。
实现哈夫曼树的方式有很多种，可以使用优先队列（Priority Queue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：
⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n
⒉如果队列内的节点数>1，则：
⑴从队列中移除两个最小的Pi节点，即连续做两次remove（min（Pi）, Priority_Queue)
⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和
⑶把（2）产生之节点加入优先队列中
⒊最后在优先队列里的点为树的根节点（root）
而此算法的时间复杂度（Time Complexity）为O（n log n）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log n）。
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
}
HuffmanTree Huffman( MinHeap H )
{ /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
int i; HuffmanTree T;
BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/
T = malloc( sizeof( struct TreeNode) ); /*建立新结点*/
T->Left = DeleteMin(H);
/*从最小堆中删除一个结点，作为新T的左子结点*/
T->Right = DeleteMin(H);
/*从最小堆中删除一个结点，作为新T的右子结点*/
T->Weight = T->Left->Weight+T->Right->Weight;
/*计算新权值*/
Insert( H, T ); /*将新T插入最小堆*/
}
T = DeleteMin(H);
return T;
}
学数据结构快一个月了,只能说对于我来说还是有点难,特别时图那个部分,只能说加油吧!毕竟22年的考研还有一个月,对于23年的考生我来说,我有时间加油加油.
整理树的学习笔记一万五千个字了,大家给个赞吧谢谢大家了,图片大多数来自浙大的数据结构mooc,毕竟我自学看的就是这个嘻嘻嘻.
最后还是一天一句的鸡汤文:
失败是什么？没有什么，只是更走近成功一步；成功是什么？就是走过了所有通向失败的路，只剩下一条路，那就是成功的路。
哎,别人失败可以继续选择,但是我失败了一次可能就无了啊,啥也不是,好好加油吧!
最后各位大佬给个赞吧.