企业官网建设流程全解析

一、二叉树基础概念

树：由根节点和若干个子节点构成的具有一对多关系的数据的集合，称为树形结构。

术语说明：

• 空树：一个结点都没有
• 根节点：最顶层节点
• 叶子节点(终端节点)：没有子节点的结点称为叶子节点(节点的度为 0)
• 分支节点：有子节点的节点
• 节点的度：节点的子节点个数
• 树的深度：树的层数
• 树的度(广度)：树中节点最大的度是该树的广度

二叉树：树的广度为二的树形结构称为二叉树，且各节点的左右子节点不能交换。

满二叉树：在不增加层数的前提下，无法再增加一个节点。

• K 层满二叉树：第 K 层的节点个数：$2^{(K-1)}$
• K 层总共节点个数：$2^K - 1$

完全二叉树：

1. 在满二叉树基础上，按照从左至右，从上至下的顺序增加节点，该树是完全二叉树
2. 在满二叉树基础上，按照从下至上，从右至左的顺序删除节点，该树是完全二叉树

   满二叉树一定是完全二叉树

二叉树的遍历

• 深度优先遍历算法
  • 前序遍历：根、左子树、右子树 → ABFGCDHIE
  • 中序遍历：左子树、根、右子树 → FBCGAHIDE
  • 后序遍历：左子树、右子树、根 → FCGBIHEDA
• 广度优先遍历算法
  • 层序遍历：从上至下，从左至右，逐层遍历 → ABDFGHECI

由遍历序列还原二叉树：

1. 已知前序遍历和中序遍历结果，可以唯一还原一棵二叉树
2. 已知后序遍历和中序遍历结果，可以唯一还原一棵二叉树

**文件的创建方式：**二叉树采用前序遍历的方式创建，字符串"ABF##GC###DH#I##E##"中#表示该位置为空子树(NULL)。

文件说明：

二、头文件 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.c

create_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); #endif

cyclequeue.c 说明

各函数的实现逻辑与《数据结构篇(队列)》中的循环队列完全相同：

• create_cyclequeue：分配管理结构体 + 数组空间，head、tail 置 0
• is_empty_cycle_queue：head == tail判空
• is_full_cycle_queue：(tail+1) % CYCQUE == head判满
• en_cycle_queue：队尾下标处写入，tail = (tail+1) % CYCQUE
• de_cycle_queue：读取队头下标处数据，head = (head+1) % CYCQUE
• free_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_demo

valgrind 检测内存泄漏：

写二叉树务必检测内存泄漏，保证每一块 malloc 都有对应的 free

valgrind --leak-check=full ./tree_demo

运行输出结果：

ABFGCDHIE FBCGAHIDE FCGBIHEDA ABDFGHECI tree_node_cnt = 9 tree_deep = 4