Makefile和树

Makefile

Makefile是用于管理项目构建过程的工具，它通过定义规则和指令，自动化编译、链接等步骤，大大简化了开发者的工作

基本概念

Makefile 主要包括以下三部分内容：

• 目标 ：最终生成的可执行程序或中间文件
• 依赖 ：生成目标所需要的源码文件
• 命令：实现编译的具体操作语句

基本语法

1. 自定义变量

以字符串的方式定义： 自定义变量的名称=值

• = 和:= 给变量直接赋值
• += 在原变量基础上增加新值
• ?= 变量如果没有被赋值，则赋新值，如果之前有被赋值，则保留原值

引用变量

$(变量名) ：相当于使用该变量中的值

2. 系统变量

• $@ : 目标文件
• $^ : 所有的依赖文件
• $<: 第一个依赖文件

3.时间戳

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

根据文件修改的时间戳，只编译最后发生修改的源文件，最后完成所有文件的链接。

OBJ=a.out SRC=main.c tree.c CC=gcc $(OBJ) : $(SRC) $(CC) $^ -o $@ clean: rm $(OBJ)

树

1.概念

一对多的结构，由一个根节点和若干个分支节点构成的具有一对多关系的数据的集合。

• 根节点：最顶层的节点
• 分支节点：有子节点的节点
• 叶子节点（终端节点）：没有子节点的节点
• 树的深度：树的层数
• 树的广度（度）：树中节点的度最大的值极为该树的度
• 节点的度：节点的子节点个数

2.二叉树

度为2的树是二叉树

3.满二叉树

在不增加层数的前提下，无法增加一个节点，这种二叉树是一个满二叉树

满二叉树：

• 第K层节点数：2^(K-1)
• K层总节点数：2^K-1

4.完全二叉树

在满二叉树的基础上，按照从上至下，从左至右的方式增加若干个连续的节点。满二叉树一定是一棵完全二叉树。

5.二叉树的遍历

（1）深度优先

前序遍历：根，左子树，右子树
中序遍历：左子树，根，右子树
后序遍历：左子树，右子树，根

（2）广度优先

层序遍历：从上至下，从左至右，逐层遍历

（3）倒推

• 已知一个前序遍历和中序遍历结果，可以确定一棵唯一的二叉树
• 已知一个后序遍历和中序遍历结果，可以确定一棵唯一的二叉树

6.代码实现

1.结构体定义

#ifndef __TREE_H__ #define __TREE_H__ typedef char DataType_t; typedef struct trnode { DataType_t data; struct trnode *pl; struct trnode *pr; }TNode_t;

2.创建二叉树

遍历预定义的字符串，#代表NULL。通过递归构建二叉树

DataType_t tree[] = {"ABE##F#I##DHM###J##"}; int idx = 0; TNode_t *create_bin_tree() { DataType_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; }

3.前序遍历二叉树

根->左节点->右结点

void pre_order(TNode_t *proot) { if (NULL == proot) { return ; } printf("%c", proot->data); pre_order(proot->pl); pre_order(proot->pr); }

4.中序遍历二叉树

左节点->根->右结点

void mid_order(TNode_t *proot) { if (NULL == proot) { return ; } mid_order(proot->pl); printf("%c", proot->data); mid_order(proot->pr); }

5.后序遍历二叉树

左节点->右结点->根

void pos_order(TNode_t *proot) { if (NULL == proot) { return ; } pos_order(proot->pl); pos_order(proot->pr); printf("%c", proot->data); }

6.获取二叉树节点总个数

空节点返回0，非空返回1，依次累加

int get_tree_node_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } return 1+get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr); }

7.获取二叉树层数

空节点返回 0，非空节点分别计算左、右子树的深度，取两者最大值并加一,最后判断谁是深度

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; }

8.销毁

void destroy_bin_tree(TNode_t *proot) { if (NULL == proot) { return ; } destroy_bin_tree(proot->pl); destroy_bin_tree(proot->pr); free(proot); }