Makefile
用来组织和管理代码工程的编译和链接，通过make工具解释和执行。
1. 文件要求
Makefile
makefile
编译：make
2. Makefile核心规则
目标文件:依赖文件
编译规则
3. Makefile的语法
1. 自定义变量
字符串的方式
自定义变量的名称=值
= := 给变量直接赋值
+= 在原变量基础上增加新值
?= 变量如果没有被赋值，则赋新值，如果之前有被赋值，则保留原值
引用变量
$(变量名) 使用该变量中的值
2. 系统变量
$@ : 目标文件
$^ : 所有的依赖文件
$<: 第一个依赖文件
4. 时间戳
gcc编译的4步骤：
1. 预处理：处理#相关的命令 gcc -E main.c -o main.i
2. 编译：将源文件编译成汇编程序 gcc -S main.i -o mian.s
3. 汇编：将汇编指令转换成二进制指令 gcc -c main.s -o main.o
4. 链接：完成函数，库等的链接操作 gcc main.o xxx.o -o a.out
根据文件修改的时间戳，只编译最后发生修改的源文件，最后完成所有文件的链接。
二叉树
树：一对多的结构
由一个根节点和若干个分支节点构成的具有一对多关系的数据的集合
根节点：最顶层的节点
分支节点：有子节点的节点
叶子节点（终端节点）：没有子节点的节点
树的深度：树的层数
树的广度（度）：树中节点的度最大的值极为该树的度
节点的度：节点的子节点个数
二叉树：度为2的树是一个二叉树
满二叉树：
在不增加层数的前提下，无法增加一个节点，这种二叉树是一个满二叉树
- 第K层节点数：2^(K-1)
- K层总节点数：2^K-1
完全二叉树：
- 在满二叉树的基础上，按照从上至下，从左至右的方式增加若干个连续的节点。
- 满二叉树---》一定是一棵完全二叉树
二叉树的遍历
深度优先
- 前序遍历：根，左子树，右子树
- 中序遍历：左子树，根，右子树
- 后序遍历：左子树，右子树，根
广度优先
层序遍历：从上至下，从左至右，逐层遍历 ABDEFHJIM
确定唯一的二叉树
已知一个前序遍历和中序遍历结果，可以确定一棵唯一的二叉树；
已知一个后序遍历和中序遍历结果，可以确定一棵唯一的二叉树；
- 仅知道前序，不能还原唯一二叉树；
- 仅知道后序，也不能还原唯一二叉树；
-必须结合中序遍历，才能唯一确定一棵二叉树 。
但后面他讲到“用前序序列构建树”时，其实是使用了扩展前序序列——即在每个叶子节点的空指针位置补上了特殊符号（如井号#），形成了一个带占位符的完整序列。这个序列本质上包含了结构信息，因此可以唯一还原树形结构。
这并不是“只用前序”，而是：
用“扩展前序”（含空节点标记）来表示整棵树的完整结构，从而实现重建。
所以：
-普通前序：不能唯一确定树 ✅
-扩展前序（含#）：可以唯一重建树 ✅
这是为了编程实现方便做的工程化处理，而不是推翻了“需中序”的理论前提。
tree.h
#ifndef __TREE_H__ #define __TREE_H__ typedef char TDataType_t; typedef struct trnode { TDataType_t data; struct trnode *pl; struct trnode *pr; }TNode_t; //声明 extern TNode_t *create_bin_tree(); extern void pre_order(TNode_t *proot); extern void mid_order(TNode_t *proot); extern void pos_order(TNode_t *proot); extern void get_tree_node_cnt(TNode_t *proot,int *pclen); extern int get_tree_node_cnt2(TNode_t *proot); extern void destroy_bin_tree(TNode_t *proot); extern int get_tree_layer_cnt(TNode_t *proot); extern void layer_order(TNode_t *proot); #endiftree.c
ABE##F#I##DHM###J##
1. 创建二叉树
TDataType_t tree[]={"ABE##F#I##DHM###J##"}; int idx=0; //前序 建立二叉树，递归 TNode_t *create_bin_tree() { TDataType_t data = tree[idx++]; if('#'==data) { return NULL; } TNode_t *pnode=malloc(sizeof(TNode_t)); if(NULL==pnode) { printf("malloc error\n"); return NULL; } pnode->data=data; pnode->pl=create_bin_tree(); pnode->pr=create_bin_tree(); return pnode; }
2. 前序遍历
//前序 遍历输出，递归 void pre_order(TNode_t *proot) { if(NULL==proot) { return; } printf("%c",proot->data); pre_order(proot->pl); pre_order(proot->pr); }
3. 中序遍历
//中序 遍历输出，递归 void mid_order(TNode_t *proot) { if(NULL==proot) { return; } mid_order(proot->pl); printf("%c",proot->data); mid_order(proot->pr); }
4. 后序遍历
//后序 遍历输出，递归 void pos_order(TNode_t *proot) { if(NULL==proot) { return; } pos_order(proot->pl); pos_order(proot->pr); printf("%c",proot->data); }
5. 获取二叉树的深度
//获取二叉树层数 int get_tree_layer_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } int cntl = get_tree_layer_cnt(proot->pl); int cntr = get_tree_layer_cnt(proot->pr); return cntl > cntr ? cntl + 1 : cntr + 1; }
6. 获取二叉树的节点个数
//获取节点个数 void get_tree_node_cnt(TNode_t *proot,int *pclen) { if(NULL==proot) { return ; } (*pclen)++; get_tree_node_cnt(proot->pl, pclen); get_tree_node_cnt(proot->pr, pclen); } // 功能：统计二叉树的总节点数 int get_tree_node_cnt2(TNode_t *proot) { // 递归出口：空树节点数为 0 if (proot == NULL) { return 0; } // 总节点数 = 根节点(1) + 左子树节点数 + 右子树节点数 return 1 + get_tree_node_cnt2(proot->pl)+get_tree_node_cnt2(proot->pr); }
7. 销毁二叉树
//销毁 void destroy_bin_tree(TNode_t *proot) { if (NULL == proot) { return ; } //这里不能用前序，中序遍历的思想， //因为开头释放根节点，后面访问的就是已经释放的内存了 destroy_bin_tree(proot->pl); destroy_bin_tree(proot->pr); free(proot); }
8. 层序遍历
- 1.创建队列
- 2. 将根节点入队
- 3. 出队节点
- 4. 打印出队节点的值
- 5. 入队左右子节点
- 6. 当队列为空，循环结束
- 7.销毁队列
//层序遍历 void layer_order(TNode_t *proot) { Queue_t *pque=NULL; DataType_t outdata; pque=create_link_queue();//创建队列 if(NULL==pque) { return; } enter_queue(pque, proot);//入队 while(!is_empty_queue(pque)) { delete_queue(pque, &outdata);//出队 printf("%c",outdata->data); if(outdata->pl!=NULL) { enter_queue(pque, outdata->pl);//入队 } if(outdata->pr!=NULL) { enter_queue(pque, outdata->pr);//入队 } } printf("\n"); destory_queue(pque); return; }main.c
#include "tree.h" #include <stdio.h> int main(int argc, char **argv) { TNode_t *proot=create_bin_tree(); if(proot==NULL) { return -1; } pre_order(proot); printf("\n"); mid_order(proot); printf("\n"); pos_order(proot); printf("\n"); int clen=0; get_tree_node_cnt(proot, &clen); printf("clen is %d\n",clen); clen=get_tree_node_cnt2(proot); printf("clen2 is %d\n",clen); printf("layer_cnt is %d\n",get_tree_layer_cnt(proot)); layer_order(proot); destroy_bin_tree(proot); return 0; }Makefile
OBJ=a.out
SRC=main.c tree.c linkqueue.c
CC=gcc$(OBJ):$(SRC)
$(CC) $^ -o $@clean:
rm $(OBJ)
