数据结构（6） Makefile,二叉树

Makefile用来组织和管理代码工程的编译和链接通过make工具解释和执行。1. 文件要求Makefilemakefile编译make2. Makefile核心规则目标文件:依赖文件编译规则3. Makefile的语法1. 自定义变量字符串的方式自定义变量的名称值 : 给变量直接赋值 在原变量基础上增加新值? 变量如果没有被赋值则赋新值如果之前有被赋值则保留原值引用变量$(变量名) 使用该变量中的值2. 系统变量$ : 目标文件$^ : 所有的依赖文件$: 第一个依赖文件4. 时间戳gcc编译的4步骤1. 预处理处理#相关的命令 gcc -E main.c -o main.i2. 编译将源文件编译成汇编程序 gcc -S main.i -o mian.s3. 汇编将汇编指令转换成二进制指令 gcc -c main.s -o main.o4. 链接完成函数库等的链接操作 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.cABE##F#I##DHM###J##1. 创建二叉树TDataType_t tree[]{ABE##F#I##DHM###J##}; int idx0; //前序 建立二叉树递归 TNode_t *create_bin_tree() { TDataType_t data tree[idx]; if(#data) { return NULL; } TNode_t *pnodemalloc(sizeof(TNode_t)); if(NULLpnode) { printf(malloc error\n); return NULL; } pnode-datadata; pnode-plcreate_bin_tree(); pnode-prcreate_bin_tree(); return pnode; }2. 前序遍历//前序 遍历输出递归 void pre_order(TNode_t *proot) { if(NULLproot) { return; } printf(%c,proot-data); pre_order(proot-pl); pre_order(proot-pr); }3. 中序遍历//中序 遍历输出递归 void mid_order(TNode_t *proot) { if(NULLproot) { return; } mid_order(proot-pl); printf(%c,proot-data); mid_order(proot-pr); }4. 后序遍历//后序 遍历输出递归 void pos_order(TNode_t *proot) { if(NULLproot) { 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(NULLproot) { 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 *pqueNULL; DataType_t outdata; pquecreate_link_queue();//创建队列 if(NULLpque) { 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 *prootcreate_bin_tree(); if(prootNULL) { return -1; } pre_order(proot); printf(\n); mid_order(proot); printf(\n); pos_order(proot); printf(\n); int clen0; get_tree_node_cnt(proot, clen); printf(clen is %d\n,clen); clenget_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; }MakefileOBJa.outSRCmain.c tree.c linkqueue.cCCgcc$(OBJ):$(SRC)$(CC) $^ -o $clean:rm $(OBJ)