树的概念

树是一种非线性的数据结构，它是一个n个节点组成的具有层次关系的集合，一棵树由一个根节点和若干个其余节点构成，除了根节点外，其他的节点都由一个前驱和多个后继，而根节点可以有多个后继，但没有前驱，树由递归定义，并且子树不能有交集，否则就不是树。

相关知识

节点的度：一个节点含有子树的个数叫做节点的度，如上图的B节点度为2
叶子节点：节点度为0的节点叫做叶子节点，如上图的G
分支节点：度不为0的节点，如上图的B
双亲节点：若一个节点拥有子节点，那这个节点就称为他子节点的双亲节点，如上图的B为D，E的双亲节点
孩子节点：一个节点含有多个子节点，那么这些子节点就是孩子节点，如上图的DE就是B的孩子节点
兄弟节点：有相同双亲节点的节点，如上图的D和E
树的度：一棵树里最大节点的度称为树的度，上图树的度为2
节点的层次：从根开始，根为第一层，以此类推，上图G在第4层
树的高度：最深的那个节点的层数，上图树的高度为4
堂兄弟节点：双亲节点在同一层称为堂兄弟节点，上图D和F，E和F为堂兄弟节点
节点的祖先：树的根，上图A为节点的祖先
子孙：除了根节点外的其余节点都是根节点的子孙
森林：由数量大于大于1的树构成的为森林

树的表示法

1.双亲表示法
用顺序表进行保存，顺序表每个位置存储的是节点的名称和双亲节点的位置，根节点没有双亲节点，其双亲的节点下标为-1.

2.左孩子右兄弟表示法
不管一个节点有多少个孩子，这个节点的指针都只指向在第一个孩子，兄弟指针指向右边的兄弟节点
如下图

二叉树概念及其表示法

概念

二叉树由一个根节点和两根分别称为左子树和右子树的二叉树构成或者没有节点构成，二叉树不存在度数大于2的节点，且二叉树的子树有左右之分，顺序不能颠倒，所以二叉树是一个有序树。
满二叉树：一个二叉树每一层的节点数都达到最大值，也就是说一个k层的满二叉树的节点数为2^k-1
完全二叉树：满二叉树是一种特殊的完全二叉树，完全二叉树的度不能为1，若一个完全二叉树有k层，前k-1层是满二叉树，最后一层可以不满，但从左到右必须是连续的，节点数最少有2 ^ (k-1），最多有2 ^ n - 1个

二叉树的存储结构

顺序存储

顺序存储就是用数组来存储，一般数组适合完全二叉树，因为不是完全二叉树就会导致空间的浪费，而二叉树的顺序存储在物理结构上是一个数组，在逻辑结构上是一棵树。
完全二叉树

不完全二叉树会有一些空的格子

链式存储

用链表来表示一棵二叉树，包括数据和左右指针，链式结构分为二叉链（两个孩子）或者三叉链（两个孩子和一个父指针），二叉树用的是二叉链，红黑树的学习要用到三叉链。

注

顺序存储中父亲和孩子的下标存在一个关系，设a为父亲的下标，b为左孩子的下标，c为右孩子的下标，则b=2a+1，c=2a+2，同理知道孩子的下标可以找父亲的节点，不管是左孩子还是右孩子，父亲的节点都可以由parent=（child-1）/2， 因为有一个取整的问题。

堆

堆是一棵完全二叉树，分为大根堆（任何一个父亲都大于等于孩子）和小根堆（任何一个父亲都小于等于孩子），主要应用于堆排序，topk问题和优先级队列

结构

typedef int valuetype;
typedef struct heap
{valuetype* arr;int size;int capacity;
}heap;

初始化

void init(heap* hp)
{assert(hp);hp->arr = (valuetype*)malloc(sizeof(valuetype) * 4);hp->size = 0;hp->capacity = 4;
}

插入

void push(heap* hp, valuetype x)
{assert(hp);//检查空间是否足够if (hp->size == hp->capacity){hp->capacity *= 2;valuetype* tmp = (valuetype*)realloc(hp->arr,sizeof(valuetype) * hp->capacity);if (tmp == NULL){perror("realloc fail");return;}hp->arr = tmp;}//插入数据hp->arr[hp->size] = x;hp->size++;//向上调整算法，这里是大堆//for (int i = hp->size-1; i > 0; i = (i - 1) / 2)//{//	int j = (i - 1) / 2;//	if (hp->arr[i] > hp->arr[j])//若是小堆把这一行的大于号改成小于号//	{//		valuetype tmp = hp->arr[i];//		hp->arr[i] = hp->arr[j];//		hp->arr[j] = tmp;//	}//	else//	{//		break;//	}//}AdjustUp(hp->arr, 0, hp->size-1);//也可以写一个向上调整算法直接调用
}

销毁

void destroy(heap* hp)
{assert(hp);free(hp->arr);hp->arr = NULL;hp->capacity = hp->size = 0;
}

删除

void pop(heap* hp)//删除堆顶的数据
{//首尾数据交换assert(hp);assert(hp->size);valuetype tmp = hp->arr[hp->size - 1];hp->arr[hp->size - 1] = hp->arr[0];hp->arr[0] = tmp;//删除最后一个数据hp->size--;//向下调整AdjustDown(hp->arr, 0, hp->size);//这种方法能最大的提高效率，因为不需要重新建堆
}

向上调整算法

void AdjustUp(valuetype* arr, int begin, int end)
{for (int i = end; i > begin; i = (i - 1) / 2){int j = (i - 1) / 2;if (arr[i] > arr[j])//这里是大堆，若是小堆把这一行的大于号改成小于号{valuetype tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}else{break;}}
}

向下调整算法

void AdjustDown(valuetype* arr, int begin, int end)
{int parent = begin;int child = 2 * parent + 1;while (child < end){if (child + 1 < end && arr[child] < arr[child + 1])//这里是大堆{child += 1;}if (arr[child] >= arr[parent]){valuetype tmp = arr[child];arr[child] = arr[parent];arr[parent] = tmp;}else{break;}parent = child;child = 2 * parent + 1;}
}

堆顶元素

valuetype top(heap* hp)
{assert(hp);assert(hp->size);return hp->arr[0];
}

topk问题

eg.有一万个数，想找出最大的前十个，但排序太浪费资源了，我们可以用这个数组中前10个数建堆，然后再用剩余10000-10个元素与堆顶元素交换，不满足条件就替换
我们可以建大堆，然后pop k次获得所需元素，但topk问题有一个特殊情况，当N太大 的时候不能使用这个思路，因为要开的空间太大了，比如说N为十亿，换算出来的数组需要4g的空间，这种就不能存在内存上，所以我们需要一个新思路：前k个数建小堆，然后N-k个数依次与建成的小堆比较，如果比堆顶的数据大，就替换它进堆，

void topk(int* a, int k,int sz)
{//先用前k个数据建堆heap hp;init(&hp);for (int i = 0; i < k; i++){push(&hp, a[i]);}for (int i = k; i < sz; i++){if (hp.arr[0] < a[i]){hp.arr[0] = a[i];AdjustDown(hp.arr, 0, hp.size-1);}}//所获得的堆里就是最大的前十个数
}//上面的向下调整算法应该变号

堆排

法1：有空间复杂度的消耗

void heapsort(int* arr,int n)
{//建堆heap hp;init(&hp);for(int i=0;i<n;i++){push(&hp,arr[i]);}for(int i=0;i<n;i++){int tmp=top(&hp);pop(&hp);arr[i]=tmp;}destroy(&hp);
}

法2：对数组建堆，向上调整建堆或者向下调整建堆

void heapsort(int* arr, int n)//向上调整
{//向上调整建堆//for (int i = 0; i < n; i++)//{//	AdjustUp(arr, 0, i);//}//向下调整建堆for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(arr,i,n-1);//时间复杂度优于向上调整建堆，可以通过差比数列算时间复杂度}//升序建大堆//交换第一个数据和最后一个数据，向下调整建堆for (int i = n-1; i > 0; i--){//swap(arr[0], arr[i - 1]);int tmp = arr[0];arr[0] = arr[i];arr[i] = tmp;AdjustDown(arr, 0, i);}
}

链式二叉树

遍历

1.前序：根 左子树 右子树的顺序遍历
2.中序：左子树 根 右子树的顺序遍历
3.后序：左子树 右子树 根的顺序遍历
4.层序：一层一层遍历

上图的前序遍历是：1 2 3 N N N 4 5 N N 6 N N
中序是：N 3 N 2 N 1 N 5 N 4 N 6 N
后序是: N N 3 N 2 N N 5 N N 6 4 1
N表示空树

链式二叉树的结构

typedef int valuetype;
typedef struct BinaryNode
{valuetype data;struct BinaryNode* left;struct BinaryNode* right;
}BTNode;

申请新节点

BTNode* BuyNode(valuetype x)
{BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));if(newnode==NULL){perror("malloc fail");return;}newnode->left=NULL;newnode->right=NULL;newnode->data=x;return newnode;
}

前序遍历

void PrevOrder(BTNode* root)
{if(root==NULL){printf("N");return;}printf("%d",root->data);PrevOrder(root->left);PrevOrder(root->right);
}

中序遍历

void InOrder(BTNode* root)
{if(root==NULL){printf("N");return;}PrevOrder(root->left);printf("%d",root->data);PrevOrder(root->right);
}

后序遍历

void AfterOrder(BTNode* root)
{if(root==NULL){printf("N");return;}PrevOrder(root->left);PrevOrder(root->right);printf("%d",root->data);
}

层序遍历

用队列实现

void levelorder(BTNode* root)
{queue obj;init(&obj);//初始化队列if(root){push(&obj,root);}while(!isempty(&obj)){BTNode* tmp=pop(&obj);//这里的pop会返回队头数据printf("%d",tmp->data);if(tmp->left){push(&obj,tmp->left);}if(tmp->right){push(&obj,tmp->right);}}
}

销毁

void destroy(BTNode* root)
{if(root==NULL){return;}destroy(root->left);destroy(root->right);free(root);//后序
}