树和快速排序
定义
专业定义：
1.有且只有一个称为根的节点
2.有若干个互不相交的子树，这些子树本身也是一棵树
通俗的定义：
1.树是由节点和边组成
2.每个节点只有一个父节点但可以有多个子节点
3.但有一个节点例外，该节点没有父节点，此节点称为根节点。
专业术语
节点 父节点 子节点
深度：从根节点到最底层节点的层数称为深度 根节点是第一层
叶子节点：没有子节点的节点
非终端节点：实际就是非叶子节点
度：子节点的个数称为度
分类
1.一般树：任意一个节点的子节点的个数都不受限制
2.二叉树：任意一个节点的子节点个数最后有两个，且子节点的位置不可更改
分类：一般二叉树
满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树
完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树
3.森林：n个互不相交的树的集合
树的存储
1.二叉树的存储
连续存储[完全二叉树]
优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度快
缺点：耗用内存空间过大
链式存储
2.一般树存储
2.1双亲表示法：求父节点方便
2.2孩子表示法：求子节点方便
2.3双亲孩子表示法：求父节点和子节点都很方便
2.4二叉树表示法：把一个普通树转换为二叉树来存储
具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的兄弟，只要能满足此条件，就可以吧一个普通树转换成二叉树
具体图：
IMG_20200212_174102.jpg
IMG_20200212_174117.jpg
3.森林存储：就是把几个树组成一个二叉树 A，B，G分别为树
IMG_20200212_180836.jpg
遍历
1.先序遍历[先访问根节点]
先访问根节点
再先序访问左子树
再先序访问右子树
2.中序遍历[中间访问根节点]
中序遍历左子树
再访问根节点
再中序遍历右子树
3.后序遍历[最后访问根节点]
先中序遍历左子树
再中序遍历右子树
再访问根节点
已知两种遍历序列求原始二叉树
只有通过先序和中序 或者通过中序和后序才能唯一确定一个二叉树
fc36336ad27b7f6162637e7e9fb1941.jpg
# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
typedef struct BTNode{
char data;
struct BTNode * pLchild;
struct BTNode * pRchild;
}BTNODE,* PBTNODE;
void PreTraverseBTree(PBTNODE pT);
void InTraverseBTree(PBTNODE pT);
void PostTraverseBTree(PBTNODE pT);
PBTNODE CreateBTree(void);
int main(void){
PBTNODE pt = CreateBTree();
printf("先序遍历：\n");
PreTraverseBTree(pt);
printf("中序遍历：\n");
InTraverseBTree(pt);
printf("后序遍历：\n");
PostTraverseBTree(pt);
}
PBTNODE CreateBTree(void){
PBTNODE pA = (PBTNODE)malloc(sizeof(BTNODE));
PBTNODE pB = (PBTNODE)malloc(sizeof(BTNODE));
PBTNODE pC = (PBTNODE)malloc(sizeof(BTNODE));
PBTNODE pD = (PBTNODE)malloc(sizeof(BTNODE));
PBTNODE pE = (PBTNODE)malloc(sizeof(BTNODE));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLchild = pB;
pB->pLchild = NULL;
pB->pRchild = NULL;
pA->pRchild = pC;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = NULL;
pE->pRchild = NULL;
return pA;
}
void PreTraverseBTree(PBTNODE pT){
if(NULL != pT){
printf("%c\n",pT->data);
if(NULL != pT->pLchild){
PreTraverseBTree(pT->pLchild);
}
if(NULL != pT->pRchild){
PreTraverseBTree(pT->pRchild);
}
}
}
void InTraverseBTree(PBTNODE pT){
if(NULL != pT){
if(NULL != pT->pLchild){
InTraverseBTree(pT->pLchild);
}
printf("%c\n",pT->data);
if(NULL != pT->pRchild){
InTraverseBTree(pT->pRchild);
}
}
}
void PostTraverseBTree(PBTNODE pT){
if(NULL != pT){
if(NULL != pT->pLchild){
PostTraverseBTree(pT->pLchild);
}
if(NULL != pT->pRchild){
PostTraverseBTree(pT->pRchild);
}
printf("%c\n",pT->data);
}
}
搜狗截图20200215213147.png
应用
1.数是数据库中数据组织的一种重要形式
2.操作系统子父进程的关系本身就是一棵树
3.面向对象语言中类的继承关系本身就是一棵树
4.赫夫曼树
快速排序
先用一个变量 val 保存第一个数的值，之后找到其在排序中的位置，如果后面的值大于val（不大于则移动H），则将值赋值给前面，如果前面的值大于 val ，则将值赋值给后面， 如果前面的值小于 val ,则移动变量 l ,不进行赋值。
fd1c241a83b8e5350cf8b50f3edbc83.jpg
# include<stdio.h>
int FindPos(int *a,int low,int high);
void QuickSort(int *a,int low,int high);
int main(void){
int a[6] = {-1,-23,4,23,-980,2};
QuickSort(a,0,5);
for(int i = 0;i < 6;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
void QuickSort(int *a,int low,int high){
int pos;
if(low < high){
pos = FindPos(a,low,high);
QuickSort(a,low,pos -1);
QuickSort(a,pos +1,high);
}
}
int FindPos(int *a,int low,int high){
int val = a[low];
while(low < high){
//如果后面的数字小于第一个数，则将其换到前面
while(low < high && a[high] >= val)
high--;
a[low] = a[high];
//如果前面的数字大于第一个数，就将其与后的交换
while(low < high && a[low] <= val)
low++;
a[high] = a[low];
}
a[low] = val;
return high;
}
搜狗截图20200215213328.png
