文章目录
1. 树
-
树是一个递归的定义，树是由子树组成的，子树又是由子树的子树组成这样嵌套下去
-
根节点（root）：第一个节点，没有前驱结点。
-
度：结点拥有子树的个数（每个结点有两个：二叉树；每个结点有三个：三叉树）
-
树的度：树内结点度的最大值
-
树的深度：树的层数
-
有序树：树中节点的各子树从左到右有次序
-
森林：由m棵不相交的树的集合
树一定是森林，森林不一定是树 -
树： 只有一个前趋结点，0个或多个后趋结点，根结点没有前趋结点
-
父节点：有一个节点的上一个节点。根节点没有父节点。
-
兄弟节点：同层的节点。
-
中间节点：有父节点且有子节点的节点。
-
叶子节点：最后一层节点没有后面的。
-
树逻辑的作用：
用来描述或存储具有层级的数据，即非线性逻辑的数据。
2. 二叉树
- 每个结点最多有两个子树（左子树，右子树）
- 二叉树的子树要严格区分左右，即使只有一个子树也要区分左子树还是右子树，其顺序颠到之后是另外一个二叉树
- 当整个树只有两个节点的话，就不需要分左右子树
2.2 二叉树的性质
- 二叉树的第i层上有2^（i-1）个结点
- 深度为k的二叉树，最多有（2^k）-1个结点；最少有K个结点（每层只有一个）
- 任何一棵二叉树T，如果叶子树为n0，度为2的结点数为n2，则n0=n2+1
- 具有n个节点的完全二叉树深度为[log_2n]+1
- 如果对一棵有n个节点的完全二叉树的节点按程序编号，则对任意节点i有:
- 如果i=1则节点i是二叉树的根无双亲；如果a>1则其双亲是节点[i/2]
2.如果2i>n，则节点a为子，节点无左孩子,否则其左孩子是节点时孩子2i - 如果2i+1>n,则节点无右孩子，否则其右孩子是结点2i+1。
- 如果i=1则节点i是二叉树的根无双亲；如果a>1则其双亲是节点[i/2]
满二叉树
每一层上的结点都是满的。
完全二叉树
在满二叉树中，从最后一个节点开始，连续去掉任意一个相连的节点，既是一颗完全二叉树。
- 满二叉树也是一个完全二叉树，但是完全二叉树不是满二叉树
2.3二叉树的遍历
二叉树的遍历有四种：前序遍历，中序遍历，后序遍历，层序遍历
- 调用的方法是递归调用
前序遍历
- 输出顺序是：根左右，先输出根，然后先左后右，如果左边也是一个小根的话，也是先把左边小根的输出出完（左侧小根也是根左右的顺序），然后再输出右侧的小根
中序遍历
- 输出顺序是：左根右，先输出左边的，然后再根，最后后右。
后序遍历
- 输出顺序是：左右根，先左后右，最后输出根。
- 已知一个二叉树，其各节点值不一样，得到的前中后序序列都是唯一的，
- 已知（前序+中序），（后序+中序）可以确定一个唯一的二叉树
二叉树的建立
struct CreateRiTree(BiTree &T)
{
cin >> ch ;
if(ch=="#")
{
T=NULL;
}
else
{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
{
T = new BiTNode ;
}
T->data = ch; //生成根节点
CreateRiTree(T->LChild); //创建左子树
CreateRiTree(T->RChild); //创建右子树
}
return OK；
}
递归遍历算法
先序遍历算法
struct PerOrderTraverse(BiTree T)
{
if(T = NULL)
{
return ok;
}
else
{
cout << T->data; //先输出根结点
PerOrderTraverse(T->LChild);
PerOrderTraverse(T->RChild);
}
}
中序遍历算法
struct PerOrderTraverse(BiTree T)
{
if(T = NULL)
{
return ok;
}
else
{
PerOrderTraverse(T->LChild);
cout << T->data;
PerOrderTraverse(T->RChild);
}
}
后序遍历算法
struct PerOrderTraverse(BiTree T)
{
if(T = NULL)
{
return ok;
}
else
{
PerOrderTraverse(T->LChild);
PerOrderTraverse(T->RChild);
cout << T->data;
}
}
遍历算法的分析
时间效率：O(n) 每个结点都要访问一次
空间效率：O(n) 栈占用的最大辅助空间
非递归遍历算法
- 用栈来实现
- 建立一个栈
- 根结点进栈，遍历左子树
- 根结点出栈，输出根结点，遍历右子树
复制二叉树
int Copy(BiTree T, BiTree &NewT)
{
//如果树为空，递归结束
if(T==NULL)
{
NewT = NULL;
retrun 0;
}
//否则申请新空间，复制根结点
else
{
// 申请新空间给要被复制的新量
NewT = new BiTNode;
// 把原数据赋值给新量
NewT->data = T->data;
// 同样递归的方法，把原来左子树分的值赋值给新的左子树
Copy(T->LChild, NewT->LChild);
Copy(T->RChild, NewT->RChild);
}
}
计算二叉树的深度
- 如果是空树，深度为0；
- 否则，递归计算左子树深度记作m，递归计算右子树深度记作n
- 深度为取n,m中较大的那个数+1，
int Depth(BiTree T)
{
// 判断树是否为空
if(T==NULL)
{
return 0;
}
// 不为空的情况下，同样求左右子树的深度
else
{
m= Depth(T->LChild);
n= Depth(T->RChild);
// +1 是因为深度要在左右子树的基础上在加上根结点
return (n>=m?n:m)+1;
}
}
计算二叉树的结点数
- 判断如果空树结点数为0
- 结点数=左节点数+右节点数+1
int NodeCount(BiTree T)
{
// 如果空树结点数为0
if(T==NULL)
{
return 0;
}
else
{
// 结点数=左节点数+右节点数+1
return NodeCount(T->LChild)+NodeCount(T->RChild)+1;
}
}
计算二叉树的叶子结点数
- 判断如果空树结点数为0
- 叶子结点数=左节点叶子结点数+右节点叶子结点数
int LeafCount(BiTree T)
{
// 如果空树叶子结点数为0
if(T==NULL)
{
return 0;
}
// 只要一个根结点，叶子数为1
if(T->LChild==NULL&&T->RChild==NULL)
{
return 1;
}
else
{
return LeafCount(T->LChild)+LeafCount(T->RChild);
}
}
2.4 线索二叉树
二叉树在寻找她的左右孩子很方便，但是无法直接寻找该节点在某种序列中的前驱结点和后继节点
-
解决方法：利用二叉链表中的空指针域
每个接结点又有左右两个指针域，N个的二叉树有2N个指针域，但是最多只有N-1个子节点，多余除了N+1个指针域- 如果结点无左孩子，就将空着的左孩子的指针域改为指向其前驱
- 如果结点无右孩子，就将空着的右孩子的指针域改为指向其后继
- 这种改变指针指向的指针称为线索
- 注：如果一个结点左右孩子都有，那么就不可以改变指针的指向，也就没有线索
-
为了区分LChild和RChild指针是指向孩子结点，还是前后趋结点，在二叉链表中增加两个标志域，ltag和rtag
- ltag=0：LChild指向结点的左孩子
- ltag=1：LChild指向结点的前驱
- rtag=0：RChild指向结点的右孩子
- rtag=1：RChild指向结点的后驱
3. 森林
是N（N>=0）棵互不相交的树的集合
3.1 树的存储结构
双亲表示法
| 数组下标 | 数据 | 双亲下标 |
|---|---|---|
| 0 | R | -1 |
| 1 | A | 0 |
| 2 | B | 0 |
| 3 | C | 0 |
| 4 | D | 1 |
| 5 | E | 1 |
| 6 | F | 3 |
| 7 | G | 6 |
| 8 | H | 6 |
| 9 | H | 6 |
typedef struct PTNode
{
TElemType data;
int parent // 记录双亲节点的位置
}
- 特点：找双亲容易，找孩子结点难
孩子链表表示法
把每个节点的孩子孩子排列起来，看成是一个线性表，用单链表存起来，N个结点有N个孩子链表。每个孩子链表并不存放具体数据，而是存放该孩子结点的地址，也为孩子结点数据已经存储了，而且该孩子结点可能有自己的孩子结点，在存储她的数据就会造成浪费
孩子结点的结构:child next
typedef struct CTNode
{
int child;
struct CTNode *next;
}*childPtr;
双亲结点的结构 data firstchild
typedef Struct
{
TELemType data;
ChildPtr firstchild; // 孩子链表的标头指针
}CTBox;
- 找孩子容易，找双亲比较困难
孩子兄弟表示法
有二叉树的形式来存储，链表中每个结点有两个指针，左边指针指向第一个孩子结点，右边指针指向下一个兄弟结点
typedef struct CSNode
{
ElemType data;
struct CSNode *firstChild *nextSibling;
}CSNode,*CSTree;
把树树转成二叉树
树的每个结点可能有多个子树，要想转化为二叉树，需要转化，把一个结点的左节点指向她的第一个子节点，右节点指向他的下一个兄弟结点
森林转化为二叉树
- 将森林中的每棵树转化成二叉树
- 将每棵树的根节点用线连起来
- 以第一棵树的很结点作为整个二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构
二叉树转换回森林
去掉全部右孩线，孤立二叉再还原
3.2 树的遍历
- 二叉树的遍历有四种：前序，中序，后序，层次
- 树的遍历有三种：前序，后序，层次
- 先序遍历：树不为空，先访问根结点，然后依次遍历各子树。
- 后序遍历：树不为空，线依次遍历各课子树，然后访问根结点
- 层次遍历：自上而下，从左到右，访问书中的每个节点。
4. 哈斯曼树
哈斯曼树是用来构造最优二叉树的
-
路径：从树中一个结点到另一个结点之间要经过的分支，这些分支构成两个结点间的路径
-
路径长度：连接点之间分支的个数
-
树的路径长度：从树根到每个节点的路径长度之和，记作:LT
- 结点数相同的二叉树中，完全二叉树的路径长度最短，但是路径长度最短的二叉树不一定都是完全二叉树
-
权：给树的结点辅一个有着某种意义的值，这个值成为该节点的权。（意义根据二叉树使用的场合而定）
-
结点的带权路径长度：（从根结点到该结点之间的路径长度）×（该节点的权）
-
树的的带权路径长度：树的所有叶子结点的带权路径长度之和
哈斯曼树：带权路径长度最短的树
是在度相同的树中比较而得的结果，因此有最优二叉树、最优三叉树之称
4.1 哈斯曼树的构造
- 把所有数据都设置成根结点
- 在在所根结点中，选出两个最小的结点a、b，构成一个二叉树,a和b的根结点为新生成的c，c的权=a权+b权，同时在原来所有根结点中删除a、b。
- 在从现有根结点中在挑选出两个最小的生成二叉树，这里包含上一步a、b生成的新结点c
- 不断重复两个小树生成一个新树，直到构成一个二叉树位置
- 总结
- 哈斯曼算法中，初始有N棵二叉树，要经过N-1次合并，且最终形成2N-1个新结点，并且最终形成的新节点又具有2个子树分支。
- 哈斯曼树的结点度数为0或2，没有度为1的结点
- 哈斯曼树具有N(叶子)+N-1(新添加的根)=2N-1(共有结点数)，且所有结点的度都不为1
哈斯曼树的算法实现
// 结点类型定义
typedef struct
{
int weight; //结点的权值
int parent,Lch,Rch;
}HTNode,*HuffmanTree;
// 初始化哈斯曼树
void CreatHuffmanTree(HuffManTree HT, int n)
{
if(n<1) // 结点数为0，退出
{
return ;
}
int m=2*n-1; // n个结点组成二叉树结点共2n-1个元素
HT = new HtNode[m+1] // 0号单元不使用，HT[m]就便是根结点。
for(int i=1;i<=m;++i) // 将2n-1个元素的parent,Lch,Rch都设置为0
{
HT[i].Lch=0;
HT[i].Rch=0;
HT[i].parent=0;
}
for(int i=1;i<n;++i) // 输入前n个元素的weight值
{
cin >> HT[i].weight;
}
}
// 构造哈斯曼树
for(i=n+1;i<=m;i++) // 合并产生n-1个新结点——构造哈斯曼树（1-n为原有结点，n+1-2n-1为新生成的结点）
{
Select(HT,i-1,s1,s2); // 在原有1-n个结点中选择处2个双亲为0,
// 并且权重最小的结点
// 并返回他们在HT表中的序号s1,s2
HT[s1].parent=i; // 表示从表中删除s1,s2
HT[s2].parent=i;
HT[i].Lch=s1; // s1,s2分别作为i的左右孩子
HT[i].Rch=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight; // i的权值为左右孩子的权值之和
}
哈斯曼编码
为每个字符设置二进制编码的时候，每一位都要有相同的位数，为一些出现次数多的数据设置段的编码，可以节省存储空间，但是设计编码的时候，这些特殊的编码，不能是其它正常编码的前缀。
设计前缀码，同时让电文总长最短——哈斯曼编码
- 统计字符集中每个字符出现的概率。
- 利用哈斯曼树的特点，字符的概率值为其权值，构造哈斯曼树，权值越大，路径越短
- 哈斯曼树每个分支：左分支记为0，右分支记为1
- 每个分支都有1或0，每个结点的编号就是从根结点到这个结点的所有分支上的数连起来，从根结点的数开始大头
哈斯曼编码的代码实现
// 从子叶向根逆向求每个字符的哈斯曼编码，存储在编码表HC中
void CreatHuffmanCode(HuffmanTreee HT,HuffmanCode &HC ,int n)
{
HC = new char*[n+1]; // 分配n个字符编码的指针矢量
cd = new char[n]; // 分配临时存放编码的动态数组空间
cd[n-1] = '0'; // 编码结束标志符
for(i=1;i<n;i++) // 逐个字符求哈斯曼编码
{
start = n+1;
c=i;
f=HT[i].parent;
while(f!=0) // 从子叶节点开始向上回溯，直达根结点
{
--start; // 回溯一次start向前指一个位置
if(HT[f].lchild==c) // 结点C是f的左孩子，则生成代码0
{
cd[start]='0';
}
else // 结点C是f的右孩子，则生成代码1
{
cd[start]='1';
}
c = f; // 继续向上回溯
f = HT[f].parent;
} // 求出第i个字符编码
HC[i] = new char[n-start]; // 为第i个字符串编码分配空间
strcpy(HC[i],&cd[start]); // 讲求的的编码从临时空间cd复制到HC的当前行中
delete cd; // 释放临时空间
}
}