从零开始的敲代码生活--数据结构篇（二叉树）

一、二叉树基础概念树由根节点和若干个子节点构成的具有一对多关系的数据的集合称为树形结构。术语说明空树一个结点都没有根节点最顶层节点叶子节点(终端节点)没有子节点的结点称为叶子节点(节点的度为 0)分支节点有子节点的节点节点的度节点的子节点个数树的深度树的层数树的度(广度)树中节点最大的度是该树的广度二叉树树的广度为二的树形结构称为二叉树且各节点的左右子节点不能交换。满二叉树在不增加层数的前提下无法再增加一个节点。K 层满二叉树第 K 层的节点个数$2^{(K-1)}$K 层总共节点个数$2^K - 1$完全二叉树在满二叉树基础上按照从左至右从上至下的顺序增加节点该树是完全二叉树在满二叉树基础上按照从下至上从右至左的顺序删除节点该树是完全二叉树满二叉树一定是完全二叉树二叉树的遍历深度优先遍历算法前序遍历根、左子树、右子树 → ABFGCDHIE中序遍历左子树、根、右子树 → FBCGAHIDE后序遍历左子树、右子树、根 → FCGBIHEDA广度优先遍历算法层序遍历从上至下从左至右逐层遍历 → ABDFGHECI由遍历序列还原二叉树已知前序遍历和中序遍历结果可以唯一还原一棵二叉树已知后序遍历和中序遍历结果可以唯一还原一棵二叉树**文件的创建方式**二叉树采用前序遍历的方式创建字符串ABF##GC###DH#I##E##中#表示该位置为空子树(NULL)。文件说明文件说明tree.h头文件二叉树结点结构体定义 函数声明tree.c源文件二叉树创建、遍历、求结点个数、求深度、释放等功能实现cyclequeue.h头文件层序遍历辅助循环队列(存储树结点指针)cyclequeue.c源文件循环队列功能实现main.c测试 main 函数二、头文件 tree.h#ifndef _TREE_H #define _TREE_H #include stdio.h #include stdlib.h #include string.h #include cyclequeue.h typedef char Data_t; /* 二叉树结点结构体:数据域 左子树指针 右子树指针 */ typedef struct tree_node { Data_t data; // 数据域:保存的数据 struct tree_node *pl; // 指针域:左子树根结点地址 struct tree_node *pr; // 指针域:右子树根结点地址 }TNode_t; extern TNode_t *create_tree(); extern void show_pro_tree(TNode_t *ptree); extern void show_mid_tree(TNode_t *ptree); extern void show_pos_tree(TNode_t *ptree); extern int get_tree_node_cnt(TNode_t *ptree); extern int get_tree_deep(TNode_t *ptree); extern void free_tree(TNode_t *ptree); extern void lay_tree(TNode_t *ptree); extern void show_lay_tree(TNode_t *ptree); #endif三、功能实现 tree.ccreate_tree 创建二叉树功能按前序遍历顺序读取全局数组 bin_tree[] 中的数据创建二叉树读到#表示该位置为空子树返回 NULL。返回树根结点指针malloc 失败返回 NULL。Data_t bin_tree[] ABF##GC###DH#I##E##; int i 0; TNode_t *create_tree() { if(bin_tree[i] #) { i; return NULL; } TNode_t *ptree malloc(sizeof(TNode_t)); if(ptree NULL) { printf(malloc fail\n); return NULL; } ptree-data bin_tree[i]; ptree-pl create_tree(); ptree-pr create_tree(); return ptree; }pro_tree 前序遍历功能按根、左子树、右子树的顺序递归遍历打印结点。void pro_tree(TNode_t *ptree) { if(ptree NULL) { return; } printf(%c,ptree-data); pro_tree(ptree-pl); pro_tree(ptree-pr); return; }pos_tree 后序遍历功能按左子树、右子树、根的顺序递归遍历打印结点。void pos_tree(TNode_t *ptree) { if(ptree NULL) { return; } pos_tree(ptree-pl); pos_tree(ptree-pr); printf(%c,ptree-data); return; }mid_tree 中序遍历功能按左子树、根、右子树的顺序递归遍历打印结点。void mid_tree(TNode_t *ptree) { if(ptree NULL) { return; } mid_tree(ptree-pl); printf(%c,ptree-data); mid_tree(ptree-pr); return; }show_pro_tree / show_mid_tree / show_pos_tree 遍历封装功能分别调用 pro_tree、mid_tree、pos_tree 完成遍历并在结尾打印换行。void show_pro_tree(TNode_t *ptree) { pro_tree(ptree); printf(\n); } void show_mid_tree(TNode_t *ptree) { mid_tree(ptree); printf(\n); } void show_pos_tree(TNode_t *ptree) { pos_tree(ptree); printf(\n); }get_tree_node_cnt 求结点个数功能递归统计二叉树结点总个数(1 左子树个数 右子树个数)。返回结点个数空树返回 0。int get_tree_node_cnt(TNode_t *ptree) { if(ptree NULL) { return 0; } return 1 get_tree_node_cnt(ptree-pl) get_tree_node_cnt(ptree-pr); }get_tree_deep 求树的深度功能递归求二叉树深度(左子树深度与右子树深度较大者 1)。返回树的深度空树返回 0。int get_tree_deep(TNode_t *ptree) { if(ptree NULL) { return 0; } return get_tree_deep(ptree-pl) get_tree_deep(ptree-pr) ? get_tree_deep(ptree-pl)1 : get_tree_deep(ptree-pr)1; }free_tree 释放二叉树功能按后序顺序递归释放所有结点(先释放左、右子树最后释放根结点)。void free_tree(TNode_t *ptree) { if(ptree NULL) { return; } free_tree(ptree-pl); free_tree(ptree-pr); free(ptree); }lay_tree 层序遍历功能借助循环队列实现广度优先遍历。根结点先入队循环出队打印结点并将其左、右孩子依次入队直到队列为空。返回:void空树直接返回。void lay_tree(TNode_t *ptree) { if(ptree NULL) { return; } CQue_t *pcque create_cyclequeue(); if(pcque NULL) { return; } en_cycle_queue(pcque,ptree); while(!is_empty_cycle_queue(pcque)) { TNode_t *ptemp NULL; de_cycle_queue(pcque,ptemp); printf(%c,ptemp-data); if(ptemp-pl ! NULL) { en_cycle_queue(pcque,ptemp-pl); } if(ptemp-pr ! NULL) { en_cycle_queue(pcque,ptemp-pr); } } free_cycqueue(pcque); return; } void show_lay_tree(TNode_t *ptree) { lay_tree(ptree); printf(\n); }四、层序遍历辅助循环队列层序遍历需要借助循环队列存储结点指针实现从上至下、从左至右逐层访问。该循环队列与《数据结构篇(队列)》中的循环队列实现完全一致仅存储的数据类型由 int 改为树结点指针struct tree_node。头文件 cyclequeue.h#ifndef _CYCLEQUEUE_H #define _CYCLEQUEUE_H #include stdio.h #include stdlib.h #define CYCQUE 10 struct tree_node; typedef struct tree_node* CQData_t; typedef struct cycle_queue { CQData_t *pbase; int head; int tail; }CQue_t; extern CQue_t *create_cyclequeue(); extern int is_empty_cycle_queue(CQue_t *pcque); extern int is_full_cycle_queue(CQue_t *pcque); extern int en_cycle_queue(CQue_t *pcque,CQData_t data); extern int de_cycle_queue(CQue_t *pcque,CQData_t *data); extern void free_cycqueue(CQue_t *pcque); #endifcyclequeue.c 说明各函数的实现逻辑与《数据结构篇(队列)》中的循环队列完全相同create_cyclequeue分配管理结构体 数组空间head、tail 置 0is_empty_cycle_queuehead tail判空is_full_cycle_queue(tail1) % CYCQUE head判满en_cycle_queue队尾下标处写入tail (tail1) % CYCQUEde_cycle_queue读取队头下标处数据head (head1) % CYCQUEfree_cycqueue先释放数组空间再释放管理结构体唯一区别typedef struct tree_node* CQData_t;使队列元素为树结点指针用于存放层序遍历过程中等待访问的结点。五、测试 main 函数 main.c#include tree.h int main(void) { TNode_t *ptree create_tree(); if(ptree NULL) { return -1; } show_pro_tree(ptree); show_mid_tree(ptree); show_pos_tree(ptree); show_lay_tree(ptree); int tree_node_cnt 0; printf(tree_node_cnt %d\n,get_tree_node_cnt(ptree)); printf(tree_deep %d\n,get_tree_deep(ptree)); free_tree(ptree); return 0; }六、编译运行 内存检测编译gcc main.c tree.c cyclequeue.c -o tree_demo运行程序./tree_demovalgrind 检测内存泄漏写二叉树务必检测内存泄漏保证每一块 malloc 都有对应的 freevalgrind --leak-checkfull ./tree_demo运行输出结果ABFGCDHIE FBCGAHIDE FCGBIHEDA ABDFGHECI tree_node_cnt 9 tree_deep 4