1.树概念及结构
1.1树的概念
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
- 有一个特殊的结点,称为根结点,根节点没有前驱结点
- 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
- 因此,树是递归定义的。
【注意】:树形结构中,子树之间不能有交集,否则就不是树形结构
1.2 树的相关定义
- 节点的度:子树的个数
- 叶节点或终端节点:度为0的节点称为叶节点
- 分支节点:度不为0的节点
- 兄弟节点:具有相同父节点的节点
- 树的度:树最大的节点的度
- 节点的层次:根为第1层,根的子节点为第2层,以此类推
- 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟
- 祖先:从根到该节点所经分支上的所有节点
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙
- 森林:由m(m>0)棵互不相交的树的集合称为森林;
根据上图,读懂这一段话就没问题啦,A的度是6,PQ是叶,DE是分支节点也是兄弟节点,树的度为6,A为第一层,树的高度为4,HI是堂兄弟结点,A是祖先,其余的都是子孙
重点理解度:结点连接的子树个数
1.3 树的表示
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间 的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。
表示文件系统的目录树结构
2.二叉树概念及结构
2.1概念
一棵二叉树是结点的一个有限集合,可以帮其想象为一颗计划生育的树
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
3. 最大度为2
4. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:
2.2现实中的二叉树
哈哈膜拜一下
2.3 特殊的二叉树
1. 满二叉树:如果每一个层的结点数都达到最大值。也就是说,如果一个二叉树的层数为K,且结点总数是 2^k-1,则它就是满二叉树。
2. 完全二叉树:完全二叉树是效率很高的数据结构,最后一层从左到右排,可以不排满。满二叉树是一种特殊的完全二叉树。 长度为h的完全二叉树,节点数量的范围[ 2^(h-1) , 2^h-1]
2.4 二叉树的性质
1. 非空二叉树的第i层上最多有 2^(i-1) 个结点.
2. 深度为h的二叉树的最大结点数是2^h-1 .
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n(0)=n(2)+1
以满二叉树理解, i 层(即度为0)是2^(i-1) , 以上(i-1)层(即度为2)有节点2^(i-1)-1
4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= . (log以2 为底,n+1为对数)
5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,奇为左孩子,偶为右孩子,双亲为(i-1)/2
2.5 二叉树的存储结构
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
1. 顺序结构,数组存储(完全二叉树适用)
2.链式结构,链表实现 (后面红黑树,会涉及到三叉链表)
模拟实现:
3.二叉树的顺序结构及实现
3.1 二叉树的顺序结构--堆
完全二叉树更适合使用顺序结 构存储。通常把堆(一种二叉树)使用顺序结构的数组来存储
【区分】
二叉树堆:一种数据结构
虚拟进程地址空间中的堆:操作系统中管理内存的一块区域分段。
小堆头最小,大堆头最大
3.2 堆的实现
3.2.1打印
//打印 void HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; ++i) { printf("%d ", php->a[i]); } printf("\n"); }
3.2.2 堆向下调整算法
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
模拟实现如下:
//向下调整 void Adjustdown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child])//找出两个孩子中较大的那个 { ++child; } if (a[child] > a[parent])//此为大堆,如果要实现小堆则 改 > { swap(&a[child], &a[parent]); //实现值的交换,向下继续遍历 parent = child; child = parent * 2 + 1; } else { break; } } }
以此类推:向上调整
//向上调整 void Adjustup(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent])//建大堆,小堆则< { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
3.2.3 堆的创建
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的 子树开始调整,一直调整到根节点的树,就可以调整成堆。
void HeapCreate(Heap* hp, HPDataType* a, int n) { assert(hp); assert(a); hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (!hp->_a) { perror("malloc fail"); exit(-1); } hp->_capacity = hp->_size = n; //将a中的元素全部转移到堆中 memcpy(hp->_a, a, sizeof(HPDataType) * n); //从最后一位开始遍历调整 for (int i = n; i >0; i--) { Adjustup(hp->_a, i);//按向上调整,此建立大堆 } }
建堆的时间复杂度为O(N)
3.2.4 堆的插入
先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_capacity == hp->_size)//扩容 { int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2; HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity); if (!new) { perror("realloc fail"); exit(-1); } hp->_a = new; hp->_capacity = newcapacity; } hp->_a[hp->_size++] = x; Adjustup(hp->_a, hp->_size - 1); }
!!!3.2.5 堆的删除
删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据交换,然后删除数组最后一个数据,再进行向下调 整算法。
//删除堆顶 void HeapPop(Heap* hp)//先将最后一个数与堆顶交换,然后再让size--,再进行向下调整 { assert(hp); swap(&hp->_a[0], &hp->_a[hp->_size - 1]); hp->_size--; Adjustdown(hp->_a, hp->_size, 0); }
3.2.6 堆的代码实现
.h:
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #include<string.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void AdjustDown(HPDataType* a, int n, int parent); void AdjustUp(HPDataType* a, int child); void Swap(HPDataType* p1, HPDataType* p2); // 堆的构建 void HeapCreate(HP* hp, HPDataType* a, int n); void HeapPrint(HP* php); void HeapInit(HP* php); void HeapDestroy(HP* php); // 保持他继续是一个堆 O(logN) void HeapPush(HP* php, HPDataType x); // 删除堆顶的数据,并且保持他继续是一个堆 O(logN) void HeapPop(HP* php); HPDataType HeapTop(HP* php); int HeapSize(HP* hp); // 堆的判空 bool HeapEmpty(HP* hp);
heap .c:
#include"pile.h" //交换的模拟实现 void swap(HPDataType* s1, HPDataType* s2) { HPDataType temp = *s1; *s1 = *s2; *s2 = temp; } //向上调整 void Adjustup(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent])//建大堆,小堆则< { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整 void Adjustdown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child])//找出两个孩子中较大的那个 { ++child; } if (a[child] > a[parent])//此为大堆,如果要实现小堆则 改 > { swap(&a[child], &a[parent]); //实现值的交换,向下继续遍历 parent = child; child = parent * 2 + 1; } else { break; } } } void HeapCreate(Heap* hp, HPDataType* a, int n) { assert(hp); assert(a); hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (!hp->_a) { perror("malloc fail"); exit(-1); } hp->_capacity = hp->_size = n; //将a中的元素全部转移到堆中 memcpy(hp->_a, a, sizeof(HPDataType) * n); //建堆 for (int i = 1; i < n; i++) { Adjustup(hp->_a, i);//按向上调整,此建立大堆 } } void HeapDestory(Heap* hp) { assert(hp); free(hp->_a); hp->_a = NULL; hp->_capacity = hp->_size = 0; } void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_capacity == hp->_size)//扩容 { int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2; HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity); if (!new) { perror("realloc fail"); exit(-1); } hp->_a = new; hp->_capacity = newcapacity; } hp->_a[hp->_size++] = x; Adjustup(hp->_a, hp->_size - 1); } //删除堆顶 void HeapPop(Heap* hp)//先将最后一个数与堆顶交换,然后再让size--,再进行向下调整 { assert(hp); swap(&hp->_a[0], &hp->_a[hp->_size - 1]); hp->_size--; Adjustdown(hp->_a, hp->_size, 0); } HPDataType HeapTop(Heap* hp)//取堆顶 { assert(hp); assert(hp->_size > 0); return hp->_a[0]; } int HeapSize(Heap* hp)//堆大小 { assert(hp); return hp->_size; } int HeapEmpty(Heap* hp)//判堆空 { assert(hp); return hp->_size == 0; }
test.c
#include"pile.h" void test() { Heap hp;//创建一个堆 int arr[] = { 1,6,2,3,4,7,5 }; HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0])); //HeapPush(&hp, 10); printf("%d\n", HeapSize(&hp)); while (!HeapEmpty(&hp)) { printf("%d %d \n", HeapTop(&hp), HeapSize(&hp)); HeapPop(&hp); } printf("%d\n", HeapSize(&hp)); HeapDestory(&hp); HeapSort(arr, sizeof(arr) / sizeof(arr[0])); printf("\n"); } int main() { test(); return 0; }