冒泡排序
思想：两数比较 将最大 或 最小 的元素，放到最后。
int i, j, temp; // 定义 外层循环变量 i，
// i 外层循环变量，j 内层循环变量 ，temp 临时变量
for( i=0 ; i<len-1 ; i++ ){ // 外层 控制 元素 比较多少躺
for( j=0 ; j<len-i-1 ; j++ ){ //内层 控制 元素 比较次数
if( arr[j] > arr[j+1] ){ //从小到大
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
顺序表 下的 冒泡排序
typedef int keyType; //关键字
typedef struct{
KeyType key;
}RecType; //单个节点 的 数据类型
typedef struct{
Rectype r[10000];
int len; //顺序表长度
}Sqlist; //顺序表 的 数据类型
int i, j, temp;
Sqlist *q;
for(i=0 ; i< q->len-1 ; i++){
for(j=0 ; j< q->len-i-1 ;j++){
if( q->r[j].key >q->r[j+1].key ){
temp = q->r[j].key;
q->r[j].key = q->r[j+1].key;
q->r[j+1].key = temp;
}
}
}
注意：冒泡排序 稳定，最多执行 n(n-1)/2 次。
简单选择排序
思想：找 最大 或 最小 的元素，往前放，分成 "已排序" 和 "待排序" 序列。
void selectSort(int arr[], int len){
int i, j ,temp, min;
for(i=0 ; i< len ; i++){
min = i; //min 标记 未排序第一个元素的位置
for(j=i+1; j< len ; j++){ //找 比 min位置 还小的元素
if(arr[j] < arr[min]){
min=j;
}
}
if(min != i){
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
选择排序 不稳定，平均比较次数 n(n-1)/2 次。
直接插入排序
思想：由后向前 查找 确定的位置，并插入元素。
void insertSort(int arr, int len){
int i, j, temp;
for( i=1; i < len ; i++ ){ // 从1开始，0位置当作有序序列
temp = arr[i]; // temp记录未排序的第一个元素
for(j=i-1; j>=0 && arr[j]>temp ;j--){
arr[j+1] = arr[j]; // 元素后移，为 待插入元素 腾空位置
arr[j+1] = temp; // 插入 比较的后一位
}
}
直接插入排序，是在有序基础上，速度最快且最稳定的排序方法，最多执行 n(n-1)/2 次。
希尔排序
希尔排序：又称为 "缩小增量排序"。
思想：按照 步长 进行分组，然后每一组的 第 几个 元素 进行排序。
增量 及 步长。
// dk 是 增量步长
void shellInsert(int arr[], int len, int dk){
int i, j, temp; // i 循环变量，j 前面组的位置，temp 临时变量
for( i=dk; i<len; i++ ){
//判断每组的 第几个元素大小
if( arr[i] < arr[i-dk] ){ //后面组 小于 前面组
temp = arr[i];
j = i-dk;
for( ; j>=0 && arr[j]>temp ; j-=dk ){
//前面的值 给到 后面
arr[j+dk] = arr[j];
}
arr[j+dk] = tmep;
}
}
}
希尔排序 是 不稳定的。
快速排序
基准值，i 从前向后找，比基准值大的元素，j 从后向前找，找比基准值小的元素。
最后 结束的条件是 i = j ，此时 将 基准值 放到这个位置。
int getPivot(int arr[], int low, int high){
int pivot = arr[low];
while( low < high ){ // i < j 的时候
// j 从后向前找，比基准值小的元素
while( low < high && arr[high] >= pivot ){
high--;
}
// 找到了 比基准值小的元素，将 元素 给到 i 位置
arr[low] = arr[high];
// i 从前向后找，找比 基准值 大 的元素
while( low < high && arr[low] <= pivot ){
low++;
}
arr[high] = arr[low];
}
// 找到了 比基准值大的元素，将 元素 给到 j 位置
arr[low] = pivot;
//返回基准值位置
return low;
}
void quickSort(int arr[], int low, int high){
if(low < high){
//基准值位置的变量
int pivot = getPivot(arr, low, high);
//递归 对 基准值位置 左边 进行快速排序
quickSort(arr, low, pivot-1);
//递归 对 基准值位置 右边 进行快速排序
quickSort(arr, pivot+1, high);
}
}
int main(){
int arr[]={4,2,7,5,9};
}
顺序查找
遍历数组，拿元素一次比较，相同 返回 下标，找不到 则 返回 -1。
// arr数组， len 长度， value 待查找值
int linearSearch(int arr[], int len, int vaule){
for(int i = 0; i < len; i++){
if( arr[i] == value ){
return i; //返回下标
return i+1; //返回 第几位
}
}
return -1; //找不到
}
二分查找（非递归）
// arr 数组， low 左值， high 右值， key 待查找数据
int binarySearch(int arr[], int low, int high, int key){
int mid; //中间值的下标
while( low <= high ){
mid = (low+high)/2; //找中间位置
if( key == arr[mid] ){
return mid; //返回下标
} else if( key > arr[mid] ){
low = mid + 1; //key 大于中间值，头移动至中间值后一位
} else {
high = low - 1; //key 小于中间值，尾移动至中间值前一位
}
}
//没有找到待查找数据
return -1;
}
二分查找（递归）
int binarySearch(int arr[], int low, int high, int key){
int mid; //中间值的下标
if( low <= high ){
mid = (low+high)/2;
if( key == arr[mid] ){
return mid; //递归出口
} else if( key >= arr[mid] ){
return binarySearch(arr, mid+1, high);
}else {
return binarySearch(arr, low, mid-1);
}
}
return -1;
}
线性表
1、顺序表(数组)
// 顺序表 一般 占用一片连续的存储空间
2、链表
//链表，结点 再内存中 随机分配，指针链接起来即可
| 数组 | 链表 | |
|---|---|---|
| 查询 | 快 | 慢 |
| 增删 | 慢 | 快 |
| 可以通过索引来直接访问指定位置， 增删元素需要移动大量元素。 | 只能通过指针指向下一位节点进行查询比较， 增删元素不需要移动元素。 |
遇到数组时，注意：下标 从 0 开始，还是 从 1 开始。
数组名 是 首元素地址，也是 指针。
bit 位 0100 0110
byte 字节
1 byte = 8 bit
int arr[] = {1,2,3,4,5};
int *p = arr;
// 数组 首元素地址
arr == &arr[0] == p
输入元素
void input(int arr[], int len){
//定义循环变量
int i;
int *p = arr;
for(i=0; i<len; i++){
printf("请输入第%d个元素：",i+1);
scanf("%d",&arr[i]);
// scanf("%d",arr + i);
// scanf("%d",p + i);
}
}
输出元素(遍历数组)
void output(int arr[], int len){
//定义循环变量
int i;
int *p = arr;
for(i=0; i<len; i++){
printf("%d ",arr[i]);
// printf("%d ", *(arr + i) );
// printf("%d ", *(p + i) );
}
}
查询元素
//根据 元素值 寻找 元素下标
int searchVlue(int arr[], int len, int value){
//定义循环变量
int i;
for(i=0; i<len ;i++){
if(value == arr[i]){
return i;
}
}
return -1;
}
//根据 元素位置 查找 元素值
int searchKey(int arr[], int len ,int key){
//判断 元素下标 是否 在数组范围之内
if( key<0 || key>len-1 ){
printf("元素位置错误！");
return; // exit(0); 结束程序
}
printf("查找的元素是：%d\n",arr[key]);
}
动态生成数组
int * getArray(int num){ // 返回一个指针变量
int i,*p; // p 指向 动态数组的首地址
p = (int *)malloc(sizeof(int)*num);
if(!p){
printf("空间申请失败！");
return;
}
return p;
}
修改元素
//根据 元素值 修改 元素值
void updateValue(int arr[], int len){
// 修改前，修改后
int firstValue, lastValue;
printf("请输入你要修改的元素：");
scanf("%d",&firstValue);
printf("请输入你要修改后的元素：");
scanf("%d",&lastValue);
for(int i=0; i<len; i++){
if(arr[i] == firstValue){
arr[i] = lastValue;
}
}
}
//根据 元素位置 修改 元素值
void uodateKey(int arr[], int len){
int key, value;
printf("请输入你要修改的位置：");
scanf("%d",&key);
printf("请输入你要修改后的值：");
scanf("%d",&value);
if( key<0 || key >len-1 ){
printf("位置不对！");
reutnr;
}
arr[key] = value;
}
插入元素
void insert(int arr[], int *len, int index, int value){
int i;
if(index < 0 || index > *len - 1){
return;
}
//元素后移
for(i=len-1; i>=index; i++){
arr[i+1] = arr[i];
}
//插入元素
arr[index] = value;
//元素插入 长度增加
(*len)++;
}
删除元素
void delete(int arr[],int *len,int index){
int i;
if(index < 0 || index > *len - 1){
return;
}
//元素前移
for(i=index; i<len-1; i++){
arr[i] = arr[i+1];
}
//元素删除 长度减少
(*len)--;
}
字符数组
// 1、大括号初始化字符数组时，需要预留一个空间 做 结束标志 \0，否则会乱码
char arr[5] = {'h','e','l','l','o'}; //乱码
// 2、使用双引初始化时，自带结束标志
char str[] = "hello";
strlen 求字符串长度时，不带 \0
sizeof 求字符串长度时，带 \0
字符数组 两种 键盘录入方式
1、gets( 字符串 );
2、scanf("%f", 字符串 );
// 可以校验 是否越界，stdio 是标准输入流(键盘输入)
fgets(a, sizeof(a), stfio);
结点
typedef struct Node{
int data; //数据域
struct Node *next; //指针域(存放下一个结点的位置)
}Node;
结点类型
1、头结点 // 只有指针域，数据与不存放数据，一般用 head 表示
2、首元结点 // 第一个存放 数据的 结点
有头结点：方便使用 头插法 插入元素。
typedef struct Node{
int data; //数据域
struct Node *next; //指针域
}Node,*LinkeList;
// Node struct Node 的别名 LinkList struct Node *
LinkList create(){
//动态申请空间(head 指针指向这个空间)
LinkList head = (Node *)malloc(sizeof(Node));
//判断空间是否开辟成功
if(!head){
printf("空间申请失败！\n");
return NULL;
}
//头节点，指针域值为 NULL
head->next = NULL;
//返回头结点 指针
return head;
}
链表长度获取
// 实际传的是 头结点的地址，但是代表的是 一个链表
int getSize(LinkList head){
//头结点 为空
if(!head){
return 0;
}
// p 指向首元结点
Node *p = head->next; // 等价于 LinkList q = head->next;
//计数器
int count = 0;
while(p){
count++;
p = p->next; //指针后移
}
//返回链表长度
return count;
}
链表的遍历（数据域）
void foreach(LinkList head){
if(!head){
return;
}
LinkList p = head->next;
while(p){
printf("%d ",p->data);
p = p->next;
}
}
链表的清空
void clear(LinkList head){
if(!head){
return;
}
Node *p = head->next;
while(p){
// q 存放的是，p 下一个结点的地址
LinkList q = p->next;
// 释放 p
free(p);
p = q;
}
head->next = NULL;
}
链表的销毁
void destory(LinkList head){
if(!head){
return;
}
clear(head);
free(head); // 释放头结点
head = NULL; // 指针变量 设置为 空
}
链表的插入（尾插法）
void insert(LinkList head){
if(!head){
return;
}
int num;
printf("请输入要插入的结点数量：");
scanf("%d",&num);
Node *q = head;
for(int i=0; i<num; i++){
LinkList p = (Node *)malloc(sizeof(Node));
printf("请输入数据域的值：");
scanf("%d",&p->data);
q->next = p;
q = q->next;
}
q->next = NULL;
}
尾插法 生成 链表。
链表的插入（头插法）
void insert(LinkList head){
if(!head){
return;
}
int num;
printf("请输入要插入的结点数量：");
scanf("%d",&num);
for(int i=0; i<num; i++){
Node *p = (Node *)malloc(sizeof(Node));
printf("请输入数据域的值：");
scanf("%d",&p->data);
p->next = NULL;
// 头插法
p->next = head->next;
head->next = p;
}
}
头插法，经常用 头指针 及逆行元素的插入。
链表的删除
// 根据 元素值 去删除 这个结点
void delete(LinkList head, int value){
if(!head){
return;
}
Node *p = head; // p 指针 指向 头结点的下一个
Node *q;
while( p->next ){
if( p->next->data == value ){ // 若满足条件，则 p 就是待删除元素结点的直接前驱
q = p->next; // 令 q 指向 待删除结点
p->next = q->next; // 直接前驱结点 指向 待删除结点的 后一位结点
free(q); // 此时 释放结点
} else{
p = p->next;
}
}
}
删除一个结点，必须知道这个结点的 直接前驱。
栈的特点：先进后出 / 后进先出
1、栈 分成了 "栈顶" 与 "栈底" （在栈顶进行元素的插入和删除）
2、入栈(push) 出栈(pop)
栈的顺序存储（使用 数组）
数组的首地址 做 "栈顶" 还是 "栈底" 比较好？
答：做 "栈底" 比较好。
因为 栈顶 要进行元素的插入和删除操作，所以数组尾部更适合比较频繁的插入和删除。
栈 的 结构体
typedef struct Stack{
int data[MXA]; //数据域 (MAX 为 宏定义值)
int size; //栈的大小 (指 栈中的元素个数)
}Stack, * SeqStack;
栈 的 初始化
SeqStack create(){
//创建栈，相当于 动态开辟一个数组出来
SeqStack p = (Stack *)malloc(sizeof(Stack));
if(!p){
printf("空间开辟失败！");
return;
}
//初始化 栈 的大小
p->size = 0;
//初始化 栈中的元素
for(int i=0; i<MAX ;i++){
p->data[i] = 0;
}
return p;
}
入栈
void push(SeqStack stack, int data){
if(!stack){
return;
}
//入栈 需要判断 栈是否已满
if( stack->size == MAX ){
printf("栈已满！\n");
return;
}
// stack->size 栈的大小 就是 待插入元素 的下一个位置
stack->data[stack->size] = data;
//改变栈的大小
stack->size++;
}
入栈 需要注意 栈是否 不存在 and 已满。
出栈
void pop(SeqStack stack){
if(!stack)
return;
if(stack->size == 0){
printf("栈已空\n");
return;
}
//删除一个元素
stack->data[stack->size -1] = 0;
//改变栈的大小
stack->size --;
}
出栈 需要注意 栈是否 不存在 and 已空。
遍历 栈中元素
void forerachStack(SeqStack stack){
if(!stack) return;
for(int i=0;i<stack->size; i++)
printf("%d ",stack->data[i]);
}
栈 的 链式存储（链表）
链表的头结点端 做 “栈顶” 还是 “栈底” 比较好？
答：做 “栈顶” 比较好。
因为 链表的头结点端 可以更方便的进行元素的 插入(头插法) and 删除(头结点做直接前驱)。
栈链式存储 结构体
//结点结构体
trpedef struct Node{
int data;
struct Node *next;
}Node;
//栈的结构体
trpedef struct Stack{
struct Node header; //头结点
int size; //栈的大小 即元素个数
}Stack, *LinkStack;
初始化栈
LinkStack inir_LinkStack(){
// myStack 是指针，指向所申请的空间
LinkStack myStack = (Stack *)malloc(sizeof(Stack));
if(!Stack)
return NULL;
//初始化 长度为0
myStack->size = 0;
//相当于 初始化 链表的头结点 指针域
myStack->header.next = NULL;
}
什么时候使用 " -> " ,什么时候使用 " . " ？
-> 在指针的时候
. 在变量名的时候
注意事项
struct Node *list; list->next list->next
struct Node a; a.data a.next
入栈
void push(LinkStack stack, int data){
if(!stack)
return;
//创建一个结点
Node *p = (Node *)malloc(sizeof(Node));
//给 结点数据域 赋值
p->data = data;
//头插法 先连后面
p->next= stack->header.next;
stack->header.next = p;
//改变 栈中元素 的个数
stack->size ++;
}
出栈
void pop(LinkStack stack){
//判断栈是否存在
if(!stack)
return;
//判断栈空
if(stack->size ==0){
printf("栈中无元素！\n");
return;
}
//定义一个节点类型的指针，用作删除结点
Node *p = stack->header.next;
//头结点 连接到 删除结点 的后边
stack->header.next = p->next;
//释放结点
free(p);
//更新 栈的大小
stack->size --;
}
队列：先进先出 后进后出
1、只允许 从一端 添加元素，从 另一端 删除元素
2、队头 出元素，队尾 进元素
3、push 入队 pop 出队
队列的顺序存储
数组的首地址做 “队头” 好，还是 “队尾” 比较好？
答：都一样。
做 队头 和 队尾 差别不大，因为都需要移动大量元素。
队列的结构体
typedef struct Queue{
int data[MAX]; //顺序存储 数组模拟的队列
int size; //队列的大小(队列中元素的个数)
}Queue, *SeqQueue;
队列的初始化（数组头做队头，数组尾做队尾）
SeqQueue init(){
//申请队列空间，即数组空间
SeqQueue p = (Queue *)malloc(sizeof(Queue));
if(!p){
return NULL;
}
//初始化队列大小
p->size = 0;
for(int i=0; i<MAX ;i++){
p->data[i] = 0;
}
reutrn p;
}
入队
void push(SeqQueue p, int value){
if(!p){ //队列不存在
return;
}
if(p->size == MAX){
printf("队列元素已满！\n");
return;
}
//插入元素(进队)
p->data[p->size] = value;
//改变队列元素个数
p->size ++;
}
出队
void push(SeqQueue p){
if(!p){ //队列不存在
return;
}
if(p->size == 0){
printf("队列元素已空！\n");
return;
}
//出队 删除数组首元素
for(int i=0; i< p->size -1 ;i++){
p->data[i] = p->data[i+1];
}
//改变队列元素个数
p->size --;
}
要记得，看到循环里边有 i+1 的时候，要改变 最终值。
队列的链式存储
链表的 头结点端 做 “队头” 还是 “队尾” 比较好？
答：做 “队头” 好。
因为 头结点端 进行删除方便，尾端 插入元素方便（尾插法）。
队列的结构体
//队列的结构体
typedef struct LQueue{
struct Node header; //头结点
int size; //队列大小
struct Node* pTail; //尾结点指针
}LQueue, *LinkQueue;
循环队列
//队满
front = (rear + 1)%n; // front 头，rear 尾
//队空
front = rear; // 头指针 指向 尾指针时，队为空
零个 或者多个任意字符组成的 有限序列 是我们的字符串。
串 是 内容受限的线性表。
子串：一个串中 任意个连续字符组成的子序列（含空串）。
"*jkj12k0" //它的子串有哪些？
// 单字符 6
// 双字符 7
// 三字符 6
// 四字符 5
// 五字符 4
// 六字符 3
// 七字符 2
// 八字符 1
// 空串 1
分别是：
// *
// *j
// *jk
// *jkj
// *jkj1
// *jkj12
// *jkj12k
// *jkj12k0
// j
// jk
// jkj
// jkj1
// jkj12
// jkj12k
// jkj12k0
// k
// kj
// kj1
// kj12
// kj12k
// kj12k0
// j1
// j12
// j12k
// j12k0
// 1
// 12
// 12k
// 12k0
// 2
// 2k
// 2k0
// k0
// 0
// 空串
真子串（不包含自身的子串）。
主串：包含子串的串，称之为 主串。
字符位置：字符在数组中的位置。
子串位置：子串第一个字符串 在 主串中的位置。
空格串：一个空格或者多个空格组成的串，称之为空格串。
空串：零个没有任意字符的串，称之为空串。
" " // 空格串
"" // 空串
串相等：当两个串长度相等，并且每个位置对应字符完全一样的时候，两个串才相等。
1. 赋值 StrAssign(s,t) 将串t的值赋值给串s
2. 求串长 StrLength(s) 返回字符串s的长度
3. 串比较 StrCompare(s,t) 比较两个串，返回-1、0和1，分别代表s<t、s=t和s>t
4. 连接 Concat(s,t) 将串t连接在串s的尾部，形成新的字符串
5. 求子串 SubString(s,start,len) 返回串s从start开始、长度为len的字符序列
6. 串拷贝 StrCopy(t,s) 将串s拷贝到串t上
7. 串判空 StrEmpty(s) 判断串s是否为空串
8. 清空串 ClearString(s) 清空字符串s
9. 子串位置 Index(S,T,pos) 字符串S中返回T所出现的位置
10. 串替换 Replace(S,T) 串S替换为T
串的顺序存储
结构体
typedef struct SString{
char ch[MAX +1]; // 字符数组空间，MAX 为宏定义值
int length; // 串的长度
};
BF算法
// str 是主串 subStr 是模式匹配串
int BF(char str[], char subStr[]){
int i=0,j=0; //定义 i 主串下表，j 模式串下标
while( i<strlen(str) && j<strlen(subStr) ){
//如果对应位置相等，则下标后移，比较下一位元素
if(str[i] == subStr[j]){
i++;
j++;
} else{
i = i-j+1; //主串下标进行回溯
j = 0; //子串下标回溯
}
}
if( j == strlen(subStr) ){ //子串下标 与 子串长度相等
//返回子串位置
return i - strlen(subStr) + 1;
}
return -1; //未找到子串下标
}
把矩阵当作 二维数组，只不过下标都是从 1 开始。
二维数组 以行为主序存储，二维数组 以列为主序存储。
以行存储，先去计算前 (i-1)行有多少元素
以列存储，先去计算前 (j-1)列有多少元素
前提：数组下标从一开始。
对称矩阵：以主对角线为对称轴，个元素对应相等的矩阵。
对角矩阵：除主对角线意外，全是 0 的矩阵。
稀疏矩阵：非零元素个数，远远少于 零元素个数，且零元素分布无规律。
三元组 (行,列,值) ：
(4,5,8) //第四行，第五列，值为8 (前提：行列下标都从1开始)
(4,5,8) //第三行，第四行，值为8 (前提：行列下标都从0开始)
树的性质
1、树中的节点数 等于 所有节点的度数加1。
2、度为 M 的树中，第i层上至多有 M的(i-1) 次方个节点(i>=1)。
3、高度为 H 的 M 叉树中，之多有 (M的H次方)/(M-1) 个节点。 // 二叉树 需要 再减去1：(M的H次方)/(M-1)-1
二叉树：有0个 到 2个节点的树，称为 二叉树。
二叉树的性质
大顶堆，小顶堆
// 大顶堆 每个根节点(所有的根节点) 都大于 它的子结点
ki >= k2i
k2 >= k2i +1
// 小顶堆 每个根节点(所有的根节点) 都小于 它的子结点
ki <= k2i
k2 <= k2i +1
结点的定义
typedef struct TreeNode{
char ch; // 数据域
struct TreeNode *lchild; //左孩子 指针
struct TreeNode *rchild; //右孩子 指针
}TreeNode;
当没有 左右孩子节点 的时候，左右孩子指针 为 NULL 值。
遍历方式
先序遍历
void preOrder(Node *root){
//递归结束条件，也就是说当一个节点 某个指针域为 NULL
if(!root){
return;
}
printf("%c ",root->ch);
//递归调用左子树
preOrder(root->lchild);
//递归调用右子树
preOrder(root->rchild);
}
中序遍历
void inOrder(Node *root){
//递归结束条件，也就是说当一个节点 某个指针域为 NULL
if(!root){
return;
}
//递归调用左子树
preOrder(root->lchild);
printf("%c ",root->ch);
//递归调用右子树
preOrder(root->rchild);
}
后序遍历
void lastOrder(Node *root){
//递归结束条件，也就是说当一个节点 某个指针域为 NULL
if(!root){
return;
}
//递归调用左子树
preOrder(root->lchild);
//递归调用右子树
preOrder(root->rchild);
printf("%c ",root->ch);
}
根据遍历的序列 确定 二叉树 的形状
// 1、先序 和 中序 可以确定一棵二叉树
答：根据先序 确定 根节点的位置，然后去 中序 找到该节点，该节点左边元素都是左子树，右边元素都是右子树；依次重复上述过程，即可根据序列确定 二叉树形状。
(从前找根节点)
// 2、后序 和 中序 可以确定一棵二叉树
答：根据先序确定 根节点的位置，然很去中序中找到该节点左边元素都是左子树，右边元素都是右子树，一次重复上述过程，即可根据序列确定 二叉树形状。
(从后找根节点)
// 3、先序 和 后序 不可以确定一棵二叉树
非递归中序遍历
void inOrder(Node * root){
//指针p 指向 根节点，并按照某种顺序游走于每一个结点
Node *p = root;
//建立栈，用来实现 递归
LinkStack s = init_LinkStack(); //初始化栈，初始化一个头结点出来
//p 不指向 NULL 并且 栈不空的时候
while(p || ! isEmpty_LinkStack(s)){
//根节点不空，进栈,让其指向左子树
if(p){
push_LinkStack(s , p);
p = p->lchild; //指向左子树
}else{
//定义一个指针 指向 栈顶元素 （就是 子树的根节点）
Node *top = top_LinkStack(s);
//元素出栈
pop_LinkStack(s);
printf("%c ",top->data);
p = top->rchild;
}
}
//销毁栈
destory_LinkStack(s);
}
如果有 n 个节点，则有 n+1 个空指针域。
线索：指向其 前驱 和 后继 的指针。
孩子兄弟表示法：左边指针是孩子，右边指针是兄弟。
// 定义节点 结构体
typedef struct TreeNode{
int data; //数据域
struct TreeNode *lchild; //左指针(指向左孩子)
struct TreeNode *rchild; //右指针(指向右孩子)
}TreeNode;
TreeNode* searchTreeNode( TreeNode *root, int key ){
//递归结束条件， root 为 NULL 相当于 没有找到节点
if( (!root) || (key == root->data) ){
return root;
}
else if( key < root->data ) // 递归左子树查找
{
retuen searchTreeNode(root->lchild, key);
}
else //递归右子树查找
{
retuen searchTreeNode(root->rchile, key);
}
}
路径：两个节点之间的 线 就是 路径。
节点的路径：从 根节点 到 该节点，有几根线，路径长度就是几。
树的路径长度：所有结点的路径长度之和，称之为树的路径长度。
权值：给这个节点 赋一个数值，这个数值就是 权值。
节点的带权路径长度：路径长度 * 该节点的权值。
树的带权路径长度（WPL）：所有 叶子节点 的带权路径长度 之和。
重点：哈夫曼树构造
//哈夫曼二叉树构造
1、每次从 序列中找出 权值最小的两个节点（一般：从左至右，从小到大）
2、生成一个新的节点，将这个节点放入 序列中，删除刚才的两个最小权值节点，再重复此过程。
防止浪费空间（稀疏矩阵），但是效率 相对于 邻接矩阵 较低。
邻接表：顶点用 一维数组存储，后面跟着 单链表 存储邻接点。
邻接表 中 邻接点的个数 和 图中这个顶点 的出度有关。
G = (V,E) ：G指的图 V指的顶点 E指的边。
生成树：顶点由边连接在一起，不存回路的图。
生成树顶点个数 和 图顶点个数相同。
生成树（极小连通图） 去掉一条边，则变成非连通图。
连通图有 n 个顶点，则其 生成树 有 n-1条边。
生成树 再加一条边，必然形成回路。
含有 n 个顶点 n-1 条边的图，不一定是 生成树。
无向图的生成树
最小生成树：边权值之和最小的树。
克鲁斯卡尔 和 边 有关。
每次去找 边权值 最小的边，两个顶相连，依次构成最小生成树。