C语言数据结构之树(保姆级讲解)
树是“一对多”的非线性存储结构,较链表、队列那些,树的概念会多点,涵盖的范围也较广。由根节点和若干子树构成;单个节点也可以看成树,只有一个树根节点
前言
树是“一对多”的非线性存储结构,较链表、队列那些,树的概念会多点,涵盖的范围也较广。
1 树概念
1.1 树基本术语
![](https://i-blog.csdnimg.cn/blog_migrate/fa23a6b537c4f8c49914cb4a2f605b8c.png)
双亲节点:以A、B、C、D为例,A是BCD的双亲节点;
孩子节点:以A、B、C、D为例,BCD是A的子节点;
兄弟节点:BCD有共同的父节点A,所以BCD之间又互为兄弟节点;
叶子节点:没有孩子节点的节点,例如K、L、M节点;
根节点:没有双亲结点的节点;
子树:A是整棵树的树根节点,单看BEFKL节点,也可以看成单独的树,B节点为该树的树根, 所以BEFKL节点称为子树;
树:由根节点和若干子树构成;单个节点也可以看成树,只有一个树根节点;
节点的度:该节点拥有孩子节点的个数,A节点的度为3;
树的度:比较树中各节点的度,最大节点的度为该树的度,以上的树的度为3;
树的深度(高度):根节点为第一层,然后依此类推,KLM在第四层,所以,以上树深度为4;
有序树:树中各节点位置不能互换的叫有序树;无序树,节点位置则可以互换;
空树:没有任何节点;
森林:由 n (n>=0)个互不相交的树组成的叫森林;以上去除 A 节点,分别以 B、C、D 为根节点的三棵子树就可以称为森林。
1.2 二叉树
二叉树:顾名思义,就是子节点的个数不能超过2个的有序树,只能0、1和2;二叉树又可以细分为满二叉树和完全二叉树;
满二叉树:二叉树中除了叶子结点,每个结点的度都为 2,则称为满二叉树;
完全二叉树:一个深度为k,有n个节点的二叉树中,节点按从上至下、从左到右的顺序进行编号,编号为 i (1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同则为完全二叉树。
2 二叉树节点的遍历
![图二](https://i-blog.csdnimg.cn/blog_migrate/772f76d3ba57498a74af18bd00a3a7c1.png)
2.1 前序遍历
公式:先“根”节点,再左子树,后右子树。
此处说的“根”节点并不是特指树的根节点,如图2,由树的根节点A开始遍历,然后遍历左节点B,然后以B节点作为“根”节点,继续套用公式,再左后右,所以下一个遍历D节点,直到叶子节点处不再有子节点,就往回找右节点,以此类推......
图2的前序遍历最终顺序为:A->B->D->H->E->C->F->I->G。
2.2 中序遍历
公式:先左子树,再“根”节点,后右子树。
如图2,把该树看成由根节点A和左、右子树组成的一棵树;先看左子树:套公式,先左,从H节点开始,再“根”遍历D,该“根”没有右节点,则继续往上找(在D、H组成的子树中,D为根,H为左;而在B、D、E组成的子树中,B为根,D为左,E为右节点),接下来遍历“根”节点B,后遍历右节点E,以此类推......
图2的中序遍历最终顺序为:H->D->B->E->A->I->F->C->G。
2.3 后序遍历
公式:先左子树,再右子树,后根节点。
后序遍历就不多解释了,跟前两个差不多逻辑,
图2的后序遍历最终顺序为:H->D->E->B->I->F->G->C->A。
3 树实例编写
3.1 实现逻辑概要
接下来我们要实现的树形结构并非二叉树,双亲节点下可以有多个孩子节点;
功能:
①可以在树形结构中,指定的节点下添加孩子节点;
②遍历树中节点,找出指定节点的双亲节点和孩子节点,并打印在终端;
③退出程序并释放节点内存空间。
3.2 程序分析
3.2.1 定义相关结构体
节点数据最大不能超过32个字节;
struct _bro结构体,用来链接双亲节点下的各兄弟节点;
struct _node结构体中,data指向节点具体数据,parent指向该节点的双亲节点,head_child指向首个孩子节点,child_count表示该节点下的孩子节点个数,cur_high表示该节点所在树结构中的层数;
struct _tree结构体,包含一个节点变量和树的深度(tree_high)。
typedef char Data_type; //数据类型
#define DATA_LEN_MAX 32
typedef struct _bro { //亲兄弟
struct _bro *next;
}Bro_t;
typedef struct _node {
Data_type *data; //节点数据
struct _node *parent; //双亲节点
struct _node *head_child; //孩子节点
int child_count; //孩子个数
Bro_t bro_list; //亲兄弟节点链表
int cur_high; //当前节点层次,根节点为1
}Node_t;
typedef struct _tree {
Node_t *node; //树的节点
int tree_high; //树的高度
}Tree_t;
3.2.2 节点位置遍历函数
传入参数:树和双亲结点数据;
通过比较节点数据找到双亲节点,并将该节点地址值返回;
查找的方法就是二叉树的先序遍历方法,先根节点,再左子树,后右子树,直到找到为止,在这里兄弟节点的链表就发挥了很大作用。
/*****************************************
* Fuction :查找双亲节点(类似前序遍历)
* root :传递树根
* Pdata :传递查找的父节点数据
* ***************************************/
Node_t *find_parent_node(Tree_t *root,Data_type *Pdata)
{
Node_t *p = root->node;
while(1) {
if(strcmp(p->data,Pdata) == 0){ //找到节点 退出
//printf("find parent node succeed .\n");
return p;
}
else{
if(p->head_child != NULL) { //判断该节点是否有子节点
p = p->head_child;
}
else {
if(p->bro_list.next != NULL) { //没有子节点,则判断是否有兄弟节点
p = (Node_t *)p->bro_list.next;
}
else {
while(1) {
p = p->parent;
if(p->parent == NULL) { //往树根节点方向查找还未遍历的节点,直到树根处退出遍历
printf("find parent node fail !\n");
return NULL;
}
if(p->bro_list.next != NULL) {
p = (Node_t *)p->bro_list.next;
break;
}
}
}
}
}
}
}
3.2.3 兄弟链表函数
参数:传递新添加的节点;
双亲节点的head_child作为兄弟链表表头,表尾node->bro_list.next指向NULL表示结束。
/********************************
* Fuction :链接亲兄弟节点
* node :添加的节点
* ******************************/
void bro_node_list(Node_t *node)
{
Node_t *p = node->parent;
Node_t *q = p->head_child;
if(p->child_count == 0) {
p->head_child = node;
node->bro_list.next = NULL;
p->child_count += 1;
}
else {
while(q->bro_list.next != NULL){
q = (Node_t *)q->bro_list.next;
}
q->bro_list.next = (Bro_t *)node;
node->bro_list.next = NULL;
}
}
3.2.4 添加节点函数
这里需要传递三个参数:树,父节点数据,新节点数据;
首先,需要为所创建的节点申请结构体变量内存空间和节点数据存放空间,内存申请失败则直接退出创建;如果创建新节点之前为空树,则新创建的节点作为树根节点,否则就通过函数find_parent_node查找父节点的位置,查找失败退出,成功就添加新节点,并将新节点添加到兄弟链表中。
该函数主要做的就是填充结构体变量,使各节点联系起来。
/*************************************************
* Fuciton :在树中创建一个新节点,新节点挂在双亲节点下
* root :传递树根节点
* Pdata :双亲节点的数据
* Data :新节点的数据
* ***********************************************/
void create_tree_node(Tree_t *root, Data_type *Pdata, Data_type *Data)
{
Node_t *node = (Node_t *)malloc(sizeof(Node_t));
Node_t *p = NULL;
Data_type *data_buf = (Data_type *)malloc(strlen(Data)+ 1);
if((node == NULL) || (data_buf == NULL)) {
printf("malloc failed !\n");
return ;
}
strcpy(data_buf,Data);
if(root->node == NULL) { //树根
root->node = node;
root->tree_high = 1;
node->data = data_buf;
node->parent = NULL;
node->head_child = NULL;
node->child_count = 0;
node->bro_list.next = NULL;
node->cur_high = 1;
}
else {
p = find_parent_node(root,Pdata);
if(p != NULL) { //找到双亲节点
node->data = data_buf;
node->parent = p;
node->head_child = NULL;
node->child_count = 0;
node->cur_high = p->cur_high + 1;
if(node->cur_high > root->tree_high) {
root->tree_high = node->cur_high;
}
bro_node_list(node);
}
else {
free(node);
free(data_buf);
}
}
}
3.2.5 节点内存释放函数
参数:传递树;
节点的内存释放只能从叶子节点开始,不然各节点的联系就会被破坏,从而无法找到其它节点,这里利用后序遍历法进行查找,先左子树,再右子树,后根节点;
通过for(p; p->head_child != NULL; p = p->head_child)查找树的最终左子树,然后判断该节点在兄弟链表中是否有其它的节点,如果有,则去查找该子树的叶子节点,从叶子节点开始释放,没有的话就释放掉,回到双亲节点继续查找。
/**********************************
* Fuction :释放掉节点申请的内存(后序遍历方法)
* root :传递树根节点
* *******************************/
void free_tree_nodes(Tree_t *root)
{
Node_t *p = root->node;
Node_t *temp = NULL;
int free_count = 0;
if(p == NULL) {
printf("empty tree! \n");
return;
}
for(p; p->head_child != NULL; p = p->head_child); //查找左子树的叶子节点
do {
if(p->bro_list.next != NULL) { //判断该节点是否有兄弟节点
temp = p;
printf(" free data is %s\n",temp->data);
p = (Node_t *)p->bro_list.next;
free(temp);
for(p; p->head_child != NULL; p = p->head_child);
}
else {
temp = p;
printf(" free data is %s\n",temp->data);
p = p->parent;
free(temp);
}
++free_count;
}while(p != NULL);
printf("%d-Node memory free OK.\n",free_count);
}
3.3 程序汇总
/****************************************
Fuction:C语言实现树
Time:11/21/2022
Author:Qurry
****************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char Data_type; //数据类型
#define DATA_LEN_MAX 32
typedef struct _bro { //亲兄弟
struct _bro *next;
}Bro_t;
typedef struct _node {
Data_type *data; //节点数据
struct _node *parent; //双亲节点
struct _node *head_child; //孩子节点
int child_count; //孩子个数
Bro_t bro_list; //亲兄弟节点链表
int cur_high; //当前节点层次,根节点为1
}Node_t;
typedef struct _tree {
Node_t *node; //树的节点
int tree_high; //树的高度
}Tree_t;
/*****************************************
* Fuction :查找双亲节点(类似前序遍历)
* root :传递树根
* Pdata :传递查找的父节点数据
* ***************************************/
Node_t *find_parent_node(Tree_t *root,Data_type *Pdata)
{
Node_t *p = root->node;
while(1) {
if(strcmp(p->data,Pdata) == 0){ //找到节点 退出
//printf("find parent node succeed .\n");
return p;
}
else{
if(p->head_child != NULL) { //判断该节点是否有子节点
p = p->head_child;
}
else {
if(p->bro_list.next != NULL) { //没有子节点,则判断是否有兄弟节点
p = (Node_t *)p->bro_list.next;
}
else {
while(1) {
p = p->parent;
if(p->parent == NULL) { //往树根节点方向查找还未遍历的节点,直到树根处退出遍历
printf("find parent node fail !\n");
return NULL;
}
if(p->bro_list.next != NULL) {
p = (Node_t *)p->bro_list.next;
break;
}
}
}
}
}
}
}
/********************************
* Fuction :链接亲兄弟节点
* node :添加的节点
* ******************************/
void bro_node_list(Node_t *node)
{
Node_t *p = node->parent;
Node_t *q = p->head_child;
if(p->child_count == 0) {
p->head_child = node;
node->bro_list.next = NULL;
p->child_count += 1;
}
else {
while(q->bro_list.next != NULL){
q = (Node_t *)q->bro_list.next;
}
q->bro_list.next = (Bro_t *)node;
node->bro_list.next = NULL;
}
}
/*************************************************
* Fuciton :在树中创建一个新节点,新节点挂在双亲节点下
* root :传递树根节点
* Pdata :双亲节点的数据
* Data :新节点的数据
* ***********************************************/
void create_tree_node(Tree_t *root, Data_type *Pdata, Data_type *Data)
{
Node_t *node = (Node_t *)malloc(sizeof(Node_t));
Node_t *p = NULL;
Data_type *data_buf = (Data_type *)malloc(strlen(Data)+ 1);
if((node == NULL) || (data_buf == NULL)) {
printf("malloc failed !\n");
return ;
}
strcpy(data_buf,Data);
if(root->node == NULL) { //树根
root->node = node;
root->tree_high = 1;
node->data = data_buf;
node->parent = NULL;
node->head_child = NULL;
node->child_count = 0;
node->bro_list.next = NULL;
node->cur_high = 1;
}
else {
p = find_parent_node(root,Pdata);
if(p != NULL) { //找到双亲节点
node->data = data_buf;
node->parent = p;
node->head_child = NULL;
node->child_count = 0;
node->cur_high = p->cur_high + 1;
if(node->cur_high > root->tree_high) {
root->tree_high = node->cur_high;
}
bro_node_list(node);
}
else {
free(node);
free(data_buf);
}
}
}
/**********************************
* Fuction :添加多个子树节点
* root :传递树根节点
* *******************************/
void add_tree_nodes(Tree_t *root)
{
Data_type pdata_buf[DATA_LEN_MAX],data_buf[DATA_LEN_MAX];
memset(pdata_buf,0,DATA_LEN_MAX);
memset(data_buf,0,DATA_LEN_MAX);
printf("window下输入ctrl+z完成创建;linux下输入ctrl+d完成创建\n");
if(root->node == NULL){
printf("please input tree root data : \n");
scanf("%s",data_buf);
create_tree_node(root, NULL, data_buf);
}
printf("please input Pdata & data :\n");
while(scanf("%s %s",pdata_buf,data_buf) != EOF) {
printf("pdata_buf:%s,data_buf:%s \n",pdata_buf,data_buf);
create_tree_node(root, pdata_buf, data_buf);
}
printf("tree high is %d\n",root->tree_high);
}
/**********************************
* Fuction :遍历打印树形结构
* root :传递树根节点
* *******************************/
void print_tree_node(Tree_t *root)
{
Data_type temp[DATA_LEN_MAX];
Node_t *p = NULL;
int i = 0;
printf("please input node data :");
scanf("%s",temp);
p = find_parent_node(root,temp);
if(p == NULL) {
printf("node data error! \n");
}
else {
if(p->parent != NULL)
printf("Node parent data :%s\n",p->parent->data);
if(p->head_child != NULL) {
p = p->head_child;
while(1) {
printf("Node child-%d:%s\n",i++,p->data);
if(p->bro_list.next == NULL)
break;
p = (Node_t *)p->bro_list.next;
}
}
}
}
/**********************************
* Fuction :释放掉节点申请的内存(后序遍历方法)
* root :传递树根节点
* *******************************/
void free_tree_nodes(Tree_t *root)
{
Node_t *p = root->node;
Node_t *temp = NULL;
int free_count = 0;
if(p == NULL) {
printf("empty tree! \n");
return;
}
for(p; p->head_child != NULL; p = p->head_child); //查找左子树的叶子节点
do {
if(p->bro_list.next != NULL) { //判断该节点是否有兄弟节点
temp = p;
printf(" free data is %s\n",temp->data);
p = (Node_t *)p->bro_list.next;
free(temp);
for(p; p->head_child != NULL; p = p->head_child);
}
else {
temp = p;
printf(" free data is %s\n",temp->data);
p = p->parent;
free(temp);
}
++free_count;
}while(p != NULL);
printf("%d-Node memory free OK.\n",free_count);
}
/*****************************
* Fuction : 模式菜单
* **************************/
int menu_select()
{
char mode[10];
printf("1:添加 2:打印 0:退出\n");
printf("Please input mode num: ");
scanf("%s",&mode);
if(mode[0] == '1')
return 1;
else if(mode[0] == '2')
return 2;
else if(mode[0] == '0')
return 0;
else
return -1;
}
void main()
{
int mode = -1;
Tree_t tree_root = {
.node = NULL,
.tree_high = 0,
};
Tree_t *tree_p = &tree_root;
while(1) {
mode = menu_select();
switch(mode)
{
case 0:
free_tree_nodes(tree_p);
return ;
case 1:
add_tree_nodes(tree_p);
break;
case 2:
print_tree_node(tree_p);
break;
default :
printf("mode input error !\n");
break;
}
}
}
4 测试结果
按照上图 图1 的树形结构进行测试,结果如下:
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)